"List" with efficient insert/delete

Question

I am looking for a "List" with log(N) insert/delete at index i. I put the word "List" in quotes, because I don't mean it to be an actual Haskell List, but just any ordered container with a bunch of objects (in fact, it probably needs some sort of tree internally). I am surprised that I haven't found a great solution yet....

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

While these are technically all log(N) functions, it feels like I am doing a bunch of extra stuff for each insert/delete.... In other words, this scales like K*log(N) for a K that is larger than it should be. Plus, since I have to define this stuff myself, I feel like I am using Sequence for something it wasn't designed for.

Is there a better way?

This is a related question (although it only deals with Sequences, I would happily use anything else): Why doesn't Data.Sequence have `insert' or `insertBy', and how do I efficiently implement them?

And yes, this question is related to this other one I posted a few days ago: Massive number of XML edits

Answer 1

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

If you could get away with an IntMap which started sparse and got denser, and was occasionally "rebuilt" when things got too dense, then that might give you better performance -- but that really depends on your patterns of use.