haskell - 寻找原始递归函数结果的程序

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

问题在于我尝试创建组合构造函数 cn。当涉及到基本情况时，f 不再是部分应用程序，而是函数的结果。然而该函数需要一个函数作为第一个参数。我该如何处理这个问题？

谢谢。

Answer 1

给定 f，

f :: [a] -> b

和 g_k，

g_k :: [a] -> a

我们想要产生 h，

h :: [a] -> b

所以组成应该是这样的

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

示例: http://codepad.org/aGIKi8dF

编辑:它也可以写成应用风格(消除 $ )为

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