为什么Haskell中的递归成语是"'n + 1'和'n'"而不是"'n'和'n-1'"？

Question

我正在通过Graham Hutton的Haskell书籍,在他的递归章节中,他经常在"n + 1"上进行模式匹配,如:

myReplicate1 0 _ = []
myReplicate1 (n+1) x = x : myReplicate1 n x

为什么这样而不是以下,(1)看起来功能相同,(2)在理解递归发生的事情方面更直观:

myReplicate2 0 _ = []
myReplicate2 n x = x : myReplicate2 (n-1) x

这里有什么我想念的吗？或者只是风格问题？

Answer 1

那些是第一个函数中的n + k个模式(应该避免!).两个函数都做同样的事情,除了n + k一个不匹配负数.但是,建议使用后者,如果您不想故意使用负数,可以采用后者,因为n + k模式无论如何都要被删除.

所以不,你什么都不缺,这确实是风格问题,但我很少看到野外的n + k模式.

Answer 2

我认为背后的想法是这样的:我们可以为自然数(0,1,...)定义一个类型,如下所示:

data Natural = Z -- zero
             | S Natural -- one plus a number; the next number; the "successor"

0 = Z,1 = S Z等等.这个系统被称为Peano算术,并且几乎是数学中的一个标准,作为"数字"实际定义的(起点).您可以继续将Integers 定义为s的对(-ish)Natural,依此类推.

当你这样做时,使用这样的模式匹配是很自然的:

myReplicate1 Z _ = []
myReplicate1 (S n) x = x : myReplicate1 n x

我认为(这只是猜测)n+1模式背后的想法是我刚刚描述的机器版本.所以,n+1要被认为是模式S n.如果你这样想,n+1模式似乎很自然.这也清楚地说明了为什么我们有这样的条件n >= 0.我们只能代表n >= 0使用该类型Natural.