Haskell:使用O(1)追加和O(1)索引的Datastruture？

Question

我在Haskell中寻找一种支持快速索引和快速追加的数据结构.这是针对由递归引起的memoization问题.

从矢量在c ++中工作的方式(这是可变的,但在这种情况下应该无关紧要)它似乎是不可变的向量与(摊销)O(1)追加和O(1)索引应该是可能的(好吧,它不是,看到这个问题的评论).这在Haskell中是不可能的,还是应该使用Data.Sequence,它有(AFAICT无论如何)O(1)追加和O(log(min(i,ni)))索引？

在一个相关的说明中,作为一个Haskell新手,我发现自己渴望一个实用,简洁的Haskell数据结构指南.理想情况下,这将对最实用的数据结构以及性能特征和指向Haskell库的指针进行相当全面的概述.似乎有很多信息,但我发现它有点分散.我问得太多了吗？

Answer 1

对于简单的memoization问题,您通常希望构建一次表,然后不再修改它.在这种情况下,您可以避免担心附加,而是将memoization表的构造视为一个操作.

一种方法是利用惰性求值,并在构造它时参考表格.

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

当表的元素之间的依赖关系使得很难提出一个提前评估它们的简单顺序时,此方法特别有用.但是,它需要使用盒装数组或向量,这可能会使这种方法由于额外的开销而不适合大型表.

对于未装箱的向量,您可以使用这样的操作constructN,以纯粹的方式构建表,同时使用下面的变异使其高效.它通过给你传递一个到目前为止构造的向量前缀的不可变视图的函数来做到这一点,然后你可以用它来计算下一个元素.

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

Answer 2

如果内存服务,C++向量实现为具有边界和大小信息的数组.当插入会增加超出大小的边界时,大小会加倍.这是O(1)时间插入的摊销(不是你声称的O(1)),并且可以使用Array类型在Haskell中模拟得很好,可能是合适的IO或ST前置的.

Answer 3

看看这个,以便更明智地选择应该使用的内容.

但简单的说法是,如果你想要相当于C++向量,请使用Data.Vector.