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

Question

我正在寻找在索引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编辑

Answer 1

如果您仔细使用预定义的 Haskell 列表，那么它们应该没有问题。（例如连接两个列表时）。

如果您想找到一个具有高效插入和删除功能的列表实现，AVLTree 或任何类型或平衡二叉树都可以。例如，在 AVLTree 中存储一个元组 (Int, a)，其中 Int 是列表的索引，a 是 elem。因此，就平均复杂度而言，插入和删除的操作将是对数的。

我希望这回答了你的问题。