影响与foldrfoldl(或foldl')

Question

首先， 现实世界Haskell, 我读，说到从未使用 foldl 和而不是使用 foldl'.所以我相信它。

但我朦胧的时使用 foldr 与 foldl'.虽然我可以看到的结构如何，他们不同的工作奠定了在我面前，我太愚蠢了解当"，这是更好的。" 我猜这似乎我喜欢它不应该有真正的问题是使用，因为他们都产生同样的答复(不是吗?).事实上，我以前的经验，这种建构是红宝石的 inject 高质量的技术资源的 reduce, ，这似乎没有"左边"，"右边"的版本。(侧的问题：哪个版本做他们使用？)

任何了解，可以帮助一个智慧挑战的排序喜欢我将非常感谢！

Answer 1

有foldr f x ys递归其中ys = [y1,y2,...,yk]看起来像

f y1 (f y2 (... (f yk x) ...))

而对于foldl f x ys递归看起来像

f (... (f (f x y1) y2) ...) yk

这里，一个重要区别是，如果f x y的结果可使用x才值来计算，然后foldr并不”需要检查整个列表。例如

foldr (&&) False (repeat False)

返回False而

foldl (&&) False (repeat False)

从不终止。 （注意：repeat False创建一个无限列表，其中的每一个元素是False）

在另一方面，foldl'是尾递归和严格。如果你知道你将不得不遍历整个列表不管是什么（例如，在列表中总结的数字），然后foldl'更节省空间（也可能时间），比foldr高效。

Answer 2

foldr看起来像这样：

foldl看起来像这样：

上下文：折叠上Haskell的维基

Answer 3

他们的语义不同所以你不能仅仅是交换 foldl 和 foldr.一个褶皱的元素从左边，其它权利。这种方式，操作者被应用在一个不同的顺序。这个问题对所有非联合行动，诸如减。

Haskell.org 有一个有趣的 文章 该问题。

Answer 4

不久，foldr是更好，当蓄能器的功能是在其第二个参数懒惰。更多详情的Haskell wiki的堆栈溢出（双关语意）。

Answer 5

原因foldl'优选foldl各种用途的99％是，它可以在恒定空间大多数用途运行。

取功能sum = foldl['] (+) 0。当使用foldl'，总和立即计算，因此应用sum一个无限名单将只是一直运行下去，并且极有可能在不断的空间（如果你使用像Ints，Doubles，Floats。Integers将使用超过一定的空间更如果数目变得比maxBound :: Int）放大。

通过foldl，一个thunk建立起来（如，如何得到答案配方，其可以随后评估，而不是存储回答）。这些可以的thunk占用大量的空间，在这种情况下，更好的做法是计算表达式，而不是存储在thunk（导致堆栈溢出......并导致你...哦，没关系）

希望有所帮助。

Answer 6

顺便说一句，Ruby的inject和Clojure的reduce被foldl（或foldl1，这取决于你使用的版本）。通常情况下，当只有一个在语言形式，它是左折，包括Python的reduce，Perl的List::Util::reduce，C ++的accumulate，C＃的Aggregate，Smalltalk的inject:into:，PHP的array_reduce，Mathematica的Fold等的Common Lisp的reduce默认为左折叠但有一个为正确的折叠的选项。

Answer 7

如康拉德所指出的，它们的语义是不同的。他们甚至没有相同的类型：

ghci> :t foldr
foldr :: (a -> b -> b) -> b -> [a] -> b
ghci> :t foldl
foldl :: (a -> b -> a) -> a -> [b] -> a
ghci> 

例如，列表追加操作符（++）可以与foldr实现为

(++) = flip (foldr (:))

，而

(++) = flip (foldl (:))

会给你一个类型的错误。