Описание Haskell 98
наверх | назад | вперед | содержание | предметный указатель функций

---

27  Случайные числа

module Random ( RandomGen(next, split, genRange), StdGen, mkStdGen, Random( random,   randomR,  randoms,  randomRs, randomIO, randomRIO ), getStdRandom, getStdGen, setStdGen, newStdGen   ) where ---------------- Класс RandomGen ------------------------ class RandomGen g where   genRange :: g -> (Int, Int)   next     :: g -> (Int, g)   split    :: g -> (g, g) ---------------- Стандартный экземпляр класса RandomGen ----------- data StdGen = ... -- Абстрактный instance RandomGen StdGen where ... instance Read     StdGen where ... instance Show     StdGen where ... mkStdGen :: Int -> StdGen ---------------- Класс Random --------------------------- class Random a where    randomR :: RandomGen g => (a, a) -> g -> (a, g)    random  :: RandomGen g => g -> (a, g)    randomRs :: RandomGen g => (a, a) -> g -> [a]    randoms  :: RandomGen g => g -> [a]    randomRIO :: (a,a) -> IO a    randomIO  :: IO a instance Random Int     where ... instance Random Integer where ... instance Random Float   where ... instance Random Double  where ... instance Random Bool    where ... instance Random Char    where ... ---------------- Глобальный генератор случайных чисел ---------------- newStdGen    :: IO StdGen setStdGen    :: StdGen -> IO () getStdGen    :: IO StdGen getStdRandom :: (StdGen -> (a, StdGen)) -> IO a

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

Библиотека делится на два уровня:

• Ядро генератора случайных чисел обеспечивает поставку битов. Класс RandomGen обеспечивает общий интерфейс к таким генераторам.

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

27.1  Класс RandomGen и генератор StdGen

Класс RandomGen обеспечивает общий интерфейс к генераторам случайных чисел.

  class RandomGen g where
    genRange :: g -> (Int,Int)
    next     :: g  -> (Int, g)
    split    :: g -> (g, g)
  
    -- Метод по умолчанию
    genRange g = (minBound,maxBound)

• Операция genRange дает диапазон значений, возвращенный генератором.

  Требуется, чтобы:

  • Если (a,b) = genRange g, то a < b.
  • genRange _|_ /= _|_.
  Второе условие гарантирует, что genRange не может проверять свой аргумент, и следовательно значение, которое он возвращает, можно определить только посредством экземпляра класса RandomGen. Это, в свою очередь, позволяет реализации выполнять один вызов genRange, чтобы установить диапазон генератора, не касаясь того, что генератор, возвращенный (скажем) next, мог бы иметь диапазон, отличный от диапазона генератора, переданного next.

• Операция next возвращает Int, который равномерно распределен в диапазоне, возвращенном genRange (включая обе конечные точки), и новый генератор.

• Операция split позволяет получить два независимых генератора случайных чисел. Это очень полезно в функциональных программах (например, при передаче генератора случайных чисел в рекурсивных вызовах), но очень мало работы было сделано над статистически надежными реализациями split ([ 1,4 ] --- единственные примеры, о которых мы знаем).

Библиотека Random предоставляет один экземпляр RandomGen --- абстрактный тип данных StdGen:

  data StdGen = ... -- Абстрактный
  
  instance RandomGen StdGen where ...
  instance Read      StdGen where ...
  instance Show      StdGen where ...
  
  mkStdGen :: Int -> StdGen

Экземпляр StgGen класса RandomGen имеет genRange по крайней мере 30 битов.

Результат повторного использования next должен быть по крайней мере таким же статистически надежным, как "Минимальный стандартный генератор случайных чисел", описанный [ 2,3 ]. До тех пор, пока нам больше ничего неизвестно о реализациях split, все, чего мы требуем, --- чтобы split производил генераторы, которые являются: (a) не идентичными и (b) независимо надежными в только что данном смысле.

Экземпляры Show/Read класса StdGen обеспечивают примитивный способ сохранить состояние генератора случайных чисел. Требуется, чтобы read (show g) == g.

Кроме того, read можно использовать для отображения произвольной строки (необязательно порожденной show) на значение типа StdGen. Вообще, экземпляр read класса StdGen обладает следующими свойствами:

• Он гарантирует, что завершится успешно для любой строки.
• Он гарантирует, что потребит только конечную часть строки.
• Различные строки аргумента, вероятно, приведут к различным результатам.

Функция mkStdGen обеспечивает альтернативный способ создания начального генератора, посредством отображения Int в генератор. Опять, различные аргументы, вероятно, должны породить различные генераторы.

Программисты могут, конечно, поставлять свои собственные экземпляры класса RandomGen.

Предупреждение о реализациях. Внешне привлекательная реализация split выглядит так:

  instance RandomGen MyGen where
    ...
    split g = (g, variantOf g)

