List with efficient insertion / deletion

Question

I am looking for a "List" with input / removal log (N) in index i. I put the word "List" in quotation marks because I do not mean that this is the actual Haskell list, but only any ordered container with a bunch of objects (in fact, it probably needs some kind of tree inside). I am surprised that I have not yet found a great solution ....

This is the best solution I have so far. Use Data.Sequence with these two functions.

doInsert position value seq = before >< ( value <| after) where (before, after) = splitAt position seq doDelete position seq = before >< (drop 1 after) where (before, after) = splitAt position seq 

Although this is technically all the functions of the log (N), it seems to me that I am doing a bunch of additional materials for each insert / delete ... In other words, it scales like K * log (N) for K, which is more than it should be. Plus, since I have to define this material myself, I feel like I'm using Sequence for something that it's not intended for.

Is there a better way?

This is a related question (although it only applies to sequences, I would love to use something else): Why Data.Sequence does not have “insert” or “insertBy”, and how can I effectively implement them?

And yes, this question is related to this other that I posted a few days ago: Massive amount of XML changes

Answer 1

There are structures like catenable seqs, catenable queues, etc. that can give you an O (1) join. However, all such structures that I know about get away from this by giving you an O (i) split. If you want to split and combine both in order to be as optimal as possible, I think your best bet is (aka Sequence ). The entire point of the Sequence path is structured to ensure that between splitting, combining, etc. There was an asymptotically not terrible amount of juggling with splitting and joining among other things.

If you could leave with IntMap , which started out leaner and denser, and was sometimes “rebuilt” when the situation got too dense, this could give you better performance, but it really depends on your usage patterns.

Answer 2

If you work carefully with Haskell predefined lists, there should be no problem with them. (For example, when combining two lists).

If you want to find an implementation for lists, with efficient insertion and deletion, AVLTree or any other or balanced binary tree will work. For example, save a tuple (Int, a) in AVLTree, where Int is the list index and element. Therefore, with moderate complexity, operations will be logarithmic for insertion and deletion.

Hope this answers your question.