[Haskell-cafe] Weaving fun

Matthew Brecknell haskell at brecknell.org
Thu Apr 12 21:39:21 EDT 2007


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. Since the cost of
building such a difference list is already O(n), the conversion cost
only becomes significant if a difference list is converted more than
once. Of course, the cost of consuming any one of those conversions is
also likely to be at least O(n), so we see why this doesn't get much
attention.

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.

To see this, consider what happens if we take the heads of two
difference lists, with concatenations grouped to the right and left
respectively:

> head_r n = head ((foldr1 (.) (map (:) [1..n])) [])
> head_l n = head ((foldl1 (.) (map (:) [1..n])) [])

We find that head_r is O(1), and head_l is O(n). Writing out the
conversion for a left-grouped difference list, we also see Jan-Willem's
reverse isomorphism quite clearly:

head ((((1:).(2:)).(3:)) [])
==> head (((1:).(2:)) (3:[]))
==> head ((1:) (2:3:[]))
==> head (1:2:3:[])
==> 1



More information about the Haskell-Cafe mailing list