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, so we don't really have to worry too much about it. For simplicity, then, let's pick one in particular:

f :: Ord x => Set x -> x -> Set x
f a x = insert x a

While we're at it, let's give a name to foldl f: stuff. So

stuff :: Ord x => Set x -> [x] -> Set x
stuff a [] = a
stuff a (x:xs) = stuff (f a x) xs

takes all the elements of the list it's given and stuffs them into the Set it's given.

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 stuff a xs as (stuff a) xs—that is, to see stuff 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 stuff.

stuffy :: Ord x => [x] -> Set x -> Set x
stuffy [] a = a
stuffy (x : xs) a = stuffy xs (f a x)

So now we see that stuffy 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 stuffy just a little:

stuffy :: Ord x => [x] -> Set x -> Set x
stuffy a [] = \a -> a
stuffy (x : xs) = \a -> stuffy xs (f a x)

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

stuffy :: Ord x => [x] -> Set x -> Set x
stuffy [] = (\a -> a)
stuffy (x : xs) = \a -> (stuffy 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 stuffy fits the foldr pattern:

stuffy :: Ord x => [x] -> Set x -> Set x
stuffy ys = foldr whatsit (\a -> a) ys
  where
    whatsit x r = \a -> r (f a x)

Substituting this in,

stuffy :: Ord x => [x] -> Set x -> Set x
stuffy list a = (foldr whatsit (\a -> a) list) a
  where
    whatsit x r = \a -> r (f a x)

And that's just about it! We wanted stuff, however, not stuffy, so let's swap the argument order again:

stuff :: Ord x => Set a -> [x] -> Set x
stuff a list = (foldr whatsit (\a -> a) list) a
  where
    whatsit x r = \a -> r (f a x)

Now since we do want to be able to use general foldl forms, we should gneralize it again:

<haskell> foldl :: (a -> x -> r) -> a -> [x] -> r foldl f a xs = (foldr whosit (\a -> a) list) a

 where
   whosit x r = \a -> r (f a x)

</haskell.

The way to look at this final expression is that whosit takes an element of the list, a function produced by folding f into the rest of the list, and the initial value, a 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.