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)
go2 (x : xs) = \acc -> (go2 xs) (f acc 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 (\acc -> acc) ys
where
whatsit x r = \acc -> r (f acc x)
Substituting this in,
foldl f a list = (foldr whatsit (\acc -> acc) list) a
where
whatsit x r = \acc -> r (f acc 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.