`foldl`

traverses with `State`

, `foldr`

traverses with anything`foldl`

or `foldr`

?Avi Press gave an excellent
talk at *Scale By the
Bay 2023* about difficulties using Haskell at a startup. He mentions
that even
experienced Haskellers don’t always know how to use fundamental parts
of the language. In particular,

even experienced Haskell engineers aren’t always going to know whether to

`foldl`

or`foldr`

.

In this article I’ll deduce a firm rule that allows you to make the
correct choice. I will stick to the versions of these functions that
operate on lists; their generalization to
`Foldable`

warrants a separate article. In summary, the answer is

- use
`foldl'`

, never use`foldl`

- prefer
`foldl'`

over`foldr`

whenever possible - alternatively, consider just using
`for_`

But why? Let’s see, by examining what these functions do.

We’ll work with the traditional definitions of `foldl`

and `foldr`

,
given below. The implementations in `base`

are more complicated, for
performance reasons, but the reasoning in this article applies to them too.

```
foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f z [] = z
foldl f z (a : as) = foldl f (f z a) as
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z [] = z
foldr f z (a : as) = f a (foldr f z as)
```

Ostensibly, the difference between `foldl`

and `foldr`

is the that
former “associates a binary operation to the left” and the latter
“associates a binary operation to the right”, as follows.

```
foldl (**) z [x1, x2, ..., xn] ==
...((z ** x1) ** x2) **...) ** xn
(
foldr (**) z [x1, x2, ..., xn] ==
** (x2 ** ... (xn ** z)...) x1
```

Those are indeed descriptions of the calculated results, but that
distinction is not particularly important. If we only care about the
result then it’s easy enough to convert between `foldl`

and `foldr`

,
as shown below. The important difference is *how* they calculate the
result; the conversion below does not preserve behaviour. For example,
`foldl (-) 0`

calculates a sequence of subtractions in constant
space^{1}; `foldr (flip (-)) 0`

uses *O(n)* space.

```
foldl f z == foldr (flip f) z . reverse
foldr f z == foldl (flip f) z . reverse
```

We will apply our analysis of `foldl`

to its strict counterpart,
`foldl'`

, too.

`foldl`

traverses with `State`

So what is the precise difference between how the two folds calculate
their results? Consider this: suppose we didn’t have `foldl`

, we only
had
`traverse`

for
`State`

.
Nonetheless, we could recover `foldl`

! (In fact we only need
`traverse_`

,
a weaker form of `traverse`

, and in these examples we’ll use `for_ = flip traverse_`

for syntactic convenience.) The example below shows
how. It converts a function that performs `for_`

(restricted to
`State`

) into a function that performs `foldl`

.

```
foldlFromForState ::
forall a b. [b] -> (b -> State a ()) -> State a ()) ->
(forall a b.
-> b -> a) ->
(a ->
a ->
[b]
a= flip evalState z $ do
foldlFromForState for_ f z bs $ \b -> do
for_ bs <- get
a
put (f a b) get
```

`foldl`

and `for_`

(restricted to `State`

) are equivalentAnd not only can we get `foldl`

from `for_`

(restricted to `State`

),
we can get `for_`

(restricted to `State`

) from `foldl`

. They are
equivalent! Importantly, they are equivalent in both result and
performance characteristics.

```
forStateFromFoldl ::
forall a b. (a -> b -> a) -> a -> [b] -> a) ->
(forall a b.
->
[b] -> State a ()) ->
(b State a ()
foldl bs f = do
forStateFromFoldl <- get
z foldl g z bs)
put (where
= execState (f b) a g a b
```

That is to say, having `foldl`

is equivalent to being able to
`traverse_`

in `State`

. If you have a `foldl`

in your program you may
as well have used `traverse_`

or `for_`

with `State`

(or vice versa).

The same analysis works for the strict left fold, `foldl'`

, in place
of lazy left fold, `foldl`

. To obtain `foldl'`

from `for_`

we would
have to change `foldlFromForState`

