Haskell - foldl and foldr?

64
votes

Is difference between foldl and foldr just the direction of looping? I thought there was a difference in what they did, not just in the direction?

1
haskellfold
I'm curious what you were reading that confused you. A link might have made the question more clear. Looks like @AndrewC has a quality answer for you though. – Jamey Sharp
You'll also find a very nice answer here stackoverflow.com/questions/3082324/… – Jerome
the difference is that their argument functions have their arguments order respectively flipped: the one fit for foldl combines result with list element type; and one for foldr combines list element type with result. – Will Ness
@WillNess a difference is that the accumulating functions have flipped types. foldr f doesn't have to be foldl (flip f) – AndrewC
@AndrewC thank you, that's what I meant, yes. – Will Ness

1 Answers

126
votes

There's a difference if your function isn't associative (i.e. it matters which way you bracket expressions) so for example,
foldr (-) 0 [1..10] = -5 but foldl (-) 0 [1..10] = -55.
This is because the former is equal to 1-(2-(3-(4-(5-(6-(7-(8-(9-(10 - 0))))))))), whereas the latter is (((((((((0-1)-2)-3)-4)-5)-6)-7)-8)-9)-10.

Whereas because (+) is associative (doesn't matter what order you add subexpressions),
foldr (+) 0 [1..10] = 55 and foldl (+) 0 [1..10] = 55. (++) is another associative operation because xs ++ (ys ++ zs) gives the same answer as (xs ++ ys) ++ zs (although the first one is faster - don't use foldl (++)).

Some functions only work one way:
foldr (:) :: [a] -> [a] -> [a] but foldl (:) is nonsense.

Have a look at Cale Gibbard's diagrams (from the wikipedia article); you can see f getting called with genuinely different pairs of data:
foldrfoldl

Another difference is that because it matches the structure of the list, foldr is often more efficient for lazy evaluation, so can be used with an infinite list as long as f is non-strict in its second argument (like (:) or (++)). foldl is only rarely the better choice. If you're using foldl it's usually worth using foldl' because it's strict and stops you building up a long list of intermediate results. (More on this topic in the answers to this question.)