Hi all, I've been looking around (unsuccessfully) for an efficient data structure to implement a sequence data type with indexed insert/delete/lookup.
lookup :: Sequence a -> Int -> Maybe a insert :: Sequence a -> Int -> a -> Sequence a delete :: Sequence a -> Int -> Sequence a Obviously I can implement this with ordinary lists in O(n) time for each operation. It seems that this could be done in O(log n) time for each operation. This seems like a fairly common collection signature to want but to my surprise I've not been able to find any existing implementations that support it. There are several that have almost all the necessary operations. 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'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. Duncan _______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
