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