Program to find the result of primitive recursive functions
- by alphomega
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.
