Программа для поиска результат примитивно рекурсивных функций

Question

Я пишу программу, чтобы решить результат примитивно рекурсивных функций:

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) 

эти функции и конструкторы определены здесь: http://en.wikipedia.org/wiki/Primitive_recursive_function

Этот вопрос с моей попыткой создать конструктор compositon, cn. Когда он попадает в базовый регистр, f больше не является частным приложением, а результатом функции. Однако функция ожидает, что функция станет первым аргументом. Как я могу справиться с этой проблемой?

Спасибо.

Answer 1

Учитывая е,

f :: [a] -> b 

и g_k,

g_k :: [a] -> a 

мы хотим производить час,

h :: [a] -> b 

поэтому композиция должна быть как

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

Пример: http://codepad.org/aGIKi8dF

---

Edit: Это может быть также записано в аппликативном стиле (исключая, что $) в

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