# Difference lists

This post is an extended version of a lightning talk I gave at the Brisbane Functional Programming Group. It introduces the difference list, a simple trick for improving the performance of certain kinds of list-building functions in Haskell, and goes on to explore the connections to monoids and folds.

The first half is aimed at Haskell novices, while the latter parts might be interesting to intermediates.

## A first example

Let’s reverse some lists. I’m sure you’ve seen this before:

It’s a simple and clear definition, but it performs badly. List concatenation, `(++)`, traverses its left argument, and since that’s a recursive call, this version takes quadratic time overall.

We can get to linear time by introducing an accumulator:

This is a worker-wrapper, where the wrapper initialises the accumulator to the empty list, `[]`. The worker, `go`, is tail recursive, and accumulates the result in reverse order as it forward-traverses the input.

Although efficient, this is less clear. Let’s tidy up the worker by eliminating the accumulator parameter, `acc`:

The first case (line 5) is just the identity function, `id`, while we can write the second case as a function composition:

If we now compare the worker, `go`, with our original version of `reverse`, we see a similar structure, with some differences:

• The empty list, `[]`, becomes the identity function, `id`.
• List concatenation, `(++)`, becomes function composition, `(.)`.
• The singleton list, `[x]`, becomes a function, `(x:)`, which prepends `x` to its argument.
• The list type, `[a]`, becomes the function type, `[a] -> [a]`, in the result.

For the last point, recall that `a -> b -> c` parses as `a -> (b -> c)`.

## Tree flattening

For a second example, let’s take a binary tree and flatten it to a list of elements in left-to-right order. Again, this version is clear, but since there is a recursive call to `flatten` on the left of list append, `(++)`, it takes quadratic time in the worst case:

As before, the linear-time version uses an accumulator to build the result in reverse:

If we rearrange, and compare the worker, `go`, with the original, inefficient version, we can see the same patterns we saw in the `reverse` function:

## Difference lists

Having identified the pattern, we can define the type of difference lists, together with its basic operations:

This means a difference list is a function which prepends some number of items to its argument, without inspecting that argument. For example, this is a difference list:

But the following is not a difference list, because the `reverse` function inspects its argument, and because it does not incorporate the argument in its result:

Comparing the difference list operations with the corresponding ones on ordinary lists, we see that that difference list `append` takes constant time, whereas for ordinary lists, `(++)` takes time linear in the size of the left argument. This means difference lists are good for building lists using left-associated concatenation.

But there’s a catch!

The time complexities are amortised, and they are only valid when the difference list is used ephemerally. If you attempt to use a difference list persistently, `toList` may degrade to linear time.

The reason for this is that there are two costs associated with `append`. The first is paid when `append` builds a closure for the function composition. The second is paid every time the function composition is applied to an argument. That is, whenever `toList` is evaluated.

This means that `toList` actually takes time that is linear in the number of function compositions it has to apply. However, if we are only interested in the overall time taken by a sequence of operations, we can assign the cost of evaluating the function composition to `append`, even though the evaluation occurs in `toList`. And so we can say that both `append` and `toList` take amortised constant time.

Of course, that analysis assumes that `toList` is only evaluated once. This is what it means to restrict ourselves to ephemeral usage.

To show that difference lists are not magical, let’s see how we might use them inappropriately. Since difference lists are good for appending, perhaps they could be used to implement a FIFO queue:

The `put` operation seems fine, provided we don’t attempt to use the `Queue` persistently. For `take`, we find that we need to use `toList` before we can inspect the contents of the queue. Worst of all, we must use the linear-time `fromList` to construct the new `Queue`.

Since switching back and forth between difference lists and ordinary lists is inefficient, difference lists are primarily useful in build-then-consume algorithms. We can use a difference list to efficiently build a list, before converting to an ordinary list that is then consumed.

## Some fun with folds

While it’s good to know when and how to use difference lists, it’s even nicer to understand the connections to folds and monoids. Let’s reexamine our difference-list-based `reverse`:

The only places we actually construct any lists are the empty list, `[]`, at the end of line 2, and the singleton difference list, `(x:)`, at the end of line 6. Let’s abstract over those, calling them `z` and `f x` respectively:

We can then generalise the type without touching the implementation, and arrive at a familiar function:

The type of argument `f` is flipped with respect to the Prelude version, but the meaning is the same. So we can say that `foldl` is just `reverse` with the constructors abstracted.

Similarly, we can say that `foldr` is just a list traversal with the constructors abstracted. In fact, we can get the right-fold on `Tree` using the same generalisation on `flatten`. For lists, we can get `foldr` by simply flipping the function composition in line 6:

## Monoids

To make precise the comparison between the two versions of each of our examples, we need to recognise that we are using the corresponding operations of two different monoids, the list monoid and the `Endo` monoid:

Notice that in the `Endo` monoid, we’ve generalised from the type `[a] -> [a]` that we used for difference lists, to `b -> b`, just as we did when we generalised from `reverse` to `foldl`.

We also need a way to inject a single element into a monoid. We use the `unit` method of the `Reducer` class, from the reducers package. We can then rewrite `reverse` and `flatten` like this:

If we treat the result as a list, we get the inefficient versions:

But if we add an appropriate wrapper, we get the efficient versions:

## More fun with folds

Now that we know about `Endo`, let’s reexamine `foldr`:

First let’s rearrange the arguments a little, swapping `z` and `xs`:

We can see the type `b -> b` in lots of places, and we’re using the function `id` and composition as well. That’s just the `Endo` monoid, so let’s rewrite like this:

Without touching the implementation, we can generalise the type to any monoid, and rename:

The wrapper is no longer doing anything, so we have just this:

Notice how `foldMap` follows the structure of the list data type. We can recover `foldr` by specialising to the `Endo` monoid, and extracting the result by applying to the argument `z`:

To get `foldl`, we would need a version of `Endo` in which the monoid append (i.e. the function composition) is reversed. `Dual` is a monoid transformer which just flips the monoid append operation, `<>`, with respect to the base monoid:

What about `Tree` flattening? Well, `Tree` has a `foldMap`, too:

Again, notice how `foldMap` follows the structure of the `Tree` data type. We could reuse the same definitions of `foldr` and `foldl` above, just by changing the types.

In fact, we’ve just reinvented the `Foldable` type class from the base package:

Just by implementing `foldMap` for your `Foldable` data types, you get `foldl` and `foldr` for free. This means you can use whichever fold is most appropriate for your situation. For example:

What’s more, if your `foldMap` follows the structure of your data type, `foldl` and `foldr` will both be maximally lazy and efficient. For example, `first` is O(1) on lists, including infinite lists, and O(log n) on `Data.Set`, while `last` is O(n) on lists, but still O(log n) on `Data.Set`.

Following Voitgländer, we can write our `extract` function with a more restrictive rank-2 type:
This ensures that the computed list is in fact a difference list, by restricting the construction to `mempty`, `(<>)` and `unit`.