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 a [] = a
    go a (x : xs) = go (f a 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 a xs as (go a) 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 [] a = a
    go2 (x : xs) a = go2 xs (f a 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:

foldl :: (a -> x -> r) -> a -> [x] -> r
foldl f a list = go2 list a
  where
    go2 [] = \a -> a
    go2 (x : xs) = \a -> go2 xs (f a 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 [] = (\a -> a)
    go2 (x : xs) = \a -> (go2 xs) (f a x)

This isn't an academic paper, so we won't mention Graham Hutton's "Tuturial on the Universality and Expressiveness of Fold", but go2 fits the foldr pattern:

go2 ys = foldr whatsit (\a -> a) ys
  where
    whatsit x r = \a -> r (f a x)

Substituting this in,

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

And that's all she wrote! One way to look at this final expression is that whatsit takes an element of the list, a function produced by folding over the rest of the list, and the value of an accumulator. It applies f to the accumulator it's given and the list element, and passes the result forward to the function it got.