blocks|key|1849609|text|它们的语义不同，所以不能简单地将foldl和foldr互换。一个从左边折叠元素，另一个从右边折叠。这样，运算符将以不同的顺序应用。这对所有非关联操作都很重要，比如减法。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|1849610|Haskell.org在这个主题上有一个有趣的article。|1849611|entityMap|0|LINK|mutability|MUTABLE|url|http://haskell.org/|1|http://haskell.org/haskellwiki/Foldr_Foldl_Foldl%2527^0|G|5|M|5|0|0|B|0|N|7|1|0^^$0|@$1|2|3|4|5|6|7|R|8|@$9|S|A|T|B|C]|$9|U|A|V|B|C]]|D|@]|E|$]]|$1|F|3|G|5|6|7|W|8|@]|D|@$9|X|A|Y|1|Z]|$9|10|A|11|1|12]]|E|$]]|$1|H|3|-4|5|6|7|13|8|@]|D|@]|E|$]]]|I|$J|$5|K|L|M|E|$N|O]]|P|$5|K|L|M|E|$N|Q]]]]

Their semantics differ so you can't just interchange <code>foldl</code> and <code>foldr</code>. The one folds the elements up from the left, the other from the right. That way, the operator gets applied in a different order. This matters for all non-associative operations, such as subtraction.

<a href="http://haskell.org" rel="noreferrer">Haskell.org</a> has an interesting <a href="http://haskell.org/haskellwiki/Foldr_Foldl_Foldl%27" rel="noreferrer">article</a> on the subject.

blocks|key|2063628|text|简而言之，当累加器函数在第二个参数上是惰性的时，foldr更好。在Haskell+wiki的Stack+Overflow上阅读更多内容(双关语)。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|2063629|entityMap|0|LINK|mutability|MUTABLE|url|http://www.haskell.org/haskellwiki/Stack_overflow^0|O|5|1A|E|0|0^^$0|@$1|2|3|4|5|6|7|N|8|@$9|O|A|P|B|C]]|D|@$9|Q|A|R|1|S]]|E|$]]|$1|F|3|-4|5|6|7|T|8|@]|D|@]|E|$]]]|G|$H|$5|I|J|K|E|$L|M]]]]

Shortly, <code>foldr</code> is better when the accumulator function is lazy on its second argument. Read more at Haskell wiki's <a href="http://www.haskell.org/haskellwiki/Stack_overflow" rel="noreferrer">Stack Overflow</a> (pun intended).

blocks|key|2063691|text|foldr+f+x+ys的递归，其中ys+=+[y1,y2,...,yk]类似于|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|2063692|f+y1+(f+y2+(...+(f+yk+x)+...))|code-block|syntax|javascript|2063693|而foldl+f+x+ys的递归看起来像这样|2063694|f+(...+(f+(f+x+y1)+y2)+...)+yk|2063695|这里一个重要的区别是，如果只使用x的值就可以计算出f+x+y的结果，那么foldr就不需要检查整个列表。例如|2063696|foldr+(&&)+False+(repeat+False)|2063697|返回False，而|2063698|foldl+(&&)+False+(repeat+False)|2063699|永不终止。(注意：repeat+False创建了一个无限列表，其中每个元素都是False。)|2063700|另一方面，foldl'是尾递归和严格的。如果您知道无论如何都必须遍历整个列表(例如，对列表中的数字求和)，那么foldl'比foldr更有空间效率(也可能是时间效率)。|2063701|entityMap^0|0|C|I|J|0|0|1|C|0|0|G|1|P|5|10|5|0|0|2|5|0|0|9|C|13|5|0|5|6|1J|6|1Q|5|0^^$0|@$1|2|3|4|5|6|7|12|8|@$9|13|A|14|B|C]|$9|15|A|16|B|C]]|D|@]|E|$]]|$1|F|3|G|5|H|7|17|8|@]|D|@]|E|$I|J]]|$1|K|3|L|5|6|7|18|8|@$9|19|A|1A|B|C]]|D|@]|E|$]]|$1|M|3|N|5|H|7|1B|8|@]|D|@]|E|$I|J]]|$1|O|3|P|5|6|7|1C|8|@$9|1D|A|1E|B|C]|$9|1F|A|1G|B|C]|$9|1H|A|1I|B|C]]|D|@]|E|$]]|$1|Q|3|R|5|H|7|1J|8|@]|D|@]|E|$I|J]]|$1|S|3|T|5|6|7|1K|8|@$9|1L|A|1M|B|C]]|D|@]|E|$]]|$1|U|3|V|5|H|7|1N|8|@]|D|@]|E|$I|J]]|$1|W|3|X|5|6|7|1O|8|@$9|1P|A|1Q|B|C]|$9|1R|A|1S|B|C]]|D|@]|E|$]]|$1|Y|3|Z|5|6|7|1T|8|@$9|1U|A|1V|B|C]|$9|1W|A|1X|B|C]|$9|1Y|A|1Z|B|C]]|D|@]|E|$]]|$1|10|3|-4|5|6|7|20|8|@]|D|@]|E|$]]]|11|$]]

The recursion for <code>foldr f x ys</code> where <code>ys = [y1,y2,...,yk]</code> looks like

<pre><code>f y1 (f y2 (... (f yk x) ...))
</code></pre>

whereas the recursion for <code>foldl f x ys</code> looks like

<pre><code>f (... (f (f x y1) y2) ...) yk
</code></pre>

An important difference here is that if the result of <code>f x y</code> can be computed using only the value of <code>x</code>, then <code>foldr</code> doesn't' need to examine the entire list. For example 

<pre><code>foldr (&amp;&amp;) False (repeat False)
</code></pre>

returns <code>False</code> whereas

<pre><code>foldl (&amp;&amp;) False (repeat False)
</code></pre>

never terminates. (Note: <code>repeat False</code> creates an infinite list where every element is <code>False</code>.)

On the other hand, <code>foldl'</code> is tail recursive and strict. If you know that you'll have to traverse the whole list no matter what (e.g., summing the numbers in a list), then <code>foldl'</code> is more space- (and probably time-) efficient than <code>foldr</code>.

blocks|key|2063918|text|在99%25的使用中，foldl'比foldl更受欢迎的原因是，对于大多数用途，它可以在恒定的空间中运行。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|2063919|以函数sum+=+foldl[']+(%2B)+0为例。当使用foldl'时，将立即计算和，因此将sum应用于无限列表将永远运行，并且很可能在常量空间中运行(如果您使用的是Ints，Doubles，Floats。如果数字变得大于maxBound+::+Int，则Integers将使用多于常量空间的空间)。|2063920|有了foldl，就建立了一个thunk+(就像如何获得答案的秘诀，可以在以后评估，而不是存储答案)。这些数据块可能会占用大量空间，在这种情况下，计算表达式要比存储数据块好得多(导致堆栈溢出…并将您带到…哦，不要紧)|2063921|希望这能有所帮助。|2063922|entityMap^0|9|6|G|5|0|3|K|T|6|1B|3|2C|3|2H|6|2P|5|34|F|3L|7|0|2|5|0|0^^$0|@$1|2|3|4|5|6|7|N|8|@$9|O|A|P|B|C]|$9|Q|A|R|B|C]]|D|@]|E|$]]|$1|F|3|G|5|6|7|S|8|@$9|T|A|U|B|C]|$9|V|A|W|B|C]|$9|X|A|Y|B|C]|$9|Z|A|10|B|C]|$9|11|A|12|B|C]|$9|13|A|14|B|C]|$9|15|A|16|B|C]|$9|17|A|18|B|C]]|D|@]|E|$]]|$1|H|3|I|5|6|7|19|8|@$9|1A|A|1B|B|C]]|D|@]|E|$]]|$1|J|3|K|5|6|7|1C|8|@]|D|@]|E|$]]|$1|L|3|-4|5|6|7|1D|8|@]|D|@]|E|$]]]|M|$]]

The reason <code>foldl'</code> is preferred to <code>foldl</code> for 99% of all uses is that it can run in constant space for most uses.

