具有高效插入/删除的"列表"

我正在寻找在索引i处插入/删除日志(N)的"列表".我把单词"List"放在引号中,因为我并不是说它是一个真正的Haskell List,而是任何带有一堆对象的有序容器(事实上,它可能需要内部的某种树).我很惊讶我还没有找到一个很好的解决方案....

这是我迄今为止最好的解决方案 - 使用Data.Sequence这两个函数.

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

虽然这些在技术上都是log(N)函数,但感觉就像我为每个插入/删除做了一堆额外的东西....换句话说,这对于K更大的K来说就像K*log(N)一样比应该的.另外,由于我必须自己定义这些内容,我觉得我正在使用Sequence来实现它不适合的东西.

有没有更好的办法？

这是一个相关的问题(尽管它只涉及Sequences,我很乐意使用其他任何东西):为什么Data.Sequence没有`insert'或`insertBy',我该如何有效地实现它们？

是的,这个问题与我几天前发布的另一个问题有关:大量的XML编辑