Recursion with eliminator

interleave.hs

unlist2 :: [a] -> [b] 
        -> (a -> [a] -> b -> [b] -> c -> c)
        -> (a -> [a] -> c)
        -> (b -> [b] -> c)
        -> c
        -> c
unlist2 l1 l2 hcc hcn hnc hnn= case (l1, l2) of
    (x:xs, y:ys) -> hcc x xs y ys (unlist2 xs ys hcc hcn hnc hnn)
    (x:xs, [])   -> hcn x xs  
    ([], y:ys)   -> hnc y ys
    ([], [])     -> hnn

-- interleave with pattern matching (non-structural recursion)
interleave :: [a] -> [a] -> [a]
interleave []     l2 = l2
interleave (x:xs) l2 = x : interleave l2 xs

-- interleave with pattern matching (structural recursion on two lists)
interleave' :: [a] -> [a] -> [a]
interleave' l1 l2 = helper l1 l2 True
    where
        helper :: [a] -> [a] -> Bool -> [a]
        helper (x:xs) l2     True  = x : helper xs l2 False
        helper l1     (y:ys) False = y : helper l1 ys True
        helper []     l2     _     = l2
        helper l1     []     _     = l1 

-- interleave with eliminator
interleave'' :: [a] -> [a] -> [a]
interleave'' l1 l2 = fst $ unlist2 l1 l2 (\x xs y ys (l, flag) -> (if flag then x:y:l else y:x:l, not flag)) 
                                         (\x xs -> (x:xs, True))
                                         (\x xs -> (x:xs, True))
                                         ([], True)

mutual-recursive.hs

data Nat = Zero | Suc Nat
  deriving (Show)

unNat :: Nat -> a -> (Nat -> a -> a) -> a
unNat Zero    fz fs = fz
unNat (Suc n) fz fs = fs n (unNat n fz fs)

evenOrOdd = \n -> unNat n (True, False) (\n' (isEven, isOdd) -> (isOdd, isEven))

even :: Nat -> Bool
even = fst . evenOrOdd

odd :: Nat -> Bool
odd  = snd . evenOrOdd