Foldr 与 foldl (或 foldl’)的含义

首先,我正在读的 真实世界 Haskell说永远不要使用 foldl而是使用 foldl',所以我相信它。

但是我不清楚什么时候使用 foldrfoldl'。虽然我可以看到它们如何以不同的方式摆在我面前,但是我太笨了,无法理解什么时候“哪个更好”我想在我看来,用哪个答案并不重要,因为它们都会得出相同的答案(不是吗?).事实上,我以前使用这个构造的经验来自 Ruby 的 inject和 Clojure 的 reduce,它们似乎没有“左”和“右”版本。(附带问题: 他们使用哪个版本?)

任何能够帮助像我这样缺乏智慧的人的见解都是非常感激的!

41158 次浏览

它们的语义不同,所以不能只交换 foldlfoldr。一个把元素从左边折叠起来,另一个从右边折叠起来。这样,操作符将以不同的顺序应用。这对于所有非关联运算都很重要,比如减法运算。

Haskell.org 有一个关于这个主题的有趣的 文章

简而言之,当累加器函数的第二个参数是惰性的时候,foldr更好。阅读更多哈斯克尔 wiki 的 堆栈溢出(双关语)。

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

这里的一个重要区别是,如果只能使用 x的值来计算 f x y的结果,那么 foldr就不需要检查整个列表。比如说

foldr (&&) False (repeat False)

返回 False,而

foldl (&&) False (repeat False)

永远不会终止。(注意: repeat False创建一个无限列表,其中每个元素都是 False。)

另一方面,foldl'是尾递归和严格的。如果您知道无论如何都要遍历整个列表(例如,对列表中的数字求和) ,那么 foldl'foldr的空间(可能还有时间)效率更高。

foldl'在99% 的使用中优于 foldl的原因是,在大多数情况下,它可以在常量空间中运行。

以函数 sum = foldl['] (+) 0为例。当使用 foldl'时,总和会立即被计算出来,因此将 sum应用于无限列表将永远运行下去,并且很可能在常量空间中运行(如果您使用的是诸如 Ints、 Doubles、 Floats 之类的东西)。如果数字大于 maxBound :: Int,则 Integer将使用比常量空间更多的空间)。

使用 foldl,可以构建一个 thunk (类似于如何得到答案的配方,可以在以后进行计算,而不是存储答案)。这些 thunk 可能会占用很多空间,在这种情况下,评估表达式比存储 thunk 要好得多(导致堆栈溢出 & hellip; 并导致 & hellip; 哦,没关系)

希望能帮上忙。

顺便说一下,Ruby 的 inject和 Clojure 的 reducefoldl(或 foldl1,取决于您使用的版本)。通常,当一种语言中只有一种形式时,它是左折的,包括 Python 的 reduce、 Perl 的 List::Util::reduce、 C + + 的 accumulate、 C # 的 Aggregate、 Smalltalk 的 inject:into:、 PHP 的 array_reduce、 Mathematica 的 reduce0等等。Common Lisp 的 reduce默认为左折叠,但是有一个右折叠的选项。

康拉德指出,它们的语义是不同的,它们甚至没有相同的类型:

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 (:))

会给你一个类型错误。

foldr是这样的:

Right-fold visualization

foldl是这样的:

Left-fold visualization

背景: Haskell wiki 上的 弃牌