Duncan Coutts wrote:
>
> I've been looking around (unsuccessfully) for an efficient data
> structure to implement a sequence data type with indexed
> insert/delete/lookup.
See also, Robert Will's "Democratic Sequences" which strive for O(log
n) complexity for all major operations...
Democratic Sequences: an Abstract Sequence Data Type which is not
optimised for some algorithms (as Deques and many other
implementations are), but which aims to provide a very simple and
consistent interface for day-to-day programming and prototyping,
where any sensible operation runs with acceptable performance,
although possible none is optimal.
...unfortunately the write-up and code seems to have lost its home, so
you'll have to get it from the Google cache ( http://xrl.us/jjs9 ).
Greg Buchholz
_______________________________________________
Haskell mailing list
Haskell@haskell.org
http://www.haskell.org/mailman/listinfo/haskell
