simonmar at microsoft.com
Mon Mar 22 10:47:33 EST 2004
> 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
More information about the Libraries