DData revision

Robert Will robertw at stud.tu-ilmenau.de
Sat Mar 20 11:48:55 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.  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!

Anyway such Sequence implementation are more a Bugfix, than an Abstract
Data Structure implementation.  They work around the bad behaviour of
"stack-based list".++.  I belive that using an accumulator to avoid ++'s
bad behaviour is the second most used optimisation in functional programs.
(Using an accumulator is just the same than using closures, since a
function with one additional argument is just the same as a function
returning a closure.)  Wadler (1987!) has even formalised that
optimisation so far it could even be used automatically in a compiler:
http://homepages.inf.ed.ac.uk/wadler/papers/vanish/vanish.pdf

If Haskell implementations would use this, programmers could really spare
some efforts and programs would be clearer.

Anyway, I strongly dissuade including such an ad-hoc data structure into
an exposed library.  (Anyway, with my new simple balancing algorithms,
building worst-case efficient sequences is a trivial Exercise, Dessy alone
provides five different implementations...)

Robert


More information about the Libraries mailing list