`foldl`的实际应用

Question

`foldl`的实际应用

16

今天我在编写一个小脚本时，我使用了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时。

附言：我知道，很难定义术语“实际”，但我希望您能理解我的意思。

另外，我理解为什么懒惰的foldl是Haskell中的默认设置。我不要求任何人移山倒海并将严格版本作为默认设置。我只是对独占使用foldl函数的示例真的很感兴趣 :)

最后，任何有趣的foldl用法都欢迎。

- d12frosted

4

不仅仅是避免使用 undefined，你还可以使用 foldl 来避免可能昂贵的操作。如果你的折叠函数在成功操作后提前退出，则可以通过懒惰性避免执行昂贵的计算。可能有更清晰的写法（比如说单子），但是折叠对于编译器优化来说也很好用。 - bheklilr

是的，我正在考虑这个问题。但是想不出一个好的这样函数的例子。 - d12frosted

2个回答

5

我可以想到一种方法（尽管这可能只有在使用优化编译器时才能产生良好的代码）：

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

- Joachim Breitner

嗯，这看起来真的像是_ ? 0 = 0。但无论如何，感谢您提供另一个例子。 - d12frosted

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- bheklilr · Accepted Answer

下面是一个更实际的例子，使用经典的朴素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示例不同，这个计算涉及bottom，因为length $ repeat 1将永远无法完成其计算。通过不使f的两个参数都是严格的（就像foldl'那样），我们实际上拥有一个会停止的程序，而不是永远不会停止的程序。