Looking for a random-access sequence data structure
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
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
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
On Fri, 2006-01-13 at 14:41 +0100, Sebastian Sylvan wrote:
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
What's the semantics of insert? Does it replace an element, or does it shirt all the elements after it one step?
It shifts all the elements after it one step. So that's why all the finite map types are no help. Here's the semantics I want, in terms of an implementation using lists: -- for simplicity lets ignore the case of indexing out of range lookup :: Sequence a -> Int -> a lookup = (!!) insert :: Sequence a -> Int -> a -> Sequence a insert seq i x = case splitAt i seq of (before, after) -> before ++ x : after delete :: Sequence a -> Int -> Sequence a delete seq i = case splitAt i seq of (before, x : after) -> before ++ after Duncan
Duncan Coutts wrote:
What's the semantics of insert? Does it replace an element, or does it shirt all the elements after it one step?
It shifts all the elements after it one step. So that's why all the finite map types are no help.
import Data.Map as Map seqInsert i v = Map.insert i v . Map.mapKeysMonotonic (\ j -> if j < i then j else j + 1)
On Fri, 2006-01-13 at 15:21 +0100, Christian Maeder wrote:
Duncan Coutts wrote:
What's the semantics of insert? Does it replace an element, or does it shirt all the elements after it one step?
It shifts all the elements after it one step. So that's why all the finite map types are no help.
import Data.Map as Map
seqInsert i v = Map.insert i v . Map.mapKeysMonotonic (\ j -> if j < i then j else j + 1)
Ah, ok so it can be done, but it's linear rather than log time. Duncan
On Fri, Jan 13, 2006 at 01:18:35PM +0000, 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.
lookup :: Sequence a -> Int -> Maybe a insert :: Sequence a -> Int -> a -> Sequence a delete :: Sequence a -> Int -> Sequence a
Have a look at Data.Sequence (in CVS/darcs version), docs at http://www.haskell.org/ghc/dist/current/docs/libraries/base/Data-Sequence.ht... insert and delete aren't provided, but are easily derived: insert :: Seq a -> Int -> a -> Seq a insert xs i x = front >< x <| back where (front, back) = splitAt i xs delete :: Seq a -> Int -> Seq a delete xs i = front >< drop 1 back where (front, back) = splitAt i xs (where splitAt and drop are the sequence versions). Each of the three operations takes O(log(min(i,n-i))) time.
On Fri, 2006-01-13 at 13:53 +0000, Ross Paterson wrote:
On Fri, Jan 13, 2006 at 01:18:35PM +0000, 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.
lookup :: Sequence a -> Int -> Maybe a insert :: Sequence a -> Int -> a -> Sequence a delete :: Sequence a -> Int -> Sequence a
Have a look at Data.Sequence (in CVS/darcs version), docs at
Ah, that's why I didn't find it! :-)
http://www.haskell.org/ghc/dist/current/docs/libraries/base/Data-Sequence.ht...
insert and delete aren't provided, but are easily derived:
insert :: Seq a -> Int -> a -> Seq a insert xs i x = front >< x <| back where (front, back) = splitAt i xs
delete :: Seq a -> Int -> Seq a delete xs i = front >< drop 1 back where (front, back) = splitAt i xs
(where splitAt and drop are the sequence versions).
Each of the three operations takes O(log(min(i,n-i))) time.
Thanks very much, that's great. Duncan
On Fri, 2006-01-13 at 13:53 +0000, Ross Paterson wrote:
On Fri, Jan 13, 2006 at 01:18:35PM +0000, 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.
lookup :: Sequence a -> Int -> Maybe a insert :: Sequence a -> Int -> a -> Sequence a delete :: Sequence a -> Int -> Sequence a
Have a look at Data.Sequence (in CVS/darcs version), docs at
http://www.haskell.org/ghc/dist/current/docs/libraries/base/Data-Sequence.ht...
And as a bonus the append and prepend operations are O(1), which is nice since for my application these are probably more likely than inserting at arbitrary indexes. It's probably too much to ask, but here's a question: would it be possible to provide an operation that gives a left or right view from looking up an index. Say: viewrFromIndex :: Seq a -> Int -> ViewL a viewlFromIndex :: Seq a -> Int -> ViewR a The library currently provides views for the each end of the sequence. viewl :: Seq a -> ViewL a viewr :: Seq a -> ViewR a I suppose this would be a zipper-like iterator for the sequence? I ask since a common use in my application will involve sequential access (though random access is still required). So if I cached an iterator/zipper/view thing to use in case the next lookup happens to be the next in the sequence then I could do that in O(1) time rather than doing an ordinary O(log n) lookup. Just wondering. :-) Duncan
On Fri, Jan 13, 2006 at 08:25:46PM +0000, Duncan Coutts wrote:
On Fri, 2006-01-13 at 13:53 +0000, Ross Paterson wrote:
Have a look at Data.Sequence (in CVS/darcs version), docs at
http://www.haskell.org/ghc/dist/current/docs/libraries/base/Data-Sequence.ht... [...] It's probably too much to ask, but here's a question:
would it be possible to provide an operation that gives a left or right view from looking up an index. Say:
viewrFromIndex :: Seq a -> Int -> ViewL a viewlFromIndex :: Seq a -> Int -> ViewR a
The library currently provides views for the each end of the sequence.
viewl :: Seq a -> ViewL a viewr :: Seq a -> ViewR a
I suppose this would be a zipper-like iterator for the sequence?
I'm not entirely sure what these are intended to do, but can't you just compose view[lr] with take/drop? A zipper for a non-empty sequence is just an element and a pair of sequences. Moving it by k positions using splitAt and (><) costs O(log(k+1)).
On Fri, 2006-01-13 at 20:52 +0000, Ross Paterson wrote:
On Fri, Jan 13, 2006 at 08:25:46PM +0000, Duncan Coutts wrote:
On Fri, 2006-01-13 at 13:53 +0000, Ross Paterson wrote:
Have a look at Data.Sequence (in CVS/darcs version), docs at
http://www.haskell.org/ghc/dist/current/docs/libraries/base/Data-Sequence.ht... [...] It's probably too much to ask, but here's a question:
would it be possible to provide an operation that gives a left or right view from looking up an index. Say:
viewrFromIndex :: Seq a -> Int -> ViewL a viewlFromIndex :: Seq a -> Int -> ViewR a
The library currently provides views for the each end of the sequence.
viewl :: Seq a -> ViewL a viewr :: Seq a -> ViewR a
I suppose this would be a zipper-like iterator for the sequence?
I'm not entirely sure what these are intended to do, but can't you just compose view[lr] with take/drop?
Oh yes, so you can. That's very neat. Thanks. Duncan
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
participants (6)
-
Christian Maeder -
Duncan Coutts -
Greg Buchholz -
Ross Paterson -
S.M.Kahrs -
Sebastian Sylvan