Concurrent Clean : 乱数ライブラリ
id:lethevert:20051230:p1
id:lethevert:20060106:p1
MersenneTwisterは、遅延ストリームを使った擬似乱数の生成ライブラリだけれど、これを使うためには、乱数のシードを用意しなければいけないのですが、これを簡単に取得する方法がなかった。2005/12/30のコメントにあるように、「*World」を用意すれば、取得する方法があるのだけれど、これは面倒だ。
randSeed
なので、randSeedという関数を用意した。一度、大域定グラフに値を保存するようにして、実行中は常に同じ値を返すので、参照透過性を壊さない。これで、「*World」を使わなくても乱数シードを取得することができる。
import code from library "kernel32_library" mkseeds :: Int mkseeds = code { ccall GetTickCount "-I" } randSeed :: Int randSeed = randSeed0 randSeed0 =: mkseeds
*Random a
また、乱数を一意型を通して取得できるように、関数群を整備してみた。「*Random a」を取得するのに参照透過でないmkseed関数を読んでいるが、使いやすいように「*World」を使わなくてもよいようにしたので、参照透過性を壊してしまう可能性がある。*1
:: *Random a = Random [a] mkRandomInt :: *(Random Int) mkRandomInt = Random (genRandInt mkseeds) mkRandomReal :: *(Random Real) mkRandomReal = Random (genRandReal mkseeds) nextRand :: *(Random a) -> (!a, *(Random a)) nextRand (Random [a:r]) = (a, Random r)
*1:参照透過性を壊すと分かっているのに、どうしてこういう風にしたかというと・・・、「*World」を使わなくても上手くやる方法について、ちょっと考えてみたいと思ったのです。
SICP : Ex1.19
これは、フィボナッチ数を行列を使って高速に計算するという問題。
続きを読むSICP : Ex1.28 (番外編:乱数ライブラリについて)
id:lethevert:20060108:p1 で定義した乱数ライブラリを使って回答したのですが、これを使って、参照透過性について多少考察します。
fast_prime_pという関数の内部では、*(Random Int)を生成して、値を取り出して、*(Random Int)を破棄して、取り出した値だけを返しています。そのため、fast_prime_pは(確率は低いものの)評価するタイミングによって、違う値を返す可能性があります。
純粋関数型のConcurrent Cleanでは、遅延評価なので、このような関数は問題を起こす可能性があるのだと思っていたのだけれど、実際どういう問題が起こるのか?
例を挙げて考える
たとえば、faという関数が、毎回返す値が違うとして、次のような関数の引数として適用することを考える。
double a = a + a
faは、一回目の評価では「1」を返し、2回目の評価では「2」を返すとすると、applicative-orderの場合は、
double fa -> double 1 -> 1 + 1 -> 2
となるが、normal-orderの場合は、
double fa -> fa + fa -> 1 + 2 -> 3
となって、矛盾が発生する。
ここまではOK。でも、Concurrent Cleanの評価はもうちょっと複雑だ。つまり、こんな感じになるはず。
double fa -> a + a where a = fa -> a + a where a = 1 -> 1 + 1 -> 2
これなら矛盾は生じないはず。この点で、ちょっと考え込んでいるのだ。