I'm writing a program to solve the result of primitive recursive functions:

  1 --Basic functions------------------------------
  2
  3 --Zero function
  4 z :: Int -> Int
  5 z = \_ -> 0
  6
  7 --Successor function
  8 s :: Int -> Int
  9 s = \x -> (x + 1)
 10
 11 --Identity/Projection function generator
 12 idnm :: Int -> Int -> ([Int] -> Int)
 13 idnm n m = \(x:xs) -> ((x:xs) !! (m-1))
 14
 15 --Constructors--------------------------------
 16
 17 --Composition constructor
 18 cn :: ([Int] -> Int) -> [([Int] -> Int)] -> ([Int] -> Int)
 19 cn f [] = \(x:xs) -> f
 20 cn f (g:gs) = \(x:xs) -> (cn (f (g (x:xs))) gs)

these functions and constructors are defined here: http://en.wikipedia.org/wiki/Primitive_recursive_function

The issue is with my attempt to create the compositon constructor, cn. When it gets to the base case, f is no longer a partial application, but a result of the function. Yet the function expects a function as the first argument. How can I deal with this problem?

Thanks.