Последовательности выборки случайных чисел в Haskell

Ответ 1

Я думаю, что выполнение ваших вычислений, требующих случайных чисел внутри монады, которая абстрагирует генератор, является самой чистой. Вот как выглядит этот код:

Мы собираемся поместить экземпляр StdGen в монаду штата, а затем предоставить немного сахара над монадой-монадом и установить метод, чтобы дать нам случайные числа.

Сначала загрузите модули:

import Control.Monad.State (State, evalState, get, put)
import System.Random (StdGen, mkStdGen, random)
import Control.Applicative ((<$>))

(Обычно я бы, вероятно, не указывал импорт, но это позволяет легко понять, откуда исходит каждая функция.)

Затем мы определим наши "вычисления, требующие случайных чисел" monad; в этом случае - псевдоним для State StdGen, называемый R. (Потому что "Random" и "Rand" уже означают что-то еще.)

type R a = State StdGen a

Способ R работает: вы определяете вычисление, требующее поток случайных чисел (монадическое "действие" ), а затем вы "запускаете его" с помощью runRandom:

runRandom :: R a -> Int -> a
runRandom action seed = evalState action $ mkStdGen seed

Это принимает действие и семя и возвращает результаты действия. Как и обычные evalState, runReader и т.д.

Теперь нам просто нужен сахар вокруг государственной монады. Мы используем get для получения StdGen, и мы используем put для установки нового состояния. Это означает, что для получения одного случайного числа мы будем писать:

rand :: R Double
rand = do
  gen <- get
  let (r, gen') = random gen
  put gen'
  return r

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

Это "действие", которое можно запустить с помощью runRandom, поэтому попробуйте:

ghci> runRandom rand 42
0.11040701265689151                           
it :: Double     

Это чистая функция, поэтому, если вы запустите ее снова с теми же аргументами, вы получите тот же результат. Примесь остается внутри "действия", которое вы передаете runRandom.

Во всяком случае, ваша функция требует пары случайных чисел, поэтому давайте напишем действие для создания пары случайных чисел:

randPair :: R (Double, Double)
randPair = do
  x <- rand
  y <- rand
  return (x,y)

Запустите это с помощью runRandom, и вы увидите два разных числа в паре, как и следовало ожидать. Но заметьте, что вам не приходилось поставлять "rand" с аргументом; потому что функции чисты, но "rand" - это действие, которое не обязательно должно быть чистым.

Теперь мы можем реализовать вашу функцию normals. boxMuller, как вы его определили выше, я просто добавил подпись типа, чтобы я мог понять, что происходит без чтения всей функции:

boxMuller :: Double -> Double -> (Double, Double) -> Double
boxMuller mu sigma (r1,r2) =  mu + sigma * sqrt (-2 * log r1) * cos (2 * pi * r2)

При выполнении всех вспомогательных функций/действий мы можем, наконец, написать normals, действие из 0 аргументов, которое возвращает (лениво сгенерированный) бесконечный список нормально распределенных парных чисел:

normals :: R [Double]
normals = mapM (\_ -> boxMuller 0 1 <$> randPair) $ repeat ()

Вы также можете написать это менее сжато, если хотите:

oneNormal :: R Double
oneNormal = do
    pair <- randPair
    return $ boxMuller 0 1 pair

normals :: R [Double]
normals = mapM (\_ -> oneNormal) $ repeat ()

repeat () дает монадическое действие бесконечный поток ничто, чтобы вызвать функцию с (и это делает результат нормалей бесконечно длинным). Я изначально написал [1..], но я переписал его, чтобы удалить бессмысленный текст 1 из текста программы. Мы не работаем с целыми числами, нам просто нужен бесконечный список.

Во всяком случае, это так. Чтобы использовать это в реальной программе, вы просто выполняете свою работу, требующую случайных нормалей внутри действия R:

someNormals :: Int -> R [Double]
someNormals x = liftM (take x) normals

myAlgorithm :: R [Bool]
myAlgorithm = do
   xs <- someNormals 10
   ys <- someNormals 10
   let xys = zip xs ys
   return $ uncurry (<) <$> xys

runRandom myAlgorithm 42

Применяются обычные методы программирования монадических действий; сохраните как можно меньше вашего приложения в R, и все будет не слишком беспорядочно.

О, а на другом: лень может "просачиваться" за границу монады чисто. Это означает, что вы можете написать:

take 10 $ runRandom normals 42

и он будет работать.

Ответ 2

Список, который вы получаете из randoms, бесконечен, и когда вы используете конечный префикс, вам не нужно выбрасывать бесконечный хвост. Вы можете передать случайные числа в качестве дополнительного параметра и вернуть неиспользуемые случайные числа в качестве дополнительного результата, или вы можете припарковать бесконечную последовательность случайных чисел в государственной монаде.

Аналогичная проблема возникает для компиляторов и других кодов, которые нуждаются в поставке уникальных символов. Это просто настоящая боль в Haskell, потому что вы выполняете потоковое состояние (генератора случайных чисел или генератора символов) по всему коду.

Я сделал рандомизированные алгоритмы как с явными параметрами, так и с монадой, и ни один из них не является действительно удовлетворительным. Если вы наберете монады, у меня, вероятно, есть небольшая рекомендация использовать государственную монаду, содержащую бесконечный список случайных чисел, которые еще не были использованы.

Ответ 3

Вы также можете обойти проблему, используя newStdGen, и каждый раз вы получите различное семя (практически).