haskell - 理解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。