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