On 1/13/06, Duncan Coutts <duncan.coutts@worc.ox.ac.uk> wrote:
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.
What's the semantics of insert? Does it replace an element, or does it shirt all the elements after it one step? /S -- Sebastian Sylvan +46(0)736-818655 UIN: 44640862