Описание библиотеки Haskell 98: Случайные числа Описание 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 имеет дело со стандартной задачей генерации псевдослучайных чисел. Библиотека делает возможным генерацию повторных результатов, посредством старта с указанного начального случайного числа генератора, или получения различных результатов при каждом выполнении, посредством использования инициализируемого системой генератора или предоставления случайного значения из некоторого другого источника.

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

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)

Библиотека 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 ...

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

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

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

Ссылки

[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