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