Edsko de Vries | 8 Jan 13:22 2013
Picon

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
(Continue reading)

Roman Cheplyaka | 8 Jan 13:57 2013

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
Stephen Tetley | 8 Jan 18:30 2013
Picon

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