在Haskell中增长数组

Question

我有以下(命令性)算法,我想在Haskell中实现:

给定一系列对[(e0,s0),(e1,s1),(e2,s2),...,(en,sn)],其中"e"和"s"部分都是自然数,不一定不同的是,在每个时间步骤中随机选择该序列的一个元素,假设(ei,si),并且基于(ei,si)的值,构建新元素并将其添加到序列中.

如何在Haskell中有效地实现这一点？对于列表来说,随机访问的需求会变得很糟糕,而据我所知,一次追加一个元素的需要会使阵列变坏.

提前致谢.

Answer 1

我建议使用Data.Set或者Data.Sequence,取决于你需要它.后者特别为您提供对数索引查找(与列表的线性对比)和在任一端附加的O(1).