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

遅延リスト

前回の修正で、シングルスレッド化を解消することができましたが、代わりに１つ新たな不都合が生まれました。

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

上は、前回のプログラムのmain()関数ですが、これをそれ以前のもの（下）と比べてみます。

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

一見、ほとんど同じに見えますが、後者ではestimate()関数が試行回数を受け取っているのに対し、前者では受け取っていません。前者では代わりに、試行回数分の乱数ペアのリストを生成しています。このことは、前者のestimate()関数が試行回数をコントロールすることができないということを示しています。
例えば、estimate()関数での試行回数があらかじめ決まっていなくて、必要な精度が得られるまで試行を繰り返すという実装にしたいときはどうすればよいでしょうか？後者の実装なら、estimate()関数に必要な精度を与えることで、必要な個数だけ乱数を生成して試行を繰り返すことができますが、前者の場合は何回試行すれば必要な精度が得られるかをあらかじめ知っていなければ、必要な乱数ペアのリストを与えることができません。
しかし、もし、無限の長さのリストを作ることができれば、前者のプログラムでも問題はありません。無限の長さのリストを作るには、遅延リストというデータ構造を使うことができます。
遅延リストは次のように作ることができます。

class LazyList:
    def __init__ (self, fun):
        self.undef = True
        self.fun = fun
    def __next__ (self):
        if self.undef:
            self.value = self.fun()
            self.undef = False
        return self.value

def next (x):
    return x.__next__()

def ones ():
    def f (): return 1, LazyList(f)
    return LazyList(f)

ones()関数は、[1, 1, 1, ...]という無限リストを作る関数です。次のように取り扱うことで、値を得ることができます。

>>> ls = ones()
>>> x,ls = next(ls)
>>> x
1
>>> x,ls = next(ls)
>>> x
1

next()が参照透明性を満たしていることに注意してください。ただし、LazyListはnext()関数を通してしか操作できないという前提を置いています。
[1, 2, 3, ...]という無限リストを作る関数は、次のようになります。

def integers ():
    def f (n): return n, LazyList(lambda: f(n+1))
    return LazyList(lambda: f(1))

次は、これを使って、モンテカルロ法のプログラムを書き換えますが、その前に遅延リストを扱うのに便利な関数をいくつか定義しておきます。

mapL (f,ls) : 遅延リスト ls の各要素を関数 f に適用した結果を、遅延リストとして返す
takeL (n,ls) : 遅延リスト ls の先頭から n 要素を取り出し、遅延リストとして返す
groupL (n,ls) : 遅延リスト ls を先頭から n 要素ずつの部分リストに分解し、部分リストの遅延リストを返す
forceList (ls) : 遅延リスト ls を、普通のリストに変換して返す

def mapL (fun, ls):
    def f (ls):
        v = next(ls)
        if v:
            x,ls = v
            return fun(x), LazyList(lambda: f(ls))
        else:
            return v
    return LazyList(lambda: f(ls))

def takeL (n, ls):
    def f (n,ls):
        if n <= 0:
            return None
        v = next(ls)
        if v:
            x,ls = v
            return x, LazyList(lambda: f(n-1,ls))
        else:
            return v
    return LazyList(lambda: f(n,ls))

def groupL (n, ls):
    def f (ls):
        ret = []
        for i in xrange(0,n):
            v = next(ls)
            if v:
                x, ls = v
                ret.append(x)
            elif ret:
                return ret, LazyList(lambda: v)
            else:
                return v
        return ret, LazyList(lambda: f(ls))
    return LazyList(lambda: f(ls))

def forceList (ls):
    ret = []
    v = next(ls)
    while v:
        x,ls = v
        ret.append(x)
        v = next(ls)
    return ret