问在Haskell中，什么容器真正模仿std::vector？

EN

使用Data.Vector.constructN的建议来自reddit

O(n)通过对向量的已构造部分重复应用生成函数来构造具有n个元素的向量。

constructN 3 f=设a=f <>；b=f；c=f in f

例如：

λ import qualified Data.Vector as V
λ V.constructN 10 V.length
fromList [0,1,2,3,4,5,6,7,8,9]
λ V.constructN 10 $ (1+) . V.sum
fromList [1,2,4,8,16,32,64,128,256,512]
λ V.constructN 10 $ \v -> let n = V.length v in if n <= 1 then 1 else (v V.! (n - 1)) + (v V.! (n - 2))
fromList [1,1,2,3,5,8,13,21,34,55]

这看起来确实有资格解决您上面所描述的问题。

我想到的第一个数据结构要么是来自Data.Map的映射，要么是来自Data.Sequence的序列。

更新

Data.Sequence

序列是持久化的数据结构，它允许大多数操作高效，同时只允许有限的序列。如果你感兴趣，他们的实现是基于finger-trees的。但是它有哪些品质呢？

使用运算符length

• O(1) respectively.

• O(n) fromlist

• O(log(min(n1，n2.

• O(log(min(i，从列表中创建<|和|>在前面/后面插入n2)长度为的序列的n1连接N-i)在长度为n的序列中对位置i处的元素进行索引。

此外，这种结构支持许多您期望从列表结构中获得的已知和方便的函数：replicate、zip、null、scan、sort、take、drop、splitAt等等。由于这些相似性，您必须在Prelude中进行限定导入或隐藏具有相同名称的函数。

Data.Map

地图有两种风格-- strict和lazy。

引用文档中的内容

严格

此模块的

接口对键和值都有严格要求。

懒惰

这个模块的

接口在键上是严格的，在值上是惰性的。

因此，您需要选择最适合您的应用程序。您可以尝试两个版本，并使用criterion进行基准测试。

我没有列出我想要介绍的Data.Map的特性

Data.IntMap.Strict

它可以利用键是整数的事实来挤出更好的性能，引用我们首先注意到的文档：

许多运算的最坏情况复杂度为O(

(n，W))。这意味着操作可以在元素数量上成为线性，最大值为W -- Int (32或64)中的位数。

那么IntMaps的特征是什么呢

• O(min(n，W))用于(不安全的)索引(!)，不安全的意思是如果键/索引不存在，您将得到一个错误。这与size
• O(min(n，W)的Data.Sequence.
• O(n)计算的行为相同))用于安全索引lookup的，如果找不到密钥则返回Nothing，并且Just a W)用于insert、delete、adjust和

因此，您可以看到，这种结构的效率低于Sequences，但如果您实际上不需要所有条目，例如稀疏图的表示，则提供了更多的安全性和巨大的好处，其中节点是整数。

为了完整起见，我想提到一个名为persistent-vector的包，它实现了clojure风格的向量，但似乎被放弃了，因为最后一次上传来自(2012)。

结论

所以对于你的用例，我强烈推荐使用Data.Sequence或Data.Vector，不幸的是我没有任何使用后者的经验，所以你需要自己尝试一下。据我所知，它提供了一种称为流融合的强大功能，可以优化在一个紧密的“循环”中执行多个函数，而不是为每个函数运行一个循环。可以在here上找到Vector的教程。

在寻找具有特定渐近运行时间的函数容器时，我总是使用Edison。

请注意，在具有不可变数据结构的严格语言中，在它们之上实现可变数据结构总是对数减速。这是一个悬而未决的问题，隐藏在懒惰背后的有限变异能否避免这种减速。还有持久与暂时的问题……

Okasaki仍然是一个很好的背景读物，但是finger tree或者像RRB-tree这样更复杂的东西应该是“现成的”，可以解决你的问题。