Fri Apr 13 03:13:12 EDT 2007

```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

```