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