# 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) -- nil case
go2 (x : xs) = \acc -> (go2 xs) (f acc x) -- construct x (go2 xs)
```

This isn't an academic paper, so we won't mention Graham Hutton's "Tutorial on the Universality and Expressiveness of Fold", but `go2`

fits the `foldr`

pattern, constructing its result in non-nil case from the list's head element (`x`

) and the recursive result for its tail (`go2 xs`

):

```
go2 list = foldr construct (\acc -> acc) list
where
construct x r = \acc -> r (f acc x)
```

Substituting this in,

```
foldl f a list = (foldr construct (\acc -> acc) list) a
where
construct x r = \acc -> r (f acc x)
```

And that's all she wrote! One way to look at this final expression is that `construct`

takes an element `x`

of the list, a function `r`

produced by folding over the rest of the list, and the value of an accumulator, `acc`

, "from the left". It applies `f`

to the accumulator and the list element, and passes the result forward to the function it got "on the right".

Because `r`

is the same function as constructed by the `construct`

here, calling this e.g. for a list `[x,y,...,z]`

scans through the whole list as-if evaluating a nested lambda applied to the initial value of the accumulator,

```
(\acc->
(\acc->
(... (\acc-> (\acc -> acc)
(f acc z)) ...)
(f acc y))
(f acc x)) a
```

which creates the chain of evaluations as in

```
(\acc -> acc) (f (... (f (f a x) y) ...) z)
```

which is just what the normal `foldl`

would do.

The `construct`

function could even be made more clever, and inspect the current element in order to decide whether to *process* the list *further* or not. Thus, such a variant of `foldl`

will be able to stop early, and thus process even infinite lists:

```
foldlWhile t f a list = foldr cons (\acc -> acc) list a
where
cons x r = \acc -> if t x then r (f acc x) else acc
```

And if we want our `foldl`

to decide whether to process or *skip* the current element, then it's

```
foldlIf t f a list = foldr cons (\acc -> acc) list a
where
cons x r = \acc -> if t x then r (f acc x) else r acc
```

(Just for comparison, skipping `foldr`

is of course, trivial:)

```
foldrIf t f a list = foldr cons a list
where
cons x r | t x = f x r
| otherwise = r
```

Another variation is (a more strict and more general)

```
foldl'Breaking break reduced reducer acc list =
foldr cons (\acc -> acc) list acc
where
cons x r acc | break acc x = reduced acc x
| otherwise = r $! reducer acc x
```