Foldl as foldr alternative

This page explains how foldl can be written using foldr. Yes, there is already such a page! This one explains it differently.

The usual definition of foldl looks like this:

foldl :: (a -> x -> r) -> a -> [x] -> r
foldl f a [] = a
foldl f a (x : xs) = foldl f (f a x) xs

Now the f never changes in the recursion. It turns out things will be simpler later if we pull it out:

foldl :: (a -> x -> r) -> a -> [x] -> r
foldl f a list = go a list
  where
    go acc [] = acc
    go acc (x : xs) = go (f acc x) xs

---

For some reason (maybe we're crazy; maybe we want to do weird things with fusion; who knows?) we want to write this using foldr. Haskell programmers like curry, so it's natural to see go acc xs as (go acc) xs—that is, to see go a as a function that takes a list and returns the result of folding f into the list starting with an accumulator value of a. This perspective, however, is the wrong one for what we're trying to do here. So let's change the order of the arguments of the helper:

foldl :: (a -> x -> r) -> a -> [x] -> r
foldl f a list = go2 list a
  where
    go2 [] acc = acc
    go2 (x : xs) acc = go2 xs (f acc x)

So now we see that go2 xs is a function that takes an accumulator and uses it as the initial value to fold f into xs. With this shift of perspective, we can rewrite go2 just a little, shifting its second argument into an explicit lambda:

foldl :: (a -> x -> r) -> a -> [x] -> r
foldl f a list = go2 list a
  where
    go2 [] = \acc -> acc
    go2 (x : xs) = \acc -> go2 xs (f acc x)

Believe it or not, we're almost done! How is that? Let's parenthesize a bit for emphasis:

foldl f a list = go2 list a
  where
    go2 [] = (\acc -> acc)                      -- nil case
    go2 (x : xs) = \acc -> (go2 xs) (f acc x)   -- construct x (go2 xs)

This isn't an academic paper, so we won't mention Graham Hutton's "Tutorial on the Universality and Expressiveness of Fold", but go2 fits the foldr pattern, constructing its result in non-nil case from the list's head element (x) and the recursive result for its tail (go2 xs):

go2 list = foldr construct (\acc -> acc) list
  where
    construct x r = \acc -> r (f acc x)

Substituting this in,

foldl f a list = (foldr construct (\acc -> acc) list) a
  where
    construct x r = \acc -> r (f acc x)

And that's all she wrote! One way to look at this final expression is that construct takes an element x of the list, a function r produced by folding over the rest of the list, and the value of an accumulator, acc, "from the left". It applies f to the accumulator and the list element, and passes the result forward to the function it got "on the right".

Because r is the same function as constructed by the construct here, calling this for a list [x,y,...,z] scans through the whole list creating a nested lambda which is then applied to the initial value of the accumulator,

(\acc-> 
    (\acc-> 
        (... (\acc-> (\acc -> acc)
                      (f acc z)) ...)
        (f acc y))
    (f acc x)) a

which, when evaluated, creates the chain of evaluations as in

(\acc -> acc) (f (... (f (f a x) y) ...) z)

which is just what the normal foldl would do.

---

Now, the construct function could be more clever, and inspect the current element, in order to decide whether to process the list further or not. Thus, this new variant of foldl would be able to stop early.