> I've been looking around (unsuccessfully) for an efficient data > structure to implement a sequence data type with indexed > insert/delete/lookup. [snip] For example the Data.Map supports all of these except > insert. Okasaki's random access lists only support inserting elements at > the head of the list.
I think it's possible to give an O(log n) insert-operation of Okasaki's random access list, but I would expect it to be rather messy. > I'd guess that some kind of (balanced) binary search tree where each > node is annotated with the number of nodes below it could support all > these operations. Yes, but you don't need to go that far. Braun trees should do fine. Stefan _______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
