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

问题描述

首先，我正在阅读的 Real World Haskell 说永远不要使用 foldl，而是使用 foldl'.所以我相信它.

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

但我不清楚什么时候使用 foldr 和 foldl'.虽然我可以在我面前看到它们如何不同工作的结构，但我太愚蠢了，无法理解什么时候哪个更好".我想在我看来，使用哪个并不重要，因为它们都产生相同的答案(不是吗?).事实上，我之前使用这个构造的经验来自 Ruby 的 inject 和 Clojure 的 reduce，它们似乎没有左"和右"版本.(附带问题:他们使用哪个版本?)

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!

推荐答案

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

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

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

而 foldl f x ys 的递归看起来像

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

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

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)

返回 False 而

foldl (&&) False (repeat False)

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

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

另一方面，foldl' 是尾递归且严格的.如果您知道无论如何都必须遍历整个列表(例如，对列表中的数字求和)，那么 foldl' 比 foldl' 更节省空间(可能还有时间)代码>文件夹.

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屋！