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