3

我正在尝试在 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我没有知道为什么。

4

2 回答 2

3

假设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在更简单的情况下，您只想(x-1) `op` y在递归调用的结果上调用它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 所说，你应该有

times = PR Z (C plus [P 2, P 3])
于 2012-11-25T01:55:11.010 回答
3

这个时间定义似乎有效：

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)

更详细的解释...

我们知道这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(which is P 3) 和x*y(which is 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的答案是关闭的。

于 2012-11-25T01:14:52.933 回答