Haskell数据结构对于交换元素是否有效？

Question

我正在寻找一个Haskell数据结构,它存储一个有序的元素列表,并且在交换列表中任意位置的元素对时节省时间.[a]显然,这不是.这不是Vector因为交换创建了新的向量.哪种数据结构有效？

Answer 1

持久数据结构的最有效实现,其展示O(1)更新(以及附加,前置,计数和切片),基于阵列映射Trie算法.例如,Clojure和Scala的Vector数据结构就是以它为基础的.我所知道的唯一Haskell实现的数据结构是由"持久向量"包提供的.

这个算法非常年轻,它只在2000年首次出现,这可能是为什么没有这么多人听说过它的原因.但事实证明这是一个普遍的解决方案,很快就适应了哈希表.该算法的改编版本称为Hash Array Mapped Trie.它也可以在Clojure和Scala中用于实现Set和Map数据结构.它在Haskell中也更为普遍,包括"无序容器"和"stm-containers"等包.

要了解有关该算法的更多信息,我建议使用以下链接:

• http://blog.higher-order.net/2009/02/01/understanding-clojures-persistentvector-implementation.html
• http://lampwww.epfl.ch/papers/idealhashtrees.pdf

Answer 2

Data.Sequence从containers这个用例开始,从包中可能是一个不太可怕的数据结构.

Answer 3

Haskell 是一种（几乎）纯函数式语言，因此您更新的任何数据结构都需要创建该结构的新副本，并且重新使用数据元素几乎是您能做的最好的事情。此外，新列表将被延迟评估，并且通常只需要创建主干，直到您需要数据为止。如果更新的数量与元素的数量相比较小，您可以创建一个差异列表，首先检查一组稀疏的更新，然后才查看原始向量。