data-structures - 实现不可变的、可增长的向量

Question

我对在 F# 中实现持久性(例如纯函数式、不可变等)、可增长向量感兴趣，以便它们可以在 .NET 框架中使用。我当前的实现是哈希映射树的一个变体，是根据 Clojure's implementation 完成的。 .

我在使用此实现实现随机访问插入和删除(在随机索引处插入和删除元素)时遇到问题。是否有一些算法/修改可以有效地允许这些操作，或者我可以查看其他一些实现？

澄清:当我说“插入”和“删除”时，我的意思是，例如，给定列表 [1; 2; 3; 4]插入 500就位1会给我[1:500:2:3:4] .我不是说 set或 associate手术。

Answer 1

Finger trees可能是你正在寻找的。有一个Clojure implementation可用的。