Program to find the result of primitive recursive functions

Question

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.

Answer 1

Given f,

f :: [a] -> b

and g_k,

g_k :: [a] -> a

we want to produce h,

h :: [a] -> b

so the composition should be like

compo :: ([a] -> b) -> [[a] -> a] -> [a] -> b
compo f gs xs = f (map ($ xs) gs)

Example: http://codepad.org/aGIKi8dF

---

Edit: It can also be written in applicative style (eliminating that $) as

compo f gs xs = f (gs <*> pure xs)