読者です 読者をやめる 読者になる 読者になる

YAMAGUCHI::weblog

土足で窓から失礼いたします。今日からあなたの息子になります。 当年とって92歳、下町の発明王、エジソンです。

ジェネレータを用いた再帰関数に関する考察

Python

相変わらずジェネレータではまってるわけです。今回は自分で実装する際に詰まったところ。
ジェネレータを使って再帰関数を作るというのは、心持ちとしては関数型言語の遅延評価を利用した無限リスト表現なんかと通ずるところがあると勝手に思ってるわけですが、その実装の前にまずは普通の再帰関数を書いてみたわけです。

def test(query):
    if len(query) == 0:
        return
    else:
        print query
        test(query[1:])

ここでたとえば test("hoge") なんてやると結果は

hoge
oge
ge
e

なんてなるわけです。test()をジェネレータを使って実装するとどうなるかというと

def test(query):
    if len(query) == 0:
        return
    else:
        yield query # ここでyield文
        for q in test(query[1:]): # for-loopを使う
            yield q

こんな感じでしょうか。これを実行するときは

for a in test("hoge")
    print a

なんていう具合で実行して先ほどと同様の結果を得ます。
さて、ここで何ではまったかというと、上のtest()の実装のなかでなぜforを使わなければならないのかというところでしばらく考えてしまったわけです。たとえば

def test(query):
    if len(query) == 0:
        return
    else:
        yield query
        while 1: # これをやるとおかしくなる(無限ループ)
            yield test(query[1:]).next()

こんなのはなぜだめなんだろうと考えてしまった訳です。これを実行すると

hoge
oge
oge
oge
(以下無限ループ)

となるわけですがこれはなぜか。ここで前回書いた記事を思い出してみます。

そもそもジェネレータというのはイテレータな訳です。だからtest()それ自体はイテレータと考えます。そしてnext()を呼ぶと、イテレータを次へ進めると同時に動かす前に指していた実体を返してくれるわけです。そして肝心なのはジェネレータでは内部状態を保存しているということです。
3番目の例の場合、test(query[1:]).next()というのは最初にtest()を呼び出したときのwhile内のスコープで完結しているので値が変化しないのではないか。
一方でforを使った場合では、forはinの後で呼び出しているイテレータを進めると同時に値は進めている。そして再帰的に呼び出されたジェネレータはまたforがあるためイテレータを進め…というのを繰り返すためちゃんと再帰になっているという寸法です。
どうもだまして理解をしているため、きちんと調べてちゃんと理解を深めたいなあ。

追記 (2008.11.18)

通りすがりさんよりいただいたコメントを元に足りない頭で考えてみました。whileでもきちんと処理をしてあげれば進みます。つまりこういうこと。

def test(query):
    i = 0
    if len(query) == 0:
        return
    else:
        yield query
        it = test(query[1:]) # whileの外でtest(query[1:])を定義
        while 1:
            print str(i) + '-----'
            yield it.next()
            i = i + 1

ちょっとわかりやすくするために、数字をインクリメントした結果を表示させてみます。途中までかみ砕くと

hoge   # test('hoge') 最初のyield
0----- # test('hoge') 1回目のループ
oge    # test('hoge')から呼ばれたtest('oge') 最初のyield
1----- # test('oge')のyeildで止まったのでtest('hoge')でインクリメントして2回目のループでのprint
0----- # test('oge')で止まったところの続き。test('oge')内のi=0に注意してprintの結果
ge # test('oge')内でのitはtest('ge')になる。それの最初のyield。
2-----
1-----
0-----
e
3-----
2-----
1-----
0-----

ちゃんとイテレータが進んでいることがわかります。さらに数字が複数回表示されているところに注意すれば、yield it.next()と呼ばれたときに、ネストしてyeild test(query[1:])が呼ばれたことが分かります。
各インクリメントの結果でる数字の各々はネストで呼び出されたジェネレータ内でのローカル変数であることに気をつければ納得のいく結果です。
一方で、whileの外にジェネレータを出さなかった場合は一番最初に呼び出したtest()内で

while 1:
    it = test(query[1:])
    yield it.next()

としてしまっていることになり、whileを展開してやれば一番最初に呼び出したtest()のスコープの中で延々とtest('oge')を行ってしまっていることになり、当然の結果となります。
ジェネレータで気をつけなければいけないのは、yieldまで進んだら、一旦動作が止まるということ。whileの中でit=test(query[1:])とした場合はどんどん最初のyeildで止まった状態のtest('oge')を生成してしまうこととなったわけです。

あー、ひとつすっきりした。通りすがりさん、ありがとうございました。