Здесь split возвращает сам g и новый генератор, полученный из g. Но теперь рассмотрим эти два предположительно независимых генератора:

  g1 = snd (split g)
  g2 = snd (split (fst (split g)))

Если split искренне поставляет независимые генераторы (как указано), то g1 и g2 должны быть независимы, но на самом деле они оба равны variantOf g. Реализации вышеупомянутого вида не отвечают требованиям спецификации.

27.2  Класс Random

Имея в собственном распоряжении источник поставки случайных чисел, класс Random позволяет программисту извлекать случайные значения разнообразных типов:

class Random a where
   randomR :: RandomGen g => (a, a) -> g -> (a, g)
   random  :: RandomGen g => g -> (a, g)

   randomRs :: RandomGen g => (a, a) -> g -> [a]
   randoms  :: RandomGen g => g -> [a]

   randomRIO :: (a,a) -> IO a
   randomIO :: IO a

     -- Методы по умолчанию
   randoms g = x : randoms g' 
   where 
     (x,g') = random g
   randomRs = ...аналогично...

   randomIO        = getStdRandom random
   randomRIO range = getStdRandom (randomR range)


instance Random Int     where ...
instance Random Integer where ...
instance Random Float   where ...
instance Random Double  where ...
instance Random Bool    where ...
instance Random Char    where ...

• randomR принимает в качестве аргументов диапазон (lo,hi) и генератор случайных чисел g и возвращает случайное значение, равномерно распределенное в закрытом интервале [lo,hi] вместе с новым генератором. Если lo>hi, то поведение функции в этом случае неопределено. Для непрерывных типов нет требования, чтобы значения lo и hi были когда-либо воспроизведены в качестве случайных значений, но они могут быть использованы в этом качестве, это зависит от реализации и интервала.

• random выполняет то же самое, что и randomR, но не использует диапазон.
  • Для ограниченных типов (экземпляров класса Bounded, например, Char), диапазон обычно является целым типом.
  • Для дробных типов диапазон обычно является полузакрытым интервалом [0,1).
  • Для Integer диапазон является (произвольно) диапазон Int.

• Множественные версии, randomRs и randoms, порождают бесконечный список случайных значений и не возвращают новый генератор.

• Версии IO, randomRIO и randomIO, используют глобальный генератор случайных чисел (см. раздел 27.3).

27.3  Глобальный генератор случайных чисел

Есть единственный, неявный, глобальный генератор случайных чисел типа StdGen, который хранится в некоторой глобальной переменной, поддерживаемой монадой IO. Он инициализируется автоматически некоторым зависящим от системы способом, например, посредством использования времени дня или генератора случайных чисел в ядре Linux. Для того чтобы получить детерминированное поведение, используйте setStdGen.

  setStdGen    :: StdGen -> IO ()
  getStdGen    :: IO StdGen
  newStdGen    :: IO StdGen
  getStdRandom :: (StdGen -> (a, StdGen)) -> IO a

• getStdGen и setStdGen соответственно возвращают и устанавливают глобальный генератор случайных чисел.

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

• getStdRandom использует указанную функцию, чтобы получить значение из текущего глобального генератора случайных чисел, и обновляет глобальный генератор с помощью нового генератора, возвращенного функцией. Например, rollDice возвращает случайное целое число между 1 и 6:
  
    rollDice :: IO Int
    rollDice = getStdRandom (randomR (1,6))
  
  

Ссылки

[1]

FW Burton and RL Page, "Distributed random number generation", Journal of Functional Programming, 2(2):203-212, April 1992.

Ф.У. Бертон и Р.Л. Пейдж, "Генерация распределенных случайных чисел", Журнал "Функциональное программирование", 2 (2):203-212, апрель 1992.

[2]

SK Park, and KW Miller, "Random number generators - good ones are hard to find", Comm ACM 31(10), Oct 1988, pp1192-1201.

С.К. Парк и К.У. Миллер, "Генераторы случайных чисел --- трудно найти хорошие", Comm ACM 31 (10), октябрь 1988, стр.1192-1201.

[3]

DG Carta, "Two fast implementations of the minimal standard random number generator", Comm ACM, 33(1), Jan 1990, pp87-88.

Д.Г. Карта, "Две быстрые реализации минимального стандартного генератора случайных чисел", Comm ACM, 33 (1), январь 1990, стр.87-88.

[4]

P Hellekalek, "Don't trust parallel Monte Carlo", ACM SIGSIM Simulation Digest 28(1), pp82-89, July 1998.

П. Хеллекалек, "Не доверяйте параллельному методу Монте-Карло ", ACM SIGSIM Simulation Digest 28 (1), стр.82-89, июль 1998.

Web-cайт http://random.mat.sbg.ac.at/ является большим источником информации.

---

Описание Haskell 98
наверх | назад | вперед | содержание | предметный указатель функций
Декабрь 2002