71

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?

duplode
  • 33,731
  • 7
  • 79
  • 150
Lethi
  • 1,167
  • 1
  • 10
  • 16
  • 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 Nov 07 '12 at 23:51
  • You'll also find a very nice answer here http://stackoverflow.com/questions/3082324/foldl-versus-foldr-behavior-with-infinite-lists – Jerome Nov 08 '12 at 01:45
  • 3
    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 Nov 12 '12 at 16:43
  • @WillNess __a__ difference is that the accumulating functions have flipped types. `foldr f` doesn't have to be `foldl (flip f)` – AndrewC Nov 13 '12 at 21:42
  • @AndrewC thank you, that's what I meant, yes. – Will Ness Nov 14 '12 at 06:51

1 Answers1

136

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.)

Enlico
  • 23,259
  • 6
  • 48
  • 102
AndrewC
  • 32,300
  • 7
  • 79
  • 115
  • 14
    Another difference, related to the last point, is that `foldl` can never return if given an infinite list, whereas `foldr` will if given a function that is non-strict in its second argument (such as `(:)` or `const`, ...) – luqui Nov 08 '12 at 02:41
  • 1
    `foldl` has argument order flipped compared to `foldr`. So all functions work both ways: `foldl (flip (:))` still typechecks. – nponeccop Nov 09 '12 at 10:22
  • @nponeccop My point is that some functions `f` only work in one of `foldl` or `foldr`. `flip (:)` is not the same function as `(:)`! Not all functions work in both. – AndrewC Nov 09 '12 at 12:45
  • 1
    some sidenotes: [1] another way to talk about it is to mention type *asymmetry* of `(:) :: a->[a]->[a]` or `flip (:) :: [a]->a->[a]` which dictates the only possible order of combination. [2] `scanl` is somewhere "between" foldl and foldr, combining the "looping from the left" with possibility to stop early. – Will Ness Nov 12 '12 at 17:10
  • 3
    There's a semantic not just syntactic difference, though: `foldr (:) "!" "Hello"` is `"Hello!"` whereas `foldl (flip (:)) "!" "Hello"` is `"olleH!"` – AndrewC Nov 13 '12 at 21:38
  • There's one thing I don't understand. `foldl (-) 0 [1..4]` returns `-10`, but your example `((1-2)-3)-4` equals to `8`? – TheLeonKing Nov 11 '15 at 14:06
  • They're a different example, just to show that subtraction isn't associative (i.e. it matters where the brackets are, unlike in addition). I've edited it to be more clearly not the same. – AndrewC May 23 '16 at 19:37
  • 1
    It's hard to see how can `foldr` even work with an infinite list as it seems the first application of function `f` is with z and the last item of the list. It will first need to traverse all the way to the last item which is infinite time in an infinite list. On the other hand `foldl`'s first application of the function `f` is with z and the first item of the list. It can already start applying the function and we can traverse down the list lazily. – laiboonh Oct 27 '17 at 15:21
  • 1
    @laiboonh The "first" application mathematically, maybe, but if the combining function is lazy in its second argument (as `(:)` is), it could produce results using its first argument and then use _part_ of its (lazily produced) second argument to produce more results. – AndrewC Oct 27 '17 at 16:17
  • @laiboonh I found a link for this topic. https://stackoverflow.com/questions/3082324/foldl-versus-foldr-behavior-with-infinite-lists – dhu Feb 23 '18 at 16:57
  • @laiboonh ``foldr g z (x:xs) = x `g` foldr g z xs`` so `g` gets to work immediately on the first item in the list. only if `g` demands the value of its second argument will the call to `foldr g z xs` go into the rest of the input list (`xs`). whereas ``foldl g z (x:xs) = foldl g (z `g` x) xs = ... = (... (((z`g`x1)`g`x2)`g`x3)`g` ... )`g` xn`` and before `g` gets t work on the _last_ item `xn` first, this whole expression needs to be built, which means the whole input list needs to be traversed for that. then, if `g` does _not_ demand the value of its first argument, only `xn`'s value will be – Will Ness Jan 27 '22 at 16:12
  • @laiboonh demanded from the input list, but none of the preceding elements values will be demanded. thus, `foldl g z [1..]` goes into infinite loop building that expression. also `foldl (\a b -> b) undefined (undefined++[1])` causes an error, but `foldl (\a b -> b) undefined [undefined,1] == 1`. whereas `foldr (\a b -> a) undefined (1 : undefined) == 1` but `foldr (\a b -> b) undefined (1 : undefined)` causes an error. so the outcome is not determined just by the use of `foldr` or `foldl`, but mainly by the properties of the function `g` used there. – Will Ness Jan 27 '22 at 16:17
  • This is one of the best answers i have seen on folds.. Thanks – Seby Sep 22 '22 at 07:57