foldr与foldl(或foldl')的含义

首先,我正在阅读的真实世界Haskell表示永远不会使用foldl而是使用foldl'.所以我相信它.

但我对什么时候使用foldrvs. 朦胧foldl'.虽然我可以看到他们如何以不同的方式摆放在我面前的结构,但是当"哪个更好"时,我太愚蠢了.我想在我看来似乎并不重要,因为它们都产生相同的答案(不是吗？).事实上,我以前使用这个结构的经验来自Ruby inject和Clojure reduce,它们似乎没有"左"和"右"版本.(附带问题:他们使用哪个版本？)

任何有助于像我这样的智能挑战的洞察力都会非常感激!

1> Chris Conway..：

---

对于递归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.

---

为避免混淆,请注意括号不显示实际的评估顺序.由于Haskell是惰性的,因此将首先评估最外层表达式.

---

在foldr中,它计算为f y1 thunk,因此它返回False,但是在foldl中,f不能知道它的任何参数.在Haskell中,无论是否是尾递归,它都会导致thunk溢出,即thunk是太大.foldl'可以在执行时立即减少thunk.

2> Greg Bacon..：

---

foldr 看起来像这样:

foldl 看起来像这样:

上下文:折叠 Haskell维基

3> Konrad Rudol..：

---

他们的语义不同,所以你不能只交换foldl和foldr.一个元素从左侧向上折叠,另一个元素从右侧折叠.这样,操作员以不同的顺序应用.这对于所有非关联操作都很重要,例如减法.

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

4> mattiast..：

---

简而言之,foldr当累加器函数在其第二个参数上是惰性时更好.阅读更多Haskell wiki的Stack Overflow(双关语).

5> Axman6..：

---

最理想的原因foldl'是foldl99%的用途是它可以在大多数用途的恒定空间中运行.

采取这个功能sum = foldl['] (+) 0.当foldl'使用时,会立即计算总和,因此应用于sum无限列表将永远运行,并且很可能在恒定空间中运行(如果您使用的是Ints,Doubles,Floats等Integers将使用多于常量空间,如果数字变得大于maxBound :: Int).

有了foldl,就会建立一个thunk(就像一个如何获得答案的方法,可以在以后评估,而不是存储答案).这些thunk可以占用很多空间,在这种情况下,评估表达式比存储thunk要好得多(导致堆栈溢出......并导致你......哦,没关系)

希望有所帮助.

6> newacct..：

---

顺便说一句,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默认左折,但有一个右折叠选项.

---

这个评论很有帮助,但我会很感激.

7> Jonas..：

---

正如康拉德指出的那样,他们的语义是不同的.它们甚至没有相同的类型:

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

例如,列表追加运算符(++)可以用foldras 实现

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

而

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

会给你一个类型错误.