関数プログラミングのアプローチ (1)

モンテカルロ法の命令的プログラム

まずは簡単な例を考えてみることにします。
プログラミング言語は当面pythonを使います。命令型も関数型も同じ言語を使います。これは、馴染のない純粋関数型言語を使わないで説明するということの他に、関数プログラミングのアプローチとプログラミング言語の依存関係がそれほどないということを示す意図もあります。
最初の例は、SICPで出てきたモンテカルロ法のサンプルです。
任意の２つの数が互いに素である確率がとなるところから、乱数を２つとってそれが互いに素であるかというテストを何度も行ってその確率を求めてそこからπの値を推定するという問題です。

def cesaro_test ():
    return 1 == gcd(rand(), rand())

def gcd(a, b):
    while b > 0: a, b = b, a % b
    return a

テストは上に示したような内容です。乱数を２つ取得して、最大公約数が１であるかを調べます。rand()は次のように作ることができます。

# xorshift 128 bit
x, y, z, w, t = 123456789, 362436069, 521288629, 88675123, 1
def rand ():
    global x,y,z,w,t
    t=(x^(x<<11)) & 0xffffffff
    x=y & 0xffffffff
    y=z & 0xffffffff
    z=w & 0xffffffff
    w=(w^(w>>19))^(t^(t>>8)) & 0xffffffff
    return w

ここから、モンテカルロシミュレーションを行ってπを求めるプログラムが次のものです。

def main ():
    print math.sqrt(6.0 / estimate(cesaro_test, 10000))

def estimate (test, times):
    x, y = 0.0, 0.0
    for i in xrange(0,times):
        if test(): x = x + 1
        y = y + 1
    return x / y

問題は、これを関数型に変換するにはどうすればよいかということです。