haskell - 原始递归函数

Question

我正在尝试定义一些 basic Primitive Recursive Haskell 中的函数。为什么我的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*x = 0 而不是 1。

请注意，我必须更改 eval (C ...) 的定义才能编译:

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

更详细的解释...

我们知道对于某些 h，times 的形式为 PR Z 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。

那么，为了得到 (x+1)*y = y+x*y，h 必须是什么？我们需要添加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。