ジェネレータは、再帰を簡単に書くことができるPython独特な機能です。yieldというキーワードを用います。例えば、関数を呼ぶたびに1,2,3,...という無限の値を返していく関数を書く例を考えてみます。

def natural_number():
    i = 1
    while True:
        yield i
        i += 1

for x in natural_number():
    if x > 10: break
    print x

natural_number()の定義で、returnではなくyieldを呼んでいます。まずiは1から始まるのですが、1をyieldしたのち、再びnatural_number()が呼ばれると、処理はそこから続行され、次は2がyieldされます。 (普通にreturn iと書いてあると、二回目に呼ばれたときも1が返ります) これにより、1,2,3...と増えていく数字が返されます。 for文のinのあとにこれを書くと、1から順番にxに値が代入されます。

再帰的にジェネレータを使う

再帰的にジェネレータを使うとき、ジェネレータそのものをyieldしてはいけない。例として、abcを使った全ての3文字の単語(aaa, aab,...)を返すジェネレータを考えてみる。 hoge()というのはA, S, target3つの引数を取る。Aは3文字の並び、Sは候補、targetは何文字目まで確定したか。

S = ['a','b','c']
n=3

def hoge(A,S,target=0):
    if target == n: # 最後の文字まで埋まったら
        yield A     # それを返す
        return
    for s in S:
        A[target] = s
        for h in hoge(A,S,target+1):
            yield h

A = []
for i in range(n):
    A.append(S[0])

h = hoge(A,S)
for a in hoge(A,S):
    print a

ここで、hoge()の中で

yield hoge()

ではだめで、

for h in hoge():
   yield h

としなくてはいけない。

ジェネレータを使ったDAGのなぞりのサンプル。

Node.nextNode()がジェネレータです。

# An example of dag tracing

class Node:
    def __init__(self, name, nexts):
        self.name  = name
        self.nexts = nexts


    def nextNode(self, nodes):
        yield self.name
        for node in self.nexts:
            for nnode in nodes[node].nextNode(nodes):
                yield nnode


    def registerMe(self, nodes):
        if self.name in nodes:
            raise "Already registered"
        nodes[self.name] = self
            

class DAG:
    def __init__(self):
        self.nodes = {}

        
    def trace(self):
        appeared = []
        for root in self.roots:
            for node in nodes[root].nextNode(self.nodes):
                if node in appeared: break
                appeared.append(node)
                print node


    def setSample(self):
        Node('na', ['nb']).registerMe(self.nodes)
        Node('nb', ['nd', 'ne']).registerMe(self.nodes)
        Node('nc', ['nb']).registerMe(self.nodes)
        Node('nd', ['nf', 'ng']).registerMe(self.nodes)
        Node('ne', []).registerMe(self.nodes)
        Node('nf', []).registerMe(self.nodes)
        Node('ng', []).registerMe(self.nodes)

        self.roots = ['na', 'nc']


dag = DAG()
dag.setSample()
dag.trace()

ジェネレーター (yield)

きほん

再帰的にジェネレータを使う

ジェネレータを使ったDAGのなぞりのサンプル。