[Haskell-cafe] Weaving fun
Jan-Willem Maessen
jmaessen at alum.mit.edu
Fri Apr 13 11:02:04 EDT 2007
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
More information about the Haskell-Cafe
mailing list