to use `put $! f a b`

in place of
`put (f a b)`

. `forStateFromFoldl'`

would be a version of `for_`

(restricted to `State`

) that forces its state after every iteration.

`foldr`

traverses with anythingHow does the behaviour of `foldr`

differ? Suppose we didn’t have
`foldr`

, we only had `for_`

(the general version). Nonetheless, we
could recover `foldr`

. The example below shows how; it converts an
`Applicative`

-polymorphic `for_`

into `foldr`

.

```
foldrFromFor ::
forall b f. Applicative f => [b] -> (b -> f ()) -> f ()) ->
(forall a b.
-> a -> a) ->
(b ->
a ->
[b]
a=
foldrFromFor for_ f z bs $ for_ bs $ \b -> mkEndoApplicative (f b) runEndoApplicative z
```

I’ve used the following convenient type definition and functions:

```
type EndoApplicative a = Const (Endo a)
mkEndoApplicative :: (a -> a) -> EndoApplicative a ()
= Const . Endo
mkEndoApplicative
runEndoApplicative :: a -> EndoApplicative a () -> a
Const (Endo f)) = f a runEndoApplicative a (
```

`foldr`

and `for_`

(the general version) are equivalentAnd not only can we get `foldr`

from `for_`

, we can get `for_`

from
`foldr`

. They are equivalent. Again, the equivalence is one not only
of result but also of performance characteristics.

```
forFromFoldr ::
forall a b. (b -> a -> a) -> a -> [b] -> a) ->
(forall b f.
Applicative f =>
->
[b] -> f ()) ->
(b
f ()foldr bs f =
forFromFoldr foldr (\b rest -> f b *> rest) (pure ()) bs
```

That is to say, having `foldr`

is equivalent to being able to
`traverse_`

. If you have a `foldr`

in your program you may as well
just have used `traverse_`

or `for_`

with an appropriate choice of
`Applicative`

(or vice versa).

What can we do with this new knowledge? Let’s look at the example of
printing all even elements of a list. We can do so using `foldr`

but
the equivalent in terms of `for_`

(choosing the `Applicative`

to be
`IO`

) is clearer. The “equivalent” in terms of `foldl`

is wrong; it
uses *O(n)* space (and completely fails on infinite lists).

```
printEvensFoldr :: [Int] -> IO ()
=
printEvensFoldr foldr
-> when (even i) (print i) *> rest)
(\i rest pure ())
(
printEvensFor :: [Int] -> IO ()
=
printEvensFor is $ \i -> when (even i) (print i)
for_ is
printEvensFoldl :: [Int] -> IO ()
=
printEvensFoldl foldl
-> when (even i) (print i) *> rest)
(\rest i pure ())
(. reverse
```

An old riddle challenges us
to write `foldl`

in terms of `foldr`

. Personally I find the riddle
impossible to solve directly and even when I know the answer I can
hardly understand it. With the code above, though, we can solve the
riddle with no further thought. We know how to turn `foldr`

into
`for_`

and `for_`

into `foldl`

, so we simply compose.

```
foldlFromFoldr ::
forall a b. (b -> a -> a) -> a -> [b] -> a) ->
(forall a b.
-> b -> a) ->
(a ->
a ->
[b]
afoldr =
foldlFromFoldr foldr) foldlFromForState (forFromFoldr
```

After purely mechanical simplification (see appendix below) this becomes

`foldr (\b rest a -> rest (f a b)) id bs z`

We didn’t need to use any brainpower to solve the riddle! The riddle
can also be solved for `foldl'`

. It ends up the same except with a
strict application:

`foldr (\b rest a -> rest $! f a b) id bs z`

`foldl'`

, `foldl`

or `foldr`

?Now we’re ready to resolve the original dilemma. We’ve seen that the
only difference in functionality between `foldl`

and `foldr`

is that
the latter can be used in a wider range of situations. In consequence
we can specify when one should be used in preference to another.

`foldl`

