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.
The conversion cost seems to be O(n), where n is the number of concatenations performed to build the difference list.
The O(n) conversion cost is amortized over deconstructing the list thanks to laziness. So the head element is O(1). If head were O(n) then it would never be a win over using reverse.
[snip]
Slightly more interesting is the observation that the grouping of difference list concatenations has a significant impact on the conversion cost, and in particular, on when the cost is incurred. When concatenations are grouped to the right, we get lazy conversion. Grouped to the left, we get strict(er) conversion.
AFAIK, constructing a difference list using (.) is exactly like constructing a tree. The cost of converting to a normal list and getting the head element requires traversing the tree from the "root" to the first element. So if you construct it with just appends then the first element is the left node of the root, which is very fast. And if you construct it with prepends then the first element requires traversing the whole list. Since the list can only be deconstructed in order the sensible way to build a difference list is with appends. Note that pre-pending a huge list will blow the stack (for at least GHC). -- Chris