8 Jan 2013 13:22

## Difference Lists versus Accumulators

```Hey all,

The connection between difference lists and accumulators is probably
well known, but I only recently realized it myself and a quick Google
search didn't find turn up any page where this was explicitly stated,
so I thought this observation might be useful to some.

Every beginner Haskell student learns that this definition of
"reverse" has O(n^2) complexity:

reverse [] = []
reverse (x : xs) = reverse xs ++ [x]

But what happens when we return a difference list instead, replacing
[] with id, (++) with (.) and [x] with (x :)?

reverse' [] = id
reverse' (x : xs) = reverse xs . (x :)

This definition of reverse' has type

reverse' :: [a] -> [a] -> [a]

Let's inline the second argument:

reverse' [] acc = acc
reverse' (x : xs) acc = reverse' xs (x : acc)

And we have recovered the standard definition using an accumulator! I
thought that was cute :) And may help understanding why difference
```

8 Jan 2013 13:57

### Re: Difference Lists versus Accumulators

```* Edsko de Vries <edskodevries <at> gmail.com> [2013-01-08 12:22:59+0000]
> But what happens when we return a difference list instead, replacing
> [] with id, (++) with (.) and [x] with (x :)?
>
> ...
>
> And we have recovered the standard definition using an accumulator! I
> thought that was cute :) And may help understanding why difference
> lists are useful.
>
> Edsko

Perl: There Is More Than One Way To Do It
Python: There Is One Way To Do It
Haskell: There Is One Way To Do It, Up To Isomorphism

:)

Roman
```
8 Jan 2013 18:30

### Re: Difference Lists versus Accumulators

```See the first Worker / Wrapper paper by Andy Gill and Graham Hutton.
Particularly there is exactly this derivation of reverse through
preliminarily using a Hughes (difference) list.

On 8 January 2013 12:22, Edsko de Vries <edskodevries <at> gmail.com> wrote:
> Hey all,
>
> The connection between difference lists and accumulators is probably
> well known, but I only recently realized it myself and a quick Google
> search didn't find turn up any page where this was explicitly stated,
> so I thought this observation might be useful to some.
```

Gmane