原始递归函数

Question

我试图在Haskell中定义一些basic Primitive Recursive函数。为什么我的times函数递归太多次（即eval times[x,y]导致(x+1)*y）？我认为我的问题通常是由于对组合函数的工作原理不了解。请不要在没有解释的情况下给出答案来澄清我的理解。

import Prelude hiding (pred,and,or,not) 

data PR = Z 
     | S 
     | P Int 
     | C PR [PR] 
     | PR PR PR 
     deriving Show 
eval :: PR -> [Integer] - Integer 
eval Z _ = 0 
eval S [x] = x+1 
eval (P n) xs = nth n xs 
eval (C f gs) xs = eval f (map (\g -> eval g xs) gs) 
eval (PR g h) (0:xs) = eval g xs 
eval (PR g h) (x:xs) = eval h ((x-1) : eval (PR g h) ((x-1):xs) : xs) 

nth _ [] = error "nth nil" 
nth 0 _ = error "nth index" 
nth 1 (x:_) = x 
nth (n) (_:xs) = nth (n-1) xs 

one = C S [Z] 
plus = PR (P 1) (C S [P 2]) 
times = PR (P 1) (C plus [P 2, P 3]) 

我已经尝试了一些其他的事情times最接近的是times = PR (P 1) (C plus[P 2, P 2]但就出来2x*y我想：“嗯，我会刚刚取代那些P 2的与Z之一，那么这将是x*y “这实际上使其成为y的身份识别功能，我不知道为什么。

Answer 1

此定义时间似乎工作：

times' = PR Z (C plus [P 2, P 3]) 

*Main> eval times' [6,7] 
42 

这是有道理的，因为0 * * = 0而不是1

注意，我不得不改变的eval (C ...)的定义，以便为它编译：

eval (C f gs) cs = eval f (map (\g -> eval g cs) gs) 

更详细的解释...

我们知道times的形式为PR Z h，其中一些h。

让我们扩展eval (PR Z h) (x+1:y:ys) ...

eval (PR z h) (x+1:y:ys) 
    = eval h ((x+1-1) : eval (PR g h) ((x+1-1):y:ys) : y : ys) 
    = eval h (x : eval (PR Z h) (x:y:ys) : y : ys) 
    = eval h (x : x*y : y : ys) 

因为通过归纳我们知道eval (PR z h) (x:y:ys) = x*y。

那么h必须是为了得到(x+1)*y = y+x*y？我们需要添加y（这是P 3）和x*y（这是P 2），所以我们应该定义h为：

h = C plus [P 2, P 3] 

如果使用P 1代替Z，那么你的基本情况是y而不是0：

eval (PR (P 1) ...) (0:y) = eval (P 1) (y) = y 

递归保持不变，所以你在回答中关闭了y。

Answer 2

假设op的形式为PR something (C otherThing projections)。然后，如果x > 0，

eval op [x,y] 

电话

eval (C otherThing projections) [x-1, (x-1) `op` y, y] 

的otherThing越高排名op从构成操作。在更简单的情况下，您只想调用递归调用y的结果(x-1) `op` y，因此投影应该选择参数列表的第二个和第三个元素。

因此，我们有

times = PR something (C plus [P 2, P 3]) 

因为我们有递归方程

x*y = (x-1)*y + y 

其不涉及分离的x-1。

现在，当达到基本情况x == 0时，递归调用应返回基本结果。对于乘法运算，当然是0，因此something应该是Z，独立于y，而不是y，其中P 1会给你。

因此，user5402 said，你应该有

times = PR Z (C plus [P 2, P 3])