Implications of foldr vs. foldl (or foldl')
Solution 1
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
.
Solution 2
foldr
looks like this:
foldl
looks like this:
Context: Fold on the Haskell wiki
Solution 3
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.
Solution 4
Shortly, foldr
is better when the accumulator function is lazy on its second argument. Read more at Haskell wiki's Stack Overflow (pun intended).
Solution 5
The reason foldl'
is preferred to foldl
for 99% of all uses is that it can run in constant space for most uses.
Take the function sum = foldl['] (+) 0
. When foldl'
is used, the sum is immediately calculated, so applying sum
to an infinite list will just run forever, and most likely in constant space (if you’re using things like Int
s, Double
s, Float
s. Integer
s will use more than constant space if the number becomes larger than maxBound :: Int
).
With foldl
, 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… and leading you to… oh never mind)
Hope that helps.
Related videos on Youtube
J Cooper
Aspiring polyglot. Enjoys classical music and long walks on the beach.
Updated on July 20, 2020Comments
-
J Cooper almost 4 years
Firstly, Real World Haskell, which I am reading, says to never use
foldl
and instead usefoldl'
. 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'sinject
and Clojure'sreduce
, 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!
-
titaniumdecoy almost 13 yearsThis comment is helpful but I would appreciate sources.
-
Sawyer over 12 yearsIn foldr it evaluates as f y1 thunk, so it returns False, however in foldl, f can't know either of it's parameter.In Haskell, no matter whether it's tail recursion or not, it both can cause thunks overflow, i.e. thunk is too big. foldl' can reduce thunk immediately along the execution.
-
Lii over 10 yearsTo avoid confusion, note that the parentheses do not show the actual order of evaluation. Since Haskell is lazy the outermost expressions will be evaluated first.
-
Lqueryvg over 9 yearsGreate answer. I would like to add that if you want a fold which can stop part way through a list, you have to use foldr; unless I'm mistaken, left folds can't be stopped. (You hint this when you say "if you know ... you'll ... traverse the whole list"). Also, the typo "using only on the value" should be changed to "using only the value". I.e. remove the word "on". (Stackoverflow wouldn't let me submit a 2 char change!).
-
Will Ness over 8 years@Lqueryvg two ways to stop left folds: 1. code it with a right fold (see
fodlWhile
) ; 2. convert it into a left scan (scanl
) and stop that withlast . takeWhile p
or similar. Uh, and 3. usemapAccumL
. :) -
MicroVirus about 8 yearsCommon Lisp's
reduce
isn't lazy, so it'sfoldl'
and much of the considerations here don't apply. -
dfeuer about 8 yearsThe big exception is if the function passed to
foldl
does nothing but apply constructors to one or more of its arguments. -
Desty about 7 years@WillNess I just noticed that
scanl
andscanl'
are fine with infinite lists, butfoldl
/foldl'
both enter an infinite loop. Why doesn'tscanl
have the same problem? -
Will Ness about 7 years@Desty because it produces new part of its overall result on each step -- unlike
foldl
, which collects its overall result and produces it only after all the work is finished and there are no more steps to perform. So e.g.foldl (flip (:)) [] [1..3] == [3,2,1]
, soscanl (flip(:)) [] [1..] = [[],[1],[2,1],[3,2,1],...]
... IOW,foldl f z xs = last (scanl f z xs)
and infinite lists have no last element (which, in the example above, would itself be an infinite list, from INF down to 1). -
Evi1M4chine over 6 yearsTheir semantics only differ in a trivial way, that is meaningless in practice: The order of arguments of the used function. So interface-wise they still count as exchangeable. The real difference is, it seems, only the optimization/implementation.
-
Evi1M4chine over 6 yearsIs there a general pattern to when
foldl
is actually the best choice? (Like infinite lists whenfoldr
is the wrong choice, optimization-wise.?) -
Evi1M4chine over 6 yearsTheir type is the same, just switched around, which is irrelevant. Their interface and results are the same, except for the nasty P/NP problem (read: infinite lists). ;) The optimization due to the implementation is the only difference in practice, as far as I can tell.
-
Evi1M4chine over 6 yearsI think you mean
foldl'
, as they are strict languages, no? Otherwise, won’t that mean all those versions cause stack overflows likefoldl
does? -
Konrad Rudolph over 6 years@Evi1M4chine None of the differences are trivial. On the contrary, they are substantial (and, yes, meaningful in practice). In fact, if I were to write this answer today it would emphasise this difference even more.
-
krapht about 6 years@Evi1M4chine This is incorrect, look at this example:
foldl subtract 0 [1, 2, 3, 4]
evaluates to-10
, whilefoldr subtract 0 [1, 2, 3, 4]
evaluates to-2
.foldl
is actually0 - 1 - 2 - 3 - 4
whilefoldr
is4 - 3 - 2 - 1 - 0
. -
pianoJames over 5 years@krapht,
foldr (-) 0 [1, 2, 3, 4]
is-2
andfoldl (-) 0 [1, 2, 3, 4]
is-10
. On the other hand,subtract
is backwards from what you might expect (subtract 10 14
is4
), sofoldr subtract 0 [1, 2, 3, 4]
is-10
andfoldl subtract 0 [1, 2, 3, 4]
is2
(positive). -
KevinOrr about 4 years@Evi1M4chine not sure what you mean by
foldr
being the wrong choice for infinite lists. In fact, you shouldn't usefoldl
orfoldl'
for infinite lists. See the Haskell wiki on stack overflows -
guido about 3 yearsMy preferred way to distinguish between the two is like this:
foldl
stacks parentheses on the left,foldr
stacks parentheses on the right:(((0+1)+2)+3)
versus(1+(2+(3+0)))