The Haskell 98 Report
top | back | next | contents | function index

27  乱数

Random ライブラリは擬似乱数生成を扱う。このライブラリはでは、 繰り返し同じ結果を得られるよになっている。これは指定の初期乱数生成器 を使う。動作ごとに違う結果がほしいときにはシステム初期化生成器を使う か、外部からシードを与えればよい。

このライブラリは2層に分れている。

• 核となる乱数生成器はビット列を供給する。RandomGen クラスはこの類の生成器への共通インターフェイスを供給する。

• Random クラスは乱数生成器から特定の型の値を取り出す手段を 提供する。たとえば、Rondom の Fload インスタンス は Float 型の値となることができる。

27.1  RandomGen クラスと StdGen 生成器

RandomGen クラスは乱数生成器への共通インタフェースを供給する。

  class RandomGen g where
    genRange :: g -> (Int,Int)
    next     :: g  -> (Int, g)
    split    :: g -> (g, g)
  
    -- Default method
    genRange g = (minBound,maxBound)

• genRange 演算は生成器の返す値の範囲になる。

  • もし、(a,b) = genRange g ならば a < b
  • genRange _|_ /= _|_.

  でなければならない。

  二つめの条件は getRange が引数をチェックできず、それゆえ それが返す値は、RandomGen のインスタンスによってのみ 決定されうるということを確実にするためのものである。 同様にgenRange を一度だけ読んで生成器の範囲を確定するよう な実装も可能にする。このとき、たとえば next が返した 生成器が next に渡された生成器と違う範囲をもつかもしれ ないという心配はない。

• next 操作は genRangeが返した範囲(両端を含む)で一 様に分布するInt と新しい生成器を返す。

• split 操作では 2 つの別の乱数生成器を得ることができる。 これは関数プログラムでは大変有用である(たとえば、乱数生成器を再帰 的呼び出しへ渡すような場合である)。しかしながら、split の 統計的にロバストな実装については殆どなにもなされていない。(文献 [1,4]が我々が知りえた例である)

Random ライブラリは、RandomGen クラスのインスタンス、 抽象データタイプ StdGen を提供する。

  data StdGen = ... -- Abstract
  
  instance RandomGen StdGen where ...
  instance Read      StdGen where ...
  instance Show      StdGen where ...
  
  mkStdGen :: Int -> StdGen

RandomGen クラスのインスタンス StdGen は少なくとも 30ビットの genRange

next を繰り返し使用した結果は少なくとも、[2,3] の "Minimal Standard Random Number Generator" にある統計的頑健性を有して いなければならない。split の実装について詳細に知らない場合に するべきことは、split が (a) 同一ではない (b) 上記の意 味で独立にロバストな生成器を届けるようにすることである。

StdGenの Show/Read インスタンスにより乱数 生成器の状態を保持する方法が提供されている。 read (show g) == g でなければならない。

さらに read は任意の文字列(show により生成されたも のである必要はない)を StdGen 型の値へ写像するのに使える。一 般的に StdGen の Read インスタンスは以下の性質をも つ。

• いかなる文字列に対しても成功することを保証する
• 文字列の有限部分のみを使うことを保証する
• 引数も文字列が異れば結果も違うように見える

関数 mkStdGen は、Int から生成器への写像により、初 期生成器をつくるもうひとつの方法を提供している。ここでも、変数が異れ ば異った生成器がつくられるように見える。

もちろん、プログラマは独自の RandomGen のインスタンスを提供 することができる。

実装上の警告。一見魅力的な split の実装は、

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

である。ここでは、split は 自身を返し、新たな 生成器を 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

     -- Default methods
   randoms g = x : randoms g' 
   where 
     (x,g') = random g
   randomRs = ...similar...

   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 と同じである。

  • (Char のような Bounded クラスのインスタンス であるような)限られた範囲をもつ型にたいしては、範囲は通常整数 型になる。
  • 小数型に対しては、範囲は通常、半閉区間 [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]

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

[3]

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

[4]

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

The Web site http://random.mat.sbg.ac.at/ is a great source of information.

The Haskell 98 Report
top | back | next | contents | function index
December 2002