惰性求值和尾递归

2011-04-23 黄毅

参考: HaskellWiki: Stack overflow

有时候我们需要尾递归

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 函数就跑得飞快了。

前一个版本的 sumfoldr (+) 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 (++) []


blog comments powered by Disqus

转载请注明出处,收藏或分享这篇文章到: