foldr与foldl（或foldl'）的含义 [英] Implications of foldr vs. foldl (or foldl')

问题描述

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

但我对何时使用 foldr 与 foldl'。虽然我可以看到他们在我面前的工作方式不同，但我太愚蠢地无法理解何时哪个更好。我想在我看来，它应该无关紧要，因为它们都产生相同的答案（不是吗？）。事实上，我以前使用这个构造的经验来自Ruby的 inject 和Clojure的 reduce ，这似乎没有左和右版本。 （旁边的问题：他们使用哪个版本？）

任何能够帮助像我这样智能挑战的洞察力的洞察力将非常感谢！

$ b $对于 foldr fx ys 的递归，其中 ys = [y1，y2 ，...，yk] 看起来像

  f y1（f y2（...（ ）
  

而 foldl fx的递归ys 看起来像

  f（...（f（fx y1）y2）... ）yk 
  

这里的一个重要区别是，如果 fxy 可以仅使用 x 的值计算，那么 foldr 不需要检查整个列表。例如

  foldr（&& amp;）False（重复False）
  

返回 False 而



  foldl（&& amp;）False（repeat False）
  

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

另一方面， foldl'是尾递归且严格的。如果你知道你不得不遍历整个列表（例如，将列表中的数字相加），那么 foldl'是更多的空间 - （并且很可能时间效率）高于 foldr 。

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

But I'm hazy on when to use foldr vs. foldl'. 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 inject and Clojure's reduce, 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!

解决方案

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

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

whereas the recursion for foldl f x ys looks like

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

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

foldr (&&) False (repeat False)

returns False whereas

foldl (&&) False (repeat False)

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

On the other hand, foldl' 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 foldl' is more space- (and probably time-) efficient than foldr.

这篇关于foldr与foldl（或foldl'）的含义的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！