DData revision

Simon Marlow 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 mailing list