On 1/13/06, Duncan Coutts <[EMAIL PROTECTED]> 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 _______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
