foldl更喜欢它的严格表弟，foldl'？ [英] Is foldl ever preferable to its strict cousin, foldl'?

问题描述

Haskell有两个左列函数用于列表： foldl 和一个严格版本， foldl'。非严格 foldl 的问题在于它构建了一个thunk的塔：

  foldl（+）0 [1..5] 
  - > （（（（0 + 1）+2）+ 3）+4）+ 5 
  - > 15 
  

这会浪费内存，并且如果列表中的项目太多，可能会导致堆栈溢出。另一方面， foldl'强制每个物品都有累加器。

然而，就我而言告诉： foldl'在语义上等同于 foldl 。评估 foldl（+）0 [1..5] 到标准形式需要强制累加器在某个点。如果我们不需要头部正常形式，我们不会评估 foldl（+）0 [1..5] 开始。

是否有任何令人信服的理由让人们想要 foldl 超过 foldl'的行为

解决方案

foldl and foldl'在语义上不等同。微不足道的反例：

  Prelude Data.List> foldl（\ xy  - > y）0 [undefined，1] 
 1 
 Prelude Data.List> foldl'（\xy  - > y）0 [undefined，1] 
 ***例外：Prelude.undefined 
  

然而，实际上，由于您提到的原因，您通常需要 foldl'。

Haskell has two left fold functions for lists: foldl, and a "strict" version, foldl'. The problem with the non-strict foldl is that it builds a tower of thunks:

    foldl (+) 0 [1..5]
--> ((((0 + 1) + 2) + 3) + 4) + 5
--> 15

This wastes memory, and may cause a stack overflow if the list has too many items. foldl', on the other hand, forces the accumulator on every item.

However, as far as I can tell, foldl' is semantically equivalent to foldl. Evaluating foldl (+) 0 [1..5] to head normal form requires forcing the accumulator at some point. If we didn't need a head-normal form, we wouldn't be evaluating foldl (+) 0 [1..5] to begin with.

Is there any compelling reason one would want the behavior of foldl over that of foldl' ?

解决方案

foldl and foldl' are not semantically equivalent. Trivial counterexample:

Prelude Data.List> foldl (\x y -> y) 0 [undefined, 1]
1
Prelude Data.List> foldl' (\x y -> y) 0 [undefined, 1]
*** Exception: Prelude.undefined

In practice, however, you usually want the strict foldl' for the reasons you mentioned.

这篇关于foldl更喜欢它的严格表弟，foldl'？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！