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