遅延評価のリストを作る

Haskell Python

データ構築子はただの関数じゃないのか？

いや、関数なのは別に構わないのだけど、リストを返す関数にしてしまってはいけないと思う。それじゃ「(呼ぶ前の)未評価の状態」と「(読んだ後の)リスト全部ができあがっている状態」の2つの状態しか取れない。実際には「頭1個だけ評価済み」「頭2個だけ評価済み」…と無数の状態があるので、これが全部関数に分かれている必要がある。

というわけでまず「評価前の状態(Thunk)」と「評価後の値」を表現するクラスを作ってみた。Thunkのforceを呼ぶと結果がValueになるまで評価を繰り返す。

>>> class Value(object):
    def __init__(self, value):
        self.value = value
    def eval(self):
        return self
    def force(self):
        return self

>>> class Thunk(object):
    value = None
    def __init__(self, func):
        self.func = func
    def eval(self):
        return self.func()
    def force(self):
        x = self
        while x.value == None:
            x = x.eval()
        return x

次に、遅延したincと遅延したconsと遅延したmapを作る。

>>> def d_inc(x):
    return Thunk(lambda:
        Value(x.force().value + 1))

>>> def d_cons(car, cdr):
    return Thunk(lambda:
        Value([car, cdr]))

>>> def d_map(f, xs):
    return Thunk(lambda:
        d_cons(
            f(xs.force().value[0]), # (f (car xs))
            d_map(f, xs.force().value[1]))) # (map f (cdr xs))

さぁ、これで無限リストができるはずだ。

>>> inflist = d_cons(Value(1), d_map(d_inc, inflist))

NameError: name 'inflist' is not defined

あれ？
あ、そうかそうか。これも遅延させなきゃダメだ。

>>> inflist = Thunk(lambda:
        d_cons(Value(1), d_map(d_inc, inflist)))
>>> inflist
<__main__.Thunk object at 0x01497B90>

できた。
carを取ってみる。

>>> inflist.force()
<__main__.Value object at 0x014977D0>
>>> inflist.force().value
[<__main__.Value object at 0x014978B0>, <__main__.Thunk object at 0x01497530>]
>>> inflist.force().value[0].force().value
1

うんうん、できている。cdrとcdarとcddarも取ってみよう。

>>> inflist.force().value[1].force().value
[<__main__.Thunk object at 0x01497510>, <__main__.Thunk object at 0x01497BF0>]
>>> inflist.force().value[1].force().value[0].force().value
2
>>> inflist.force().value[1].force().value[1].force().value[0].force().value
3

ちゃんと無限リストになっていることが確認できた。

        • -

!!も作ってみた

>>> def car(xs):
	return xs.force().value[0]

>>> def cdr(xs):
	return xs.force().value[1]

>>> car(cdr(cdr(inflist)))
<__main__.Thunk object at 0x01497E30>
>>> car(cdr(cdr(inflist))).force().value
3
>>> def get(xs, i):
	if i == 0:
		return car(xs)
	return get(cdr(xs), i - 1)

>>> get(inflist, 5)
<__main__.Thunk object at 0x0149D250>
>>> get(inflist, 5).force().value
6
        • -

フィボナッチ数列を作ってみた。

>>> def zipWith(f, xs, ys):
    return Thunk(lambda:
        d_cons(
            f(car(xs), car(ys)), # (f (car xs) (car ys))
            zipWith(f, cdr(xs), cdr(ys))))

>>> def d_add(x, y):
    return Thunk(lambda:
        Value(x.force().value + y.force().value))

>>> fib = Thunk(lambda:
        d_cons(Value(1),
           d_cons(Value(1),
              zipWith(d_add, fib, cdr(fib)))))

>>> get(fib, 0).force().value
→無限ループ

うまく行かなかった。なんでうまく行かなかったのかは後で考える。

        • -

答え

-   zipWith(d_add, fib, cdr(fib)))))
+   Thunk(lambda: zipWith(d_add, fib, cdr(fib))))))

thunkが足りなかった。fib = Thunk(...)の中で、遅延されることなくfibが呼ばれてしまっていることが問題。fibの1回目の評価のタイミングでfibの評価が走ってしまうため無限ループになっていた。

for i in range(7):
    print get(fib, i).force().value,
# 1 1 2 3 5 8 13

できたできた。