相关疑难解决方法(0)

我正在学习Haskell,并阅读了几篇关于Haskell列表和(插入语言)数组的性能差异的文章.

作为一个学习者,我显然只是在不考虑性能差异的情况下使用列表.我最近开始调查,发现Haskell中有许多数据结构库.

有人可以解释一下列表,数组,向量,序列之间的区别,而不是深入研究数据结构的计算机科学理论吗？

此外,是否有一些常见的模式,您将使用一个数据结构而不是另一个？

是否有任何其他形式的数据结构我缺少并可能有用？

问题

我正在寻找一个容器,用于保存n - 1问题的部分结果,以便计算n第一个问题.这意味着容器的大小始终是n.

i容器的每个元素取决于至少2个和最多4个先前的结果.

容器必须提供:

• 开始或结束时的恒定时间插入(两者之一,不一定都是)
• 中间的恒定时间索引

或者(给定O(n)初始化):

• 恒定时间单元素编辑
• 中间的恒定时间索引

std::vector它是什么以及为什么相关

对于那些不了解C++的人来说,std::vector是一个动态大小的数组.它非常适合这个问题,因为它能够:

• 建设中的储备空间
• 在中间提供恒定时间索引
• 最后提供恒定时间插入(带有预留空间)

因此O(n),在C++中,这个问题在复杂性方面是可以解决的.

为什么Data.Vector不呢std::vector

Data.Vector与...一起Data.Array提供类似的功能std::vector,但不完全相同.当然,两者都在中间提供恒定的时间索引,但它们既不提供恒定的时间修改((//)例如至少O(n)),也不提供在任何一个开始时的恒定时间插入.

结论

什么容器真的模仿std::vectorHaskell？或者,什么是我最好的镜头？