Recently I was surprised by the behaviour of a Haskell program I wrote. This simple example demonstrates the problem:

This computes the length of the list formed by every n-sized combination of the letters “a”, “b” and “c”. For example, if `n` is 4, the first few elements of the list are “aaaa”, “aaab”, “aaac”, “aaba”. (In other words, it’s a slow way to compute 3 to the power of `n`.) I expected this program to take near-constant space, even though the list might be very long, because it can be consumed by `length` as it is produced by `sequence`.

However, as `n` increases the space required grows exponentially.

For example:

The “in use” value is the interesting one: 4MB for `n`=10, and 11MB for `n`=11.

Even more surprising is what happens when you give your own definition of `sequence`:

Now the same examples as before:

This time we get constant space. Then take the same program, and turn on optimization:

And memory use is high again — optimization has made it worse. What is going on?

The explanation is that GHC has tried to make our definition of `mySequence` faster, but at the expense of using more memory. It has observed that the value of `mySequence ys` does not depend on what value is chosen for `x`, and moved it out of the loop. In effect, it has transformed our definition into:

The result for our combination-counting program is that to compute the big list of `n`-sized combinations, it first computes the list of `(n-1)`-sized combinations and keeps this sub-list in memory so that it can put an “a”, “b” or “c” on the front of each element. That is, while exploring all the combinations that start with “a”, the sub-list stays in memory so it doesn’t have to be computed again later to make all the combinations that start with “b” and “c”. The sub-list is pretty big, and that’s the cause of the high memory use.

This optimization is called “full laziness”, and you can turn it off:

With the optimization turned off, memory use is constant again.

When I first encountered this problem I had no idea what the cause was. After some searching I found this discussion on Stack Overflow, which explains what is going on and a couple of ways to work around it (apart from just turning off the full laziness optimization).

## A second problem

A variation of the problem comes courtesy of Albert Lai. In this program, we also get exponential memory use, but changing the optimization level doesn’t fix it. Here is the program in question:

On the surface it looks similar to the previous programs. In particular, the definition of `k` is very close to `mySequence` above and so you might expect that the full laziness optimization is again the culprit. But turning off optimization here doesn’t help.

In this case the `foldr` is the problem. Recall the behaviour of `foldr`:

In the misbehaving problem, we have:

where `ms = [m0, m1, ... mn]`. If we examine the outermost call to `k` more closely, we get:

This is equivalent in behaviour to:

The function `k` has done the same thing that full laziness did: it’s given a name (here `m'`) to the big sub-list, causing it to be shared across the loop over the choice of the first element (the `x <- m`).