A program for finding the result of primitive recursive functions
I am 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 problem is trying to create a compositon constructor, cn. When it hits the base register, f is no longer a private application, but the result of a function. However, the function expects the function to be the first argument. How can I solve this problem?
Thanks.
+2
a source to share
1 answer
Given f,
f :: [a] -> b
and g_k,
g_k :: [a] -> a
we want to create 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 an applicative style (excluding this $
) as
compo f gs xs = f (gs <*> pure xs)
+3
a source to share