在Haskell中的结构共享矢量

Question

是Vector在Haskell结构共享？在Clojure中,修改(immutable)vector只需要O(log n)时间,因为它实际上是一个类似trie的结构.(http://hypirion.com/musings/understanding-persistent-vector-pt-1)

在Haskell中是否有相同的实现？

Answer 1

Data.Vector 是具有O(n)修改的普通数组.

当时没有相当于Clojure的矢量.

Data.Sequence 实现为手指树,它支持比Clojure的向量(O(log(n))连接和分裂,O(1)两端读/写)更广泛的渐近有效操作,但它也更多一点重量级数据结构,具有更多的RAM使用和一些不断的开销.