Differences between `foldl` and `foldr`

31 points by eatonphil

ryan-duve

TIL what a thunk is.

The article starts with:

To start, you have to understand that foldl and foldr are not folds “from the left” and “from the right.” Both foldl and foldr traverse the structure in the same order, which in the case of lists means left to right. The difference is the fold’s associativity.

but then goes on to explain that the list is processed exactly as if the right two items are processed first, then continuing to proceed right-to-left. The whole thing seems to me like an explanation of how the internal workings of lazy vs eager implementations affect performance, but I can't distinguish the final result from

foldl and foldr fold “from the left” and “from the right exactly as you expect. That may be bad performancewise.

chriswarbo
Keep in mind that the [a, b, c, d] syntax is sugar for the value a : (b : (c : (d : []))), hence anything processing such a value must go left-to-right. For example, if we use pattern-matching, like:
```
case myList of
  [] -> myNilCase
  x:xs -> myConsCase
```
Then the above value would hit the x:xs pattern, where x gets bound to a and xs gets bound to b : (c : (d : [])) (AKA [b, c, d]).

For something to go right-to-left, i.e. processing d before it processes a, it would first have to traverse through the list (e.g. using pattern-matching like above) in order to find those values that are buried under the : ("cons") constructors; and that traversal would be left-to-right! (Indeed, it would look like foldr with the function's arguments flipped).
- gignico
  
  I think the point is whether the actual work is done before the recursion on the "head" or after on the "tail". If the main work is done after the recursion, on its return value, you have to accumulate thunks and then unroll them after you reached the end of the list, and they will be effectively processed in reverse order. So it is still true that foldr goes from right to left somehow. At least this is how I get it.
nathan

I've seen a few of Alexis' talks over the years and she's a great science communicator; hope she keeps writing on the Haskell blog!
nil

I believe one of the great strengths of lazily-evaluated languages is that they allow elegant implementations of certain algorithms. I also believe one of their great weaknesses is that they require one to think about evaluation strategies in places they otherwise wouldn't need to, such as with foldl and foldl'. In a functional language with immutability like Haskell, this can often offset the reduction in incidental complexity that comes with eliminating/encapsulating mutable state. However, it is unfortunately necessary in order to permit a style of programming that complements said immutability.