Implications of foldr vs. foldl (or foldl')
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 fx ys where ys = [y1,y2,...,yk] looks like
f y1 (f y2 (... (f yk x) ...))
whereas the recursion for foldl fx ys looks like
f (... (f (f x y1) y2) ...) yk
An important difference here is that if the result of fxy 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 (eg, summing the numbers in a list), then foldl' is more space- (and probably time-) efficient than foldr .
foldr looks like this:
foldl looks like this:
Context: Fold on the Haskell wiki
Their semantics differ so you can't just interchange foldl and foldr . 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.
Haskell.org has an interesting article on the subject.
链接地址: http://www.djcxy.com/p/80722.html上一篇: foldl与foldr行为与无限列表