Haskell递归'sum'函数

Question

我发现很难理解以下递归函数的机制:

sums (x:y:ys) = x:sums(x + y : ys)
sums xs = xs

sums ([0..4])

Output:
[0, 1, 3, 6, 10]

这一行究竟发生了什么？:

x:sums(x + y : ys)

我想说在程序可以将'x'附加到列表之前,必须首先执行函数sum(x + y:ys).但在这种情况下,'x'只会在递归循环结束时附加到列表中一次 - 这不会产生给定的输出......那么我逻辑中的缺陷在哪里？

我的后续问题:我应该如何以合乎逻辑的方式看待/处理递归函数,这会(希望)将我引向'aha-erlebnis'？

任何帮助深表感谢!

Answer 1

您可以通过逐步减少来理解Haskell代码.也许以下示例缩减序列有助于您的aha.

(Haskell实现实际上会执行与此类缩减步骤相关的操作,但可能会以不同的顺序执行.但是,您获得了相同的最终结果).

在此示例中,您将从:

sums [0..4]

[0..4]稍微扩展一下符号:

sums (0 : 1 : [2..4])

现在我们看到的第一个方程式sums比赛,有x = 0,y = 1和ys = [2..4].所以我们得到:

0 : sums (0 + 1 : [2..4])

我们可以计算0 + 1:

0 : sums (1 : [2..4])

并扩大[2..4]一点:

0 : sums (1 : 2 : [3..4])

现在我们看到的第一个方程式sums的比赛,这一次用x = 1,y = 2和ys = [3..4].所以我们得到:

0 : 1 : sums (1 + 2 : [3..4])

我们可以计算1 + 2:

0 : 1 : sums (3 : [3..4])

并扩大[3..4]一点:

0 : 1 : sums (3 : 3 : [4..4])

现在我们看到的第一个方程式sums的比赛,这一次用x = 3,y = 3和ys = [4..4].所以我们得到:

0 : 1 : 3 : sums (3 + 3 : [4..4])

我们可以计算3 + 3:

0 : 1 : 3 : sums (6 : [4..4])

并扩大[4..4]:

0 : 1 : 3 : sums (6 : 4 : [])

现在我们看到的第一个方程式sums的比赛,这一次用x = 6,y = 4和ys = [].所以我们得到:

0 : 1 : 3 : 6 : sums (6 + 4 : [])

我们可以计算6 + 4:

0 : 1 : 3 : 6 : sums (10 : [])

这一次,第一个方程式sums不匹配.但第二个等式匹配.所以我们得到:

0 : 1 : 3 : 6 : 10 : []

这是观察到的输出[0, 1, 3, 6, 10].