Take the function <code>sum = foldl['] (+) 0</code>. When <code>foldl'</code> is used, the sum is immediately calculated, so applying <code>sum</code> to an infinite list will just run forever, and most likely in constant space (if you’re using things like <code>Int</code>s, <code>Double</code>s, <code>Float</code>s. <code>Integer</code>s will use more than constant space if the number becomes larger than <code>maxBound :: Int</code>).

With <code>foldl</code>, a thunk is built up (like a recipe of how to get the answer, which can be evaluated later, rather than storing the answer). These thunks can take up a lot of space, and in this case, it’s much better to evaluate the expression than to store the thunk (leading to a stack overflow&hellip; and leading you to&hellip; oh never mind)

Hope that helps.

blocks|key|2063959|text|顺便说一句，Ruby的inject和Clojure的reduce都是foldl+(或者foldl1，取决于您使用的版本)。通常，当一种语言中只有一种形式时，它是左文件夹，包括Python的reduce，Perl的List::Util::reduce，C%2B%2B的accumulate，C#的Aggregate，Smalltalk的inject:into:，PHP的array_reduce，Mathematica的Fold等。Common+Lisp的reduce默认使用左文件夹，但有一个右文件夹的选项。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|2063960|entityMap^0|B|6|Q|6|Y|5|17|6|2M|6|2Y|I|3L|A|3Z|9|4J|C|50|C|5P|4|67|6|0^^$0|@$1|2|3|4|5|6|7|H|8|@$9|I|A|J|B|C]|$9|K|A|L|B|C]|$9|M|A|N|B|C]|$9|O|A|P|B|C]|$9|Q|A|R|B|C]|$9|S|A|T|B|C]|$9|U|A|V|B|C]|$9|W|A|X|B|C]|$9|Y|A|Z|B|C]|$9|10|A|11|B|C]|$9|12|A|13|B|C]|$9|14|A|15|B|C]]|D|@]|E|$]]|$1|F|3|-4|5|6|7|16|8|@]|D|@]|E|$]]]|G|$]]

By the way, Ruby's <code>inject</code> and Clojure's <code>reduce</code> are <code>foldl</code> (or <code>foldl1</code>, depending on which version you use). Usually, when there is only one form in a language, it is a left fold, including Python's <code>reduce</code>, Perl's <code>List::Util::reduce</code>, C++'s <code>accumulate</code>, C#'s <code>Aggregate</code>, Smalltalk's <code>inject:into:</code>, PHP's <code>array_reduce</code>, Mathematica's <code>Fold</code>, etc. Common Lisp's <code>reduce</code> defaults to left fold but there's an option for right fold.

blocks|key|2063966|text|正如Konrad所指出的，它们的语义是不同的。它们甚至没有相同的类型：|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|2063967|ghci>+:t+foldr
foldr+::+(a+->+b+->+b)+->+b+->+[a]+->+b
ghci>+:t+foldl
foldl+::+(a+->+b+->+a)+->+a+->+[b]+->+a
ghci>+|code-block|syntax|javascript|2063968|例如，列表追加运算符(%2B%2B)可以使用foldr实现为|style|CODE|2063969|(%2B%2B)+=+flip+(foldr+(:))|2063970|而|2063971|(%2B%2B)+=+flip+(foldl+(:))|2063972|会给你一个类型错误。|2063973|entityMap|0|LINK|mutability|MUTABLE|url|https://stackoverflow.com/questions/384797/implications-of-foldr-vs-foldl-or-foldl/384802#384802^0|2|6|0|0|0|I|5|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|12|8|@]|9|@$A|13|B|14|1|15]]|C|$]]|$1|D|3|E|5|F|7|16|8|@]|9|@]|C|$G|H]]|$1|I|3|J|5|6|7|17|8|@$A|18|B|19|K|L]]|9|@]|C|$]]|$1|M|3|N|5|F|7|1A|8|@]|9|@]|C|$G|H]]|$1|O|3|P|5|6|7|1B|8|@]|9|@]|C|$]]|$1|Q|3|R|5|F|7|1C|8|@]|9|@]|C|$G|H]]|$1|S|3|T|5|6|7|1D|8|@]|9|@]|C|$]]|$1|U|3|-4|5|6|7|1E|8|@]|9|@]|C|$]]]|V|$W|$5|X|Y|Z|C|$10|11]]]]

As <a href="https://stackoverflow.com/questions/384797/implications-of-foldr-vs-foldl-or-foldl/384802#384802">Konrad</a> points out, their semantics are different. They don't even have the same type: 

<pre><code>ghci&gt; :t foldr
foldr :: (a -&gt; b -&gt; b) -&gt; b -&gt; [a] -&gt; b
ghci&gt; :t foldl
foldl :: (a -&gt; b -&gt; a) -&gt; a -&gt; [b] -&gt; a
ghci&gt; 
</code></pre>

For example, the list append operator (++) can be implemented with <code>foldr</code> as

<pre><code>(++) = flip (foldr (:))
</code></pre>

while

<pre><code>(++) = flip (foldl (:))
</code></pre>

will give you a type error.

blocks|key|2064571|text|foldr看起来像这样：|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|2064572|​|2064573|📷|atomic|2064574|2064575|foldl看起来像这样：|2064576|2064577|2064578|2064579|上下文:+Haskell维基上的Fold|2064580|entityMap|0|IMAGE|mutability|IMMUTABLE|imageUrl|https://ask.qcloudimg.com/http-save/yehe-900000/3ca5362a6efdf1cd08433740993b61c3.png|imageAlt|1|https://ask.qcloudimg.com/http-save/yehe-900000/feee731f2e5d2ca0e135de0ed0cd0f55.png|2|LINK|MUTABLE|url|http://www.haskell.org/haskellwiki/Fold^0|0|5|0|0|0|1|0|0|0|0|5|0|0|0|1|1|0|0|G|4|2|0^^$0|@$1|2|3|4|5|6|7|18|8|@$9|19|A|1A|B|C]]|D|@]|E|$]]|$1|F|3|G|5|6|7|1B|8|@]|D|@]|E|$]]|$1|H|3|I|5|J|7|1C|8|@]|D|@$9|1D|A|1E|1|1F]]|E|$]]|$1|K|3|G|5|6|7|1G|8|@]|D|@]|E|$]]|$1|L|3|M|5|6|7|1H|8|@$9|1I|A|1J|B|C]]|D|@]|E|$]]|$1|N|3|G|5|6|7|1K|8|@]|D|@]|E|$]]|$1|O|3|I|5|J|7|1L|8|@]|D|@$9|1M|A|1N|1|1O]]|E|$]]|$1|P|3|G|5|6|7|1P|8|@]|D|@]|E|$]]|$1|Q|3|R|5|6|7|1Q|8|@]|D|@$9|1R|A|1S|1|1T]]|E|$]]|$1|S|3|-4|5|6|7|1U|8|@]|D|@]|E|$]]]|T|$U|$5|V|W|X|E|$Y|Z|10|-4]]|11|$5|V|W|X|E|$Y|12|10|-4]]|13|$5|14|W|15|E|$16|17]]]]

<code>foldr</code> looks like this:

<img src="https://imgur.com/XHakM.png" alt="Right-fold visualization">

<code>foldl</code> looks like this:

<img src="https://imgur.com/oqckX.png" alt="Left-fold visualization">

Context: <a href="http://www.haskell.org/haskellwiki/Fold" rel="noreferrer">Fold</a> on the Haskell wiki

Firstly, Real World Haskell, which I am reading, says to never use <code>foldl</code> and instead use <code>foldl'</code>. So I trust it. 

But I'm hazy on when to use <code>foldr</code> vs. <code>foldl'</code>. Though I can see the structure of how they work differently laid out in front of me, I'm too stupid to understand when "which is better." I guess it seems to me like it shouldn't really matter which is used, as they both produce the same answer (don't they?). In fact, my previous experience with this construct is from Ruby's <code>inject</code> and Clojure's <code>reduce</code>, which don't seem to have "left" and "right" versions. (Side question: which version do they use?) 

Any insight that can help a smarts-challenged sort like me would be much appreciated!

Implications of foldr vs. foldl (or foldl')

Python

Perl

首先，我正在阅读的Real World Haskell建议永远不要使用foldl，而要使用foldl'。所以我相信它。但我不清楚什么时候使用foldr，什么时候使用foldl'。虽然我可以看到它们的不同工作结构摆在我面前，但我太愚蠢了，不知道什么时候“哪个更好”。我猜在我看来，使用哪一个并不重要，因为它们都产生了相同的...

问foldr与foldl (或foldl')的含义
EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问foldr与foldl (或foldl')的含义EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问foldr与foldl (或foldl')的含义
EN