Infinite/Lazy Haskell 中的水库采样

Question

我尝试在 haskell 中实现一个简单的水库采样，遵循 http://jeremykun.com/2013/07/05/reservoir-sampling/（请注意，显示的算法可能在语义上不正确）

据此：Iterative or Lazy Reservoir Sampling 懒惰的水库采样是不可能的，除非你提前知道人口规模。

即便如此，我还是不明白为什么（从操作上讲）下面的 sampleReservoir 不适用于无限列表。懒惰到底在哪里被打破？

import System.Random (randomRIO)

-- equivalent to python's enumerate
enumerate :: (Num i, Enum i) => i -> [e] -> [(i, e)]
enumerate start = zip [start..]

sampleReservoir stream = 
    foldr 
        (\(i, e) reservoir -> do 
            r <- randomRIO (0.0, 1.0) :: IO Double
                              -- randomRIO gets confused about 0.0 and 1.0
            if r < (1.0 / fromIntegral i) then
                fmap (e:) reservoir
            else 
                reservoir) 
        (return []) 
        (enumerate 1 stream)

挑战和考验是fmap (take 1) $ sampleReservoir [1..]。

再者，如果水库抽样不能惰性化，那有什么可以接受惰性列表并产生抽样的惰性列表？

我认为必须有一种方法可以使上述函数在输出中也变得惰性，因为我可以更改它：

if r < (1.0 / fromIntegral i) then
    fmap (e:) reservoir
else

收件人：

if r < (1.0 / fromIntegral i) then
    do 
        print e
        fmap (e:) reservoir

这显示了函数迭代列表时的结果。使用协程抽象，也许可以有一个 yield e 而不是 print e，其余的计算可以作为一个延续。

Answer 1

问题在于 IO monad 在操作之间保持严格的顺序。写入 fmap (e:) reservoir 将首先执行与 reservoir 关联的所有效果，如果输入列表是无限的，那么它将是无限的。

我能够通过自由使用 unsafeInterleaveIO 来解决这个问题，它允许你打破 IO 的语义：

sampleReservoir2 :: [e] -> IO [e]
sampleReservoir2 stream = 
    foldr 
        (\(i, e) reservoir -> do 
            r <- unsafeInterleaveIO $ randomRIO (0.0, 1.0) :: IO Double -- randomRIO gets confused about 0.0 and 1.0
            if r < (1.0 / fromIntegral i) then unsafeInterleaveIO $ do
                rr <- reservoir
                return (e:rr)
            else 
                reservoir) 
        (return []) 
        (enumerate 1 stream)

显然，这将允许 IO 操作的交错，但由于您所做的只是生成随机数，所以这无关紧要。但是，这个解决方案不是很令人满意；正确的解决方案是稍微重构您的代码。您应该生成一个无限的随机数列表，然后使用 foldr:

（懒惰地）使用该无限列表

sampleReservoir3 :: MonadRandom m => [a] -> m [a]
sampleReservoir3 stream = do
  ws <- getRandomRs (0, 1 :: Double) 
  return $ foldr 
     (\(w, (i, e)) reservoir -> 
        (if w < (1 / fromIntegral i) then (e:) else id) reservoir
     ) 
     []
     (zip ws $ enumerate 1 stream)

这也可以（等价地）写成

sampleReservoir4 :: [a] -> IO [a] 
sampleReservoir4 stream = do
  seed <- newStdGen 
  let ws = randomRs (0, 1 :: Double) seed 
  return $ foldr 
     (\(w, (i, e)) reservoir -> 
        (if w < (1 / fromIntegral i) then (e:) else id) reservoir
     ) 
     []
     (zip ws $ enumerate 1 stream)

顺便说一句，我不确定算法的正确性，因为它似乎总是 return 输入列表的第一个元素。不是很随意。

Infinite/Lazy Haskell 中的水库采样

Infinite/Lazy Reservoir Sampling in Haskell

random

algorithm

haskell

sampling

reservoir-sampling