On Fri, 19 Mar 2004, Robert Will wrote:

...

By the way: a Sequence implementation based on OrdList is not too attractive either...

I have had a look at OrdList (in GHC 5.00 and JPs DData) and this has really no advantage over the simple Catenable Sequences, in fact it only uses data cells where the other one uses closures.

I didn't write OrdList, but I don't agree: toList.fromList is O(n) in the the closure version, but O(1) in the OrdList version. I suppose in a sense that is really a constant factor difference, because with laziness the closure version only adds a constant factor to the O(n) operation that observes the result list. But it also unshares the result list, which might be important.

Also the implementor has not been too clever, since in the function OLtoList he uses the Closure-trick to create the resulting list, but just the same would have been achieved by a call to foldr!

Indeed, toList is just a specialised version of foldr. Probably either (a) a specialised version was used for speed, or (b) foldr was added later. Cheers, Simon