Haskell:具有 O(1) 附加和 O(1) 索引的数据结构？

Question

我在 Haskell 中寻找一种同时支持快速索引和快速追加的数据结构。这是针对递归引起的内存问题。

从向量在 c++ 中的工作方式(它是可变的，但在这种情况下这不重要)看来，具有(摊销)O(1) 附加和 O(1) 索引的不可变向量应该是可能的(好吧，它不是，请参阅对此问题的评论)。这在 Haskell 中是否可行，或者我应该使用具有(AFAICT 无论如何)O(1) 附加和 O(log(min(i,n-i))) 索引的 Data.Sequence？

在相关的说明中，作为一名 Haskell 新手，我发现自己渴望一份实用、简洁的 Haskell 数据结构指南。理想情况下，这将对最实用的数据结构以及性能特征和实现它们的 Haskell 库的指针提供相当全面的概述。似乎那里有很多信息，但我发现它有点分散。我要求太多了吗？

Answer 1

对于简单的内存问题，您通常希望构建表一次，以后不要修改它。在这种情况下，您可以避免担心追加，而是将内存表的构造视为一项操作。

一种方法是利用惰性求值并在我们构建表时引用它。

import Data.Array
fibs = listArray (0, n-1) $ 0 : 1 : [fibs!(i-1) + fibs!(i-2) | i <- [2..n-1]]
  where n = 100

当表格元素之间的依赖关系使得难以提前制定简单的评估顺序时，此方法特别有用。但是，它需要使用盒装数组或向量，由于额外的开销，这可能使这种方法不适合大型表。

对于未装箱的向量，您可以进行 constructN 之类的操作它可以让你以纯粹的方式构建一个表，同时在下面使用突变来提高它的效率。它通过给函数传递一个到目前为止构造的向量前缀的不可变 View 来实现这一点，然后你可以使用它来计算下一个元素。

import Data.Vector.Unboxed as V
fibs = constructN 100 f
  where f xs | i < 2 = i
             | otherwise = xs!(i-1) + xs!(i-2)
             where i = V.length xs