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”

  1. You must have read my mind! I was wondering about this a few hours ago, and then your post shows up in my RSS feed. Thank you for a very well-written explanation.

  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

Leave a Reply

(required)

Staypressed theme by Themocracy