Python のジェネレータ (5) - 再帰とジェネレータと Composite

Python のジェネレータ (4) - 無限リスト のつづき

1. 例

例えば、「リストの要素を 2 倍したい」とする。

リスト内包表記や map 関数を使うなら、以下のように書ける。

L = [1,2,3,4,5]

print [x*2 for x in L]
print map(lambda e: e*2, L)

 

2. for ループ

単純に、for ループでリストを走査しながら、要素を2 倍するなら、

def double(L):
    result = []
    for e in L:
        result.append(e*2)
    return result

print double(L)

これをジェネレータで置き換える。

def gDouble(L):
    for e in L:
        yield e * 2

for e in gDouble(L):
    print e

 

3. 再帰

再帰で書くと、

def rDouble(L):
    if not L: return []
    else:
        return [L[0]*2] + rDouble(L[1:])

print rDouble(L)

これをジェネレータで置き換えてみる。ジェネレータは要素をいっぺんに返さず、処理した要素ごとに返すようにする。

def grDouble(L):
    if not L: return
    else:
        yield L[0]*2
        for g in grDouble(L[1:]):
            yield g

for e in grDouble(L):
    print e

ジェネレータを再帰的に呼出すには、再帰的に適用したい部分を for に投入し (next() が呼出されるため)、その要素を yield で返す。渡された引数 L の要素がなければ、何もせず return でジェネレータを終了する。

次のように書き直すこともできる。

def grDouble(L):
    if L:
        yield L[0]*2
        for g in grDouble(L[1:]):
            yield g

 

4. Composite

ジェネレータを再帰的に呼出すことに、何かメリットがあるのだろうか？

ツリー状のノードの要素を走査するためにジェネレータが使われている例 を目にした。これを見ると、Iterator パターン 、Visitor パターン を連想する。

試しに、Composite パターン のオブジェクトに対して、その要素を走査する関数をジェネレータで定義してみる。

Composite パターン - Wikipedia via kwout

class Component:
    pass

class Composite(Component):
    def __init__(self):
        self.components = []
    def add(self, component):
        self.components.append(component)
        return self
    def __iter__(self):
        return iter(self.components)

class Leaf(Component):
    def __init__(self, val):
        self.val = val

def gComposite(composite):
    if isinstance(composite, Leaf):
        yield composite.val
    else:
        for c in composite:
            for g in gComposite(c):
                yield g

c = Composite().add(
        Leaf(100)).add(
        Leaf(200)).add(
        Composite().add(
            Leaf(1000)).add(
            Composite().add(
                Leaf(10000)).add(
            Leaf(2000))).add(
        Leaf(300)))

for e in gComposite(c):
    print e

Composite クラスの __iter__() メソッドの定義については、Python のイテレータ (3) を参照。