[Haskell] Looking for a random-access sequence data structure

[Greg Buchholz]

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