[Haskell-cafe] Difference Lists versus Accumulators

Edsko de Vries edskodevries at gmail.com
Tue Jan 8 13:22:59 CET 2013


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



More information about the Haskell-Cafe mailing list