在Haskell中实现可变数组

Question

我有以下（命令式）算法，想在Haskell中实现：

给定一系列成对出现的数字[(e0,s0), (e1,s1), (e2,s2),...,(en,sn)]，其中“e”和“s”都是自然数，不一定不同，每个时间步骤会随机选择一个元素，假设为(ei,si)，并基于(ei,si)的值构建一个新元素添加到序列中。

如何在Haskell中高效地实现这个算法？需要随机访问，因此列表不适合，而每次只添加一个元素则数组也不适合，据我所知。

谢谢。

- dsign

---

根据（ei，si）的值，构建一个新元素并将其添加到序列中……什么？为什么要向序列附加额外的元素？这让我想到可能有更好、更纯粹的重构此算法的方法。当选择元素时，它们是否被消耗？如果是这样，那么为什么不用新元素替换旧元素呢？（数组对此很有效） - Dan Burton

@丹：这是一个“优先连接”算法的一部分，其中一个事件是一对，每个部分都可以是新东西（即下一个数字）或旧有物品。如果是旧货，则选择任何特定值的概率与其先前出现次数成比例。因此，给定序列[(1,1)，(1,2)，(2,3)]，那么下一对将有第一个元素为1->2/3，2->1/3的可能性，第二个元素为1->1/3，2->1/3和3->1/3的可能性。在这里进行采样最简单的方法就是从序列中随机取两个元素并复制它们的组件...至少我是这么认为的。 - dsign

Answer 1

我建议根据你的需求使用Data.Set或Data.Sequence。特别是后者，它提供了对数级索引查找（与列表的线性查找相比）和在任一端点上的O(1)追加。

- ivanm

---

时光倒流四年，我意识到对数复杂度有时是一个小代价...;-) - dsign

Answer 2

“需要一次追加一个元素会使数组变得糟糕”，从算法上来看，你可能需要一个动态数组（也称为向量、数组列表等），它的平摊时间复杂度为O（1）以添加一个元素。我不知道Haskell有没有这样的实现，它也不是一个非常“函数式”的数据结构，但在某种状态单子中，在Haskell中肯定可以实现它。”

- newacct

---

是的，这正是我所想的。 - dsign

实际上，如果没有将O(1)随机访问数组作为原语提供给您，就不可能实现它们。状态单子可以帮助您抽象出数组实现，但无法帮助您编写一个。 - Rotsor

@Rotsor：但是 GHC 有数组，可变的数组，所以我应该能够使用 ST monad、STRef 和这些数组来实现一些有状态的数组列表……我想不出更好的方法了。最终，我应该能够获得摊销 O(1)…… - dsign

好的。这是最接近的答案。感谢所有使用集合的建议，但我认为如果可以使用可增长数组来完成，就没有必要牺牲性能。感谢所有提交答案的人。 - dsign

Answer 3

如果您大致知道需要多少个元素，那么可以创建一个“稀疏”的数组，然后根据需要将元素放入其中。可以使用以下类似的方式表示这个新数组：

data MyArray = MyArray (Array Int Int) Int

（其中最后一个Int表示数组中使用了多少个元素）

- Ankur

Answer 4

如果您真的需要停止和启动调整大小，可以考虑使用simple-rope包以及StringLike实例来处理类似于Vector的东西。特别是，这可能适用于您从大型数组开始并且对相对较小的添加感兴趣的情况。

话虽如此，在绳索的块中添加单个元素仍可能会引起大量复制。您需要尝试您的具体情况，但您应该准备使用可变向量，因为您可能不需要纯中间结果。

如果您可以一次构建数组并且只需要所描述的索引行为，则以下内容可能足够：

import Data.Array.IArray

test :: Array Int (Int,Int)
test = accumArray (flip const) (0,0) (0,20) [(i, f i) | i <- [0..19]]
  where f 0 = (1,0)
        f i = let (e,s) = test ! (i `div` 2) in (e*2,s+1)

- Anthony

---

哇，有人真的看了我的simple-rope包！在机场度过的两个小时没有白费 :) - jkff

Answer 5

借鉴ivanm的意见，我认为集合是解决这个问题的最佳方法。

import Data.Set as Set
import System.Random (RandomGen, getStdGen)

startSet :: Set (Int, Int)
startSet = Set.fromList [(1,2), (3,4)] -- etc. Whatever the initial set is

-- grow the set by randomly producing "n" elements.
growSet :: (RandomGen g) => g -> Set (Int, Int) -> Int -> (Set (Int, Int), g)
growSet g s n | n <= 0    = (s, g)
              | otherwise = growSet g'' s' (n-1)
    where s' = Set.insert (x,y) s
          ((x,_), g')  = randElem s g
          ((_,y), g'') = randElem s g'

randElem :: (RandomGen g) => Set a -> g -> (a, g)
randElem = undefined

main = do
    g <- getStdGen
    let (grownSet,_) = growSet g startSet 2
    print $ grownSet -- or whatever you want to do with it

这假设randElem是一种有效的、可定义的方法，用于从一个集合中选择一个随机元素。(我在这个SO问题中询问了关于这种方法的有效实现)。我在编写这个实现时意识到一件事情，那就是它可能不适合你的需求，因为Set不能包含重复的元素，而我的算法没有办法给出多次出现在列表中的配对额外的权重。

- Dan Burton

---

如果需要多个元素，可以在Hackage上使用multiset包（它在底层使用Map a Int），并且您想要使用类似于集合的数据结构。 - ivanm