Firstly, regarding the choice between the two left folds, always use
the strict version `foldl'`

, not the lazy version `foldl`

. The latter
can cause space leaks when strictness analysis is off; the former
always avoids those space leaks. I’ve never seen a reason to use
`foldl`

.^{2} This advice is common knowledge in the Haskell community
and not directly the subject of this article but it seems appropriate
to reiterate it.

`foldl'`

in preference to `foldr`

Regarding the choice between left and right fold, our first thought
might have been been to take into account the ostensible distinction
that the former “associates to the left” and the latter “to the
right”. But we are no longer distracted by this mirage. We saw above
that `foldl'`

is equivalent to `for_`

restricted to (a strict use of)
`State`

, and `foldr`

is equivalent to general `for_`

, so `foldl'`

is a
special case of `foldr`

. According to the Principle of Least
Power you should use
`foldl'`

in preference to `foldr`

when you can, this is, when the
operation you want to perform is to traverse the list with a state
parameter.

`for_`

`foldr`

does not do a *different* job to `foldl'`

: it does a more
general version of the *same* job. This was not immediately clear,
however; it required careful analysis. The lack of clarity around the
behavior of folds might be an argument for avoiding them and instead
using `for_`

with an appropriate choice of `Applicative`

. Personally,
I find `for_`

much clearer than `foldr`

in many cases. The `base`

implementation
of `(!?)`

, below, is a case in point. It is a `foldr`

that simulates
a `for_`

in a composition of `StateT`

and `Either`

by handwriting the
bind (`(>>=)`

).

```
(!?) :: [a] -> Int -> Maybe a
!? n
xs | n < 0 = Nothing
| otherwise = foldr (\x r k ->
case k of
0 -> Just x
-> r (k-1)) (const Nothing) xs n _
```

I find it much clearer written as a literal `for_`

, as below (but it
can’t be, because `StateT`

isn’t in `base`

). The two implementations
should have equal performance when compiled, assuming sufficient
inlining, because `for_`

for lists in `base`

is implemented in terms
of `foldr`

.

```
!? n =
xs | n < 0 = Nothing
| otherwise =
$ do
fromEither flip evalStateT n $ do
$ \x -> do
for_ xs >>= \case
get 0 -> lift (Left (Just x))
-> put (k - 1)
k Left Nothing
fromEither :: Either a a -> a
= either id id fromEither
```

`for_`

imperative?Yes. Although I don’t know how to precisely define “imperative style”
I am confident in saying that the style of `(!?)`

defined with `foldr`

is functional and the style of `(!?)`

defined with `for_`

is
imperative. Yet they calculate exactly the same thing in exactly the
same way. In fact, I think the implementation with `for_`

is both
imperative and clearer. How can that be? Don’t functional
programmers eschew imperative style? Actually, no: I also think that
Haskell is the world’s finest imperative programming language!

What does the algorithm look like in other imperative programming
languages? Below are two implementations in Python. Each shows the
weakness of Python’s support for imperative programming compared to
Haskell. In the first example the scopes of `k`

, `ret`

and `x`

are
limited to no less than the rest of the function, and the `break`

is
implicitly scoped to the closest enclosing `for`

– you don’t get a
choice about that. By contrast, the corresponding Haskell variables
are scoped to their precise range of use, and the `break`

equivalent
is scoped precisely to its enclosing handler, `fromEither`

. The scope
is maintained even across function call boundaries so you can refactor
and abstract. The second Python example is no better; it just trades
a too-large scope of `ret`

for an abstraction-resistant scope of early
`return`

.

I find imperative style programming in Haskell clear to understand and easy to reason about exactly because Haskell’s type system and expression-based nature allows fine-grained effect tracking and precise control of the scopes of values and effects.

Python example avoiding early return:

```
def lookup(xs, n):
if n < 0: return None
= n
k = None
ret for x in xs:
if k == 0:
= x
ret break
-= 1
k
return ret
```

Python example with early return:

```
def lookup(xs, n):
if n < 0: return None
= n
k for x in xs:
if k == 0:
return x
-= 1
k
return None
```

By carefully analysing the behaviour of three Haskell folds on lists
we were able to determine when we should use each. We even discovered
that “imperative style” programming in Haskell can be clearer than
“functional style”. In summary, never use `foldl`

, prefer `foldl'`

to
`foldr`

where you can, or maybe just forget them all and use `for_`

instead.

`Monoid`

sThis article is the culmination of an idea I wrote about years ago:
*What is foldr made
of?*.
Brent Yorgey wrote a follow-up,

`foldr`

is made of
monoids`foldr`

being “made of
monoids” is equivalent to it being “made of applicatives whose result
type we ignore”, because when you have an applicative whose result
type you ignore, that’s equivalent to having a monoid.There is also a *specific* `Applicative`

that corresponds directly to
any given `Monoid`

`m`

, that is, `Const m`

, and my earlier blog post
showed that there is a specific `Moniod`

that `foldr`

is “made of”:
`Endo a`

; that’s why we ended up using `Const`

and `Endo`

to define
`foldrFromFor`

. Instead of “`foldr`

traverses with anything” we could
have said “`foldr`

traverses with `Const (Endo _)`

” (but that’s much
less catchy). However, it is worth observing that the following
characterizations are also valid:

- “
`foldl`

`foldMap`

s with`Dual (Endo _)`

” - “
`foldr`

`foldMap`

s with any`Monoid`

” - “
`foldl'`

`foldMap`

s with`StrictEndo _`

” - “
`foldr`

`foldMap`

s with`Endo _`

”

(where `StrictEndo`

is a strict version of `Endo`

, which doesn’t seem
to exist anywhere in the Haskell
ecosystem).
The lens library takes advantage of these correspondences in its
definitions of
`foldlOf'`

,
`foldlOf`

and
`foldrOf`

(although it uses `Endo (Endo _)`

instead of `StrictEndo _`

).

In any case, the slogan “`foldl`

traverses with `State`

, `foldr`

traverses with anything” seems the most catchy and the easiest to use
as a guide to practice.

Alexis King has a post from 2019 explaining the difference between
`foldl`

and
`foldr`

.
She agrees that one should never use `foldl`

. Regarding the
distinction between `foldl'`

and `foldr`

she writes

When the accumulation function is strict, use foldl’ to consume the list in constant space, since the whole list is going to have to be traversed, anyway. When the accumulation function is lazy in its second argument, use foldr.

Those rules of thumb are hard to apply because they presuppose that
you already have an (“accumulation”) function (which is also a
misnomer: in the case of foldr it doesn’t accumulate). That is, it’s a
rule that you can use if you start with a function, to determine which
fold to use with that function. By contrast, this article presents a
rule that you can use if you start with a problem, to determine which
fold can solve your problem. If your problem is “traverse with (only)
a state”-shaped then the answer is `foldl'`

; if the problem is
“traverse with anything else”-shaped then the answer is `foldr`

(or in
either case you could just use `for_`

).

Yao Li et al. address the choice of folds in Reasoning about the Garden of Forking Paths from the point of view of laziness and demand analysis.

`foldM`

There is corresponding characterization of `foldM`

: “`foldM`

traverses
with `StateT`

”, as demonstrated by the following, which is a minor
adjustment to the `foldl`

equivalents.

```
foldMFromForStateT ::
forall a b m.
( Monad m =>
->
[b] -> StateT a m ()) ->
(b StateT a m ()
->
) forall a b m.
Monad m =>
-> b -> m a) ->
(a ->
a ->
[b]
m a= flip evalStateT z $ do
foldMFromForStateT for_ f z bs $ \b -> do
for_ bs <- get
a =<< lift (f a b)
put
get
forStateTFromFoldM ::
forall a b m.
( Monad m =>
-> b -> m a) ->
(a ->
a ->
[b]
m a->
) forall a b m.
Monad m =>
->
[b] -> StateT a m ()) ->
(b StateT a m ()
= do
forStateTFromFoldM foldM bs f <- get
z =<< lift (foldM g z bs)
put where
= execStateT (f b) a g a b
```

`(!?)`

written that way?It would be even clearer to write `(!?)`

as below. Why not just do
that instead, instead of considering `foldr`

and `for_`

? Because when
written in terms of `foldr`

GHC can apply short cut
fusion,
a rewrite rule that leads to an optimization.

```
0 !? (x:_) = Just x
!? [] = Nothing
_ !? (_:xs) = (n-1) !? xs n
```

Thanks to tobz619 for raising this question and suggesting the alternative implementation.

`traverse`

”There’s a running joke in the Haskell world that “it’s always
`traverse`

”, that is, many complicated transformations can be boiled
down to a use of `traverse`

. This article sheds more light on that
phenomenon; `foldl`

, `foldl'`

, `foldr`

and `foldM`

are just different
flavours of `traverse_`

.

`Foldable`

This article only discusses the relationship between `foldl`

and
`foldr`

as functions on lists, not as functions in the `Foldable`

class; that can of worms deserves an article of its own. However, the
slogan “`foldl`

traverses with `State`

, `foldr`

traverses with
anything” can be seen as specifying a putative *law* for how the
`Foldable`

versions of these functions should behave. Determining
whether that law holds in practice, and role of the mysterious
`foldr'`

, requires further analysis.

He we do the calculation for `foldl`

. The calculation for `foldl'`

is
almost identical. Starting from the original definition of
`foldlFromFoldr`

, after inlining `foldlFromForState`

and
`forFromFoldr`

, we get

```
foldlFromFoldr ::
forall a b. (b -> a -> a) -> a -> [b] -> a) ->
(forall a b.
-> b -> a) ->
(a ->
a ->
[b]
afoldr f' z bs' =
foldlFromFoldr flip evalState z $ do
$ \b -> do
for_ bs' <- get
a
put (f' a b)
getwhere
= foldr (\b rest -> f b *> rest) (pure ()) bs for_ bs f
```

Then we can extract the body of `for_`

as a variable `g`

```
flip evalState z $ do
for_ bs' g
getwhere
= foldr (\b rest -> f b *> rest) (pure ()) bs
for_ bs f = do
g b <- get
a put (f' a b)
```

Then inline `for_`

```
flip evalState z $ do
foldr (\b rest -> g b *> rest) (pure ()) bs
getwhere
= do
g b <- get
a put (f a b)
```

Write `g`

in terms of `modify`

```
flip evalState z $ do
foldr (\b rest -> g b *> rest) (pure ()) bs
getwhere
= modify (flip f b) g b
```

and then inline `g`

```
flip evalState z $ do
foldr (\b rest -> modify (flip f b) *> rest) (pure ()) bs
get
```

and use `execState`

rather than `evalState`

with `get`

```
flip execState z $ do
foldr (\b rest -> modify (flip f b) *> rest) (pure ()) bs
```

Now we can take advantage of an interesting property of `foldr`

, that
when `h . g == id`

we have the equality

`foldr (\a -> f a) z == h . foldr (\a -> g . f a . h) (g z)`

(I don’t know if this is a free theorem or whether you have to prove
it by induction.) Observing that `execState`

and `modify`

are
inverses we get

```
flip execState z $ do
$
modify foldr
-> execState $ modify (flip f b) *> modify rest)
(\b rest pure ()))
(execState ( bs
```

We can combine the two `modify`

s to get

```
flip execState z $ do
$
modify foldr
-> execState $ modify (rest . flip f b))
(\b rest pure ()))
(execState ( bs
```

and use that `execState . modify == id`

to get

```
foldr
-> rest . flip f b)
(\b rest pure ()))
(execState (
bs z
```

which is

`foldr (\b rest a -> rest (f a b)) id bs z`

The same calculation for `foldl'`

yields

`foldr (\b rest a -> rest $! f a b) id bs z`