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