有时候我们需要尾递归

sum :: [Int] -> Int
sum [] = 0
sum (x:xs) = x + sum xs

模拟求值：

sum [1..10]
1 + sum [2..10]
1 + (2 + sum [3..10])
1 + (2 + (3 + sum [4..10]))
...
1 + (2 + (3 + 49))
1 + (2 + 52)
1 + 54
55

可以看出在上面这个实现中，需要占用O(n)的空间，如果是堆栈的话，就容易溢出了。

解决方案第一步就是改为尾递归形式。因为尾递归形式中，递归调用是函数体的最后一步，所以进入递归调用时可以放心地把当前栈帧丢弃，所以不会有堆栈溢出的问题:

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

对于严格求值的语言，这样就够了；但是对于惰性求值的语言，还存在另一个问题，模拟求值一下就可以看得出来：

sum' 0 [1..10]
sum' (1+0) [2..10]
sum' (2+(1+0)) [3..10]
sum' (3+(2+(1+0))) [4..10]
...
sum' (10+(9+36)) []
sum' (10+45) []
sum' 55 []
55

因为 sum' 的第二个参数是惰性求值的，所以计算过程中还是会把这个 thunk 留着，不到万不得已不会对它求值，于是依然导致O(n)的空间占用。

解决这个问题也好办，给 accu 参数加一个 严格求值的标记 就好了：

sum' !accu [] = accu
sum' !accu (x:xs) = sum' (x+accu) xs
sum = sum' 0

这下 sum 函数就跑得飞快了。

前一个版本的 sum 是 foldr (+) 0 ，后一个版本是 foldl' (+) 0 。

有时候我们不需要尾递归

concat :: [[a]] -> [a]
concat (x:xs) = x ++ concat xs

模拟求值：

concat [[1], [2], [3], ...]
(1:[]) ++ concat [[2], [3], ...]
1 : ([] ++ concat [[2], [3], ...])

求值完毕了。为什么？因为 (++) 的第二个参数是惰性求值的，只有当我们需要后面的元素时才会触发后续的求值。 所以 concat 不会栈溢出，常数级空间占用，并且还有一个好处，可以处理无穷列表。

另外： concat = foldr (++) []