Бесконечный/ленивый отбор проб из резервуара в Haskell

Я попытался реализовать простую выборку из резервуара в Haskell, следуя http://jeremykun.com/2013/07/05/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

To:

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

Это показывает результаты, когда функция выполняет итерацию по списку. Используя абстракцию сопрограммы, возможно, вместо print e может быть yield e, а остальные вычисления можно провести как продолжение.


random algorithm haskell sampling reservoir-sampling
person CMCDragonkai    schedule 25.11.2015    source источник
comment
ну, алгоритмы держат одну монету до конца (и, возможно, заменяют ее какой-то другой) - ключевой момент: до конца - поэтому вам нужно пройти весь список ... и конечно конечно, этот алгоритм зависит именно от этого, чтобы дать вам равномерное распределение   -  person Random Dev    schedule 25.11.2015
comment
Судя по тому, как это написано выше, ничего не заменяется. Это то, что меня смущало, почему пример Джереми Куна на самом деле не поддерживал какой-либо конкретный резервуар для мутаций. Так что я не понимаю вашего комментария.   -  person CMCDragonkai    schedule 25.11.2015
comment
Я говорю об алгоритме отбора проб из резервуара, как описано в вашей первой ссылке - кажется, вы удалили жизненно важные части - но ваш не работает, потому что вы пытаетесь материализовать полный список - почему бы вам не попробовать и сделайте это без IO (передайте генератор с помощью randomR ?   -  person Random Dev    schedule 25.11.2015
comment
На практике ваш sampleReservoir можно сделать достаточно ленивым; однако у него неправильное обозначение. Он не создает элемент, нарисованный случайным образом из входного списка. Действительно, он создает список, а не элемент; но даже список, который он производит, не содержит равномерно распределенных значений.   -  person Daniel Wagner    schedule 25.11.2015

Ответы (1)


arrow_upward
4
arrow_downward

Проблема в том, что монада IO поддерживает строгую последовательность действий. Запись 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)

Очевидно, это позволит чередовать действия ввода-вывода, но, поскольку все, что вы делаете, — это генерация случайных чисел, это не должно иметь значения. Однако это решение не очень удовлетворительно; правильное решение - несколько реорганизовать код. Вы должны сгенерировать бесконечный список случайных чисел, а затем использовать этот бесконечный список (лениво) с помощью 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)

Кроме того, я не уверен в правильности алгоритма, поскольку он всегда сначала возвращает первый элемент входного списка. Не очень случайно.

person user2407038    schedule 25.11.2015
comment
в этой версии опора. вернуть первое чрезвычайно велико (случайное число в [0,1] ‹ 1) ;) - person Random Dev; 25.11.2015
comment
Это круто! Да, я согласен, я немного настороженно отношусь к этому алгоритму, он кажется странным, поскольку вероятность начинается с высокой и становится очень низкой. - person CMCDragonkai; 25.11.2015
comment
Теперь я пересмотрел этот ответ более подробно, работает ли рефакторинговая версия, потому что вместо fmapping в бесконечно вложенную структуру ввода-вывода (вынуждая строгую оценку изнутри), вместо этого у нас есть структура данных списка, которая просто содержит случайное значение, созданное IO вычисление. И каким-то образом это позволяет лениво потреблять значения ввода-вывода при деконструкции списка? - person CMCDragonkai; 27.11.2015
comment
В sampleReservoir3 нет ленивого потребления вычислений ввода-вывода. Когда вы пишете ws <- getRandomRs (0, 1 :: Double), вы получаете одно вычисление ввода-вывода, которое при выполнении создает бесконечный случайный список двойных чисел от 0 до 1. По сути, происходит то, что getRandomRs выполняет действие ввода-вывода для получения нового случайного начального числа, а затем чисто< /i> и lazily возвращает бесконечный список случайных значений, используя это начальное число. Я добавил другую эквивалентную версию функции. - person user2407038; 27.11.2015