理解sum函数的实现

Question

我开始与Haskell一起玩,并遇到了以下sum函数的实现:

sum [] = 0
sum (x:xs) = x + sum xs

然后有一个解释,显示函数在一个真实的例子中的行为:

sum [1,2,3]

1 + (sum [2,3])
1 + (2 + sum [3])
1 + (2 + (3 + sum []))
1 + (2 + (3 + 0))
= 6

我不明白,为什么每次sum [x]调用时,列表都会减少1个元素？

我唯一的假设是,当构造(x:xs)执行时,x列表的元素不仅被检索,而且被删除(类似于栈pop()方法.),但我不确定这一点.

Answer 1

在表示法中x:xs,x是列表的头部,它是1个项目,xs是列表的尾部,它是0个或更多项目的列表.

由于递归调用是在xs上,因此每个递归级别的问题大小集都会减少1.

Answer 2

没有"从列表中删除元素"这样的事情.列表是不可变的,就像任何其他对象一样.现在,关于实施,在:

sum (x:xs) = x + sum xs

你是一个模式匹配列表到它的头部x和列表的其余部分(没有头部)xs.具体来说,sum [1, 2, 3]你会得到:

sum (1:[2, 3]) = 1 + sum [2, 3]

如果你还记得,(:)用于将一个元素附加到列表中.所以:1:[2, 3]其实[1, 2, 3]也可以写成:1:2:3:[].

你唯一应该记住的是模式匹配(x:xs),意味着:将列表的头部和列表x的其余部分放入xs.