[Haskell-cafe] Difference Lists versus Accumulators

[Edsko de Vries]

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
lists are useful.

Edsko