Derek Elkins derek.a.elkins at gmail.com
Fri Apr 13 22:26:57 EDT 2007

```Jan-Willem Maessen wrote:
>
> On Apr 12, 2007, at 9:39 PM, Matthew Brecknell wrote:
>
>> Jan-Willem Maessen:
>>> Interestingly, in this particular case what we obtain is isomorphic
>>> to constructing and reversing a list.
>>
>> Jan-Willem's observation also hints at some interesting performance
>> characteristics of difference lists. It's well known that difference
>> lists give O(1) concatenation, but I haven't seen much discussion of the
>> cost of conversion to ordinary lists.
>
> Nice analysis, thanks to both of you.  I think a lot of this folklore
> isn't widely understood, particularly the fact that the closures
> constructed by difference lists are isomorphic to trees, with nodes
> corresponding to append/compose and leaves corresponding to
> empty/singleton.
> So you pay the cost for append each time you flatten---the difference
> list trick is only a win if you flatten to an ordinary list once and/or
> consume the entire list each time you flatten it.  I'd had an intuitive
> notion of how this worked, but this spells it out nicely.
>
> Of course, once you represent things like so:
>
> data DiffList a = Segment [a]
>         | DiffList a :++ DiffList a
>
> toList :: DiffList a -> [a]
> toList dl = toListApp dl []
>
> toListApp :: DiffList a -> [a] -> [a]
> toListApp (Segment s) = (s++)
> toListApp (a:++b)     = toListApp a . toListApp b
>
> You can start thinking about all sorts of other interesting questions,
> beyond just transforming to a list and eta-abstracting toListApp.  The
> next thing you know, you're writing a better pretty printer or otherwise
> mucking about with the DiffList type itself to tailor it for your own
> nefarious purposes.
>
> -Jan
>
>
> ------------------------------------------------------------------------
>
> _______________________________________________