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
------------------------------------------------------------------------
_______________________________________________
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe
And the relationship between them is de-/re-functionalization,
"Defunctionalization at Work" (http://www.brics.dk/RS/01/23/) has some
interesting applications of ideas along the line of Jan's.
_______________________________________________
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe
