Haskell:有效模拟内存块的纯数据结构？

Question

我有兴趣编写一个使用内存块的虚拟机。我想使用纯数据结构对内存块(例如 1MB)进行建模，该结构对于 block 内任何位置的读写仍然有效。对可变结构不太感兴趣。这样的结构存在吗？

Answer 1

vector包提供不可变(和可变)装箱和未装箱向量，具有您期望的所有时间复杂度。可变的可以从 IO 和 ST 中使用，并且您可以拥有任何 Storable 实例的未装箱数组。它比标准数组模块好得多。

但是，既然您提到了高效的不可变更新，我建议使用类似 Map 的数据结构；也许是来自 unordered-containers 的 HashMap 。甚至可能值得在叶子处拥有一张带有小型未装箱矢量的 map ，以避免一些树开销。

根据您的用例，您可能还对标准 Data.Sequence 感兴趣，它对开头和结尾的访问时间为 O(1)，并且对序列中间的访问时间相当长。