实际使用`foldl`

Question

今天,当我使用一个小脚本时,我用foldl而不是foldl'.我得到了stack overflow,所以我进口Data.List (foldl')并对此感到满意.这是我的默认工作流程foldl.只需foldl'在懒惰版本评估时使用.

Real World Haskell说我们应该使用foldl'而不是foldl在大多数情况下.Foldr Foldl Foldl'说

通常选择在foldr和之间foldl'.

...

但是,如果组合函数在其第一个参数中是惰性的,则foldl可能会愉快地返回到达foldl'异常的结果.

一个给定的例子:

(?) :: Int -> Int -> Int
_ ? 0 = 0
x ? y = x*y

list :: [Int]
list = [2, 3, undefined, 5, 0]

okey = foldl (?) 1 list

boom = foldl' (?) 1 list

嗯,我很抱歉,但它相当学术,有趣但是学术上的例子.所以我在问,有没有实际使用的例子foldl？我的意思是,当我们无法取代foldl时foldl'.

PS我知道,定义术语很难practical,但我希望你能理解我的意思.

PPS我明白了,为什么懒惰foldl是默认的haskell.我不要求任何人移动山并默认严格版本.我只是对foldl函数的独占使用的例子非常感兴趣:)

PPPS嗯,foldl欢迎使用任何有趣的用法.

Answer 1

这是一个更实际的例子,使用经典的天真Fibonacci实现来模拟昂贵的计算:

fib :: Int -> Int
fib 0 = 1
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)

f :: Int -> Int -> Int
f a b = if b < 1000 then b else min b a

如果你有的话

> -- Turn on statistics for illustrative purposes
> :set +s
> foldl f maxBound $ map fib [30, 20, 15]
987
(0.02 secs, 0 bytes)
> foldl' f maxBound $ map fib [30, 20, 15]
987
(4.54 secs, 409778880 bytes)

在这里,我们在懒惰版本和严格版本之间的运行时性能方面存在巨大差异,懒惰版本以压倒性优势赢得胜利.当然,您的电脑数量可能因电脑而异,但您肯定会注意到执行速度的差异.foldl'每次计算发生的力量,而foldl不是.这对于类似的东西也很有用

> foldl f maxBound $ map length [repeat 1, repeat 1, replicate 10 1]
10

与fib示例不同,此计算在技术上涉及底部,因为length $ repeat 1永远不会完成其计算.如果没有两个参数f都是严格的(就像foldl'那样),我们实际上有一个程序停止而不是永远不会.

Answer 2

我可以想到一个(虽然它可能只会通过优化编译器产生良好的代码):

last = foldl (\_ x -> x) (error "emptyList")

它没有正确的行为foldl':

> foldl (\_ x -> x) (error "emptyList") [error "foo", "last"]
"last"
> foldl' (\_ x -> x) (error "emptyList") [error "foo", "last"]
"*** Exception: foo