[Haskell-cafe] Weaving fun

[Jan-Willem Maessen]

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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 2425 bytes
Desc: not available
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20070413/00e6b81a/smime-0001.bin