## Why foldr works for infinite lists and foldl doesn’t

About two months ago I wrote a post about expressing `foldl` in terms of `foldr`. Back then I left one question open – why does `foldr` work for infinite lists, while `foldl` doesn’t? I finally found some time sit down and find the answer.

First of all the fact that `foldl` doesn’t work for infinite lists, while `foldr` does, was counter-intuitive for me. I thought that since `foldl` consumes the list from the beginning it should be able to stop at some point and return the result. On the other hand `foldr` was explained to me as consuming a list from the right, that is from the end. Since infinite lists have no end it seemed to me that `foldr` shouldn’t be able to handle infinite lists.

Here are the definitions of folds from Haskell 2010 Language Report:

```foldl :: (a -> b -> a) -> a -> [b] -> a foldl _ z []     = z foldl f z (x:xs) = foldl f (f z x) xs```
```foldr :: (a -> b -> b) -> b -> [a] -> b foldr _ z [] = z foldr f z (x:xs) = f x (foldr f z xs)```

These two definitions supported my incorrect intuition. After all they show clearly that `foldl` processes the first argument of a list immediately, while `foldr` needs to process whole list with `foldr` before it can pass the result to `f`. Or at least I thought that they show this.

As I already said all the above intuitions are wrong. My mistake became clear to me when I explicitly wrote how recursion looks for each fold. For `foldl` the recursion is:

`f (... (f ( f (f z x1) x2) x3) ...) xn`

For `foldr` recursion looks like this:

`f x1 (f x2 (f x3 (...(f xn z) ...)))`

Now you can see that for `foldl` you need to get to the end of the list to make the most outer call. In case of `foldr` you need the first element of the list and the result of processing the rest of the list with `foldr`. Unless you can determine the value of `f` without the need for its second parameter! This is in fact the case for some operators, logical conjunction for example – if first parameter is False then we can conclude that the whole expression is False, without the need to evaluate the second argument. Therefore `foldr` will work for infinite lists if the accumulating function is lazy in its second argument. One might ask if `foldl` will work for infinite lists if the accumulating function is lazy in its first argument. The answer is no – you still need the last element of a list to calculate the value of first call and there is no last element for infinite lists.

Looking at the fold definitions given earlier I made one embarrassing omission. Recursion in `foldl` is unconditional! The recursive call is being made no matter what. The only way to stop the recursion is getting to the end of a list, but for infinite lists this ain’t gonna happen. In case of `foldr` recursion is conditional – it depends on the first argument of `f`, assuming of course that `f` is lazy for its second argument. Moreover, looking at the implementation of `foldr` given above you can see that it in fact works from the left! My intuition about `foldr` was so fixed on it consuming the list from the right that I even missed this obvious fact when writing this post. Big thanks to nh2, who pointed that out in his comment. So in the end consuming a list from the right is about grouping of terms with parentheses.

As a final remark let me note that definitions of `foldl` and `foldr` in Haskell libraries are slightly different from those given in the Haskell report. GHC.Base defines `foldr` as:

```foldr :: (a -> b -> b) -> b -> [a] -> b -- foldr _ z [] = z -- foldr f z (x:xs) = f x (foldr f z xs) {-# INLINE [0] foldr #-} -- Inline only in the final stage, after the foldr/cons rule has had a chance -- Also note that we inline it when it has *two* parameters, which are the -- ones we are keen about specialising! foldr k z = go where go [] = z go (y:ys) = y `k` go ys```

While Data.List contains following definition of `foldl`:

```foldl :: (a -> b -> a) -> a -> [b] -> a foldl f z0 xs0 = lgo z0 xs0 where lgo z [] = z lgo z (x:xs) = lgo (f z x) xs```

Semantics are of course identical with folds defined in the report.

### 6 Responses to “Why foldr works for infinite lists and foldl doesn’t”

2. nh2 says:

“On the other hand foldr consumes the list from the right, that is from the end.”

I think that is basically wrong / confusing.

Both folds consume the list from the left, as you can see in its deconstruction: (x:xs). The “r” and “l” is *not* about the direction of list processing, it is about the bracketing of the terms. foldl has the innermost brackets on the left, foldr has them on the right side.

Some example: foldr (:) [] [1..5] gives [1,2,3,4,5]. There is no right-to left processing in here.

3. Jan Stolarek says:

nh2 > I must admit that a similar thought crossed my mind when I was writing my post. Just now, after reading you’re comment I realized WHY my intuition was initially wrong. It’s because books that I read conceptually explained foldr as consuming list from the right. Indeed, in a conceptual sense it can be considered correct – the initial accumulator gets applied to the farthest element from the right to create new accumulator value, which then gets applied to next unconsumed element on the right, and so on. You are however completely right that this is not how implementation works! Thanks for clearly pointing that out! I’ll update my post.

4. nh2 says:

Exactly, the l/r influences which end of the list your initial accumulator will be combined with at some point (in my foldr (:) [] [1..5] example, it is (rightMostElem:[])), but it doesn’t mean that that happens *first* (in any meaning of “first”: neither concerning the list traversal, which is left to right, nor order of evaluation of the result list).

5. Matthias Braun says:

Enlightening, thank you!

6. Matthias Braun says:

For additional explanations (it helped me to read multiple views on the issue), here is a very helpful discussion on the implications of the different folds (including the strict foldl’):

https://stackoverflow.com/questions/384797/implications-of-foldr-vs-foldl-or-foldl

Staypressed theme by Themocracy