2

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

据此：迭代或惰性水库采样惰性水库采样是不可能的，除非您提前知道人口规模。

即便如此，我还是不明白为什么（从操作上讲）下面的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

这显示了函数在列表上迭代时的结果。使用协程抽象，也许可以代替print ea yield e，其余的计算可以作为延续。

4

1 回答 1

4

问题在于 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)

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

于 2015-11-25T16:30:04.113 回答