素朴にエラトステネスのふるい (1)

Haskell プログラミング ～ 純粋関数型言語への誘い～ を読んでいたら、「エラトステネスのふるい」 (p15) というのがあった。

sieve (p:ps) =
  p : sieve [n|n <- ps, n ‘mod‘ p /= 0]

Python で真似するなら、

def sieve(L):
    if not L: return []
    else:
        return [L[0]] + sieve([x for x in L[1:] if  x % L[0] != 0])

(ただし、L は有限のリスト)

 

素数

エラトステネスの篩 – Wikipedia によると、

素数判定法の一種で、指定された整数以下の全ての素数を発見するための単純なアルゴリズムである。

え～ (@_@;) 、こんなシンプルな表現で素数が得られるとは…。てゆうか「素数」なんて言葉何年ぶりに聞いただろうか。 ^^;

ところで、素数とは、

1とその数自身以外に正の約数がない（つまり1とその数以外のどんな自然数によっても割り切れない）、1 より大きな自然数のこと。

(素数 – Wikipedia より)

 

再帰的な定義

上記 sieve 関数は、定義の中で更に sieve 関数を適用している。苦手な再帰的な表現だ。うーむ。。。 (@_@;)

素数のリストが欲しいときは、2 以上の自然数のリストに関数を適用。これにより素数の無限リストが得られる。

primes = sieve [2..]  (同上より)

Python であれば、range(2,100) などのような有限のリストを sieve 関数に渡す。

 

部分的に考える

どのように動作するか具体的な例で考えてみる。例えば、「2 ~ 11 の自然数のリスト」に sieve 関数を適用した場合は、

sieve [2..11] = 2 : sieve [n|n <- [3..11], n `mod` 2 /= 0]

あ～  (+_+) 、再帰はいきなり見ると目が回るので部分ごとに。

まずは、リスト内包表記から。

[n|n <- [3..11], n `mod` 2 /= 0]

sieve 関数に適用したのは [2..11] のリスト。だから、ここでは「seive に適用したリストの先頭以外の要素」の中で「seive に適用したリストの先頭である 2」 で割り切れない要素をリストにしている。これが `ふるい’ にかける様子の一部を表現。

 

 

その後 `ふるい’ にかけたリストに対して更に sieve 関数を適用。ここが再帰的に関数を適用しているところで、目が回る原因。(@_@;)

sieve [n|n <- [3..11], n `mod` 2 /= 0]

言葉にすれば、

「ふるいにかける方法は、ふるいにかけたものを、更にふるいにかけること」

… と日本語にしたところで、再帰のイメージがしやすくなるわけではないか。 ^^;

 

混乱の原因

再帰の混乱の元は、再帰的に連なる呼出しをイメージしようとすることにある気がする。 (+_+) あくまでも考えるのは、連なる呼出し全体ではなく、そのスナップショット的な表現。例えば、上記のように sieve [2..11] と適用された場合、その適用された文脈でのみ動作を考える。再帰のそのまた先まで考えない。

 

具体的に、sieve[2..11] を定義するのであれば、定義は適用された引数 [2..11] に対してどのような作用をするのか考えるということ。あくまでも、一つ先の再帰を手持のコマで表現する。もう一度、以下を見ると、

sieve [n|n <- [3..11], n `mod` 2 /= 0]

再帰的に適用している対象  (リスト内包表記の中の変数) は、その文脈での「関数の適用対象」を使って表現している。

 

類似したパターン

定義の内容を続けて読んでいくと、次に、上記の再帰的な関数の適用によって生成されるリストと、先頭要素である `2’ をくっつけてリストを作成。ここでも同じく、 sieve の再帰的な適用の先の先は読まない。関数は「自分が欲しいものが既に得られた」と仮定し、「それを使ってどうしたいのか」という視点で考えると考えやすい。

2 : sieve [n|n <- [3..11], n `mod` 2 /= 0]

上記を言葉で表現するなら、

「ふるいにかける方法は、『ふるいにかけるリストの先頭』と『その先頭の要素では割り切れない要素に対して更にふるいをかけた結果』をつなげてリストにする。」

ポイントは、ふるいにかけられることによって「何」が残るのかということ。ここが自分はイメージしにくい。 (+_+) 関数が何を返し、それに対してどうしたいのか。再帰的な定義だと急に動作を想像しにくくなる気がする。

これを考えるには、関数の定義で再帰的に考えなくても明らかな部分に注目。上記の例ではリストの先頭要素である `2’ が手がかりとなる。

ところで、seive 関数の全体を眺めると、次のように再帰的に関数を適用している。

sieve リスト = リストの先頭要素 : sieve リストの先頭要素以外に対するリスト内包表記

こうやってみると全体の形が「n からはじまる数の無限リストを得る」再帰と類似しているのがわかる。

ints :: Int -> [Int]
ints n = n : ints (n+1)

ints 関数の実際の動作を考えると、例えば ints 1 なら、

1 : ints(2)
1 : 2 : ints(3)
1 : 2 : 3 : ints(4)
1 : 2 : 3 : 4 : ints(5)

再帰的に ints が適用されるごとに先頭要素がひねりだされ、前の要素にくっついていくという感じがする。適用されるごとに ints がリストを生長させているようにも見える。

sieve 関数も同様に見たてることができる。 sieve により適用されたリストの先頭がひねりだされ、リストが生長していく。再帰的に sieve 関数に適用されるリストによって、最終的に生成されるリストの内容が決定される。つまり、sieve に適用するリスト内包表記による操作がリストの要素を構成する決め手。このとき、最初にひねりだされるのが、リストの先頭要素である自明な `2’ 。

 

実際に確かめる

しかし、やはり実際に関数が定義と置き換えられていく様子を追ってみないと納得できない。 ^^;

2 : sieve [n|n <- [3..11], n `mod` 2 /= 0]
2 : sieve [3,5,7,9,11]
2 : 3 : sieve [n|n <- [5,7,9,11], n `mod` 3 /= 0]
2 : 3 : sieve [5,7,11]
2 : 3 : 5 : sieve [n|n <- [7,11], n `mod` 5 /= 0]
2 : 3 : 5 : sieve [7,11]
2 : 3 : 5 : 7 : sieve [n|n <- [11], n `mod` 7 /= 0]
2 : 3 : 5 : 7 : sieve [11]
2 : 3 : 5 : 7 : 11 : sieve [n|n <- [], n `mod` 11 /= 0]
2 : 3 : 5 : 7 : 11 : sieve []    -- ここで例外が発生

先ほど ints 関数を見たので、sieve 関数がリストの要素をゾロゾロと生み出しているように見える。 ^^;

ところで、上記では有限のリストに適用したので、例外が発生してしまった。

Prelude> sieve ([2..11])
[2,3,5,7,11*** Exception: :1:4-54: Non-exhaustive patterns in funct
ion sieve

例外が発生しないようにするには take 関数を使うか、

Prelude> take 5 $ sieve [2..]
[2,3,5,7,11]

空のリストに適用したときに空のリストを返すようにしておく。

sieve [] = []

 

Python で実装

さて、最初に Python におけるエラトステネスのふるいの実装例を挙げた。そこでは再帰的な定義をしたが、アルゴリズムとしては素朴な内容となっている。「素朴」である理由は、エラトステネスの篩 – Wikipedia のアルゴリズムの説明の中で、「ステップ 4」の一部の判定を省略しているため。

探索リストの最大値が素数リストの最大値の平方よりも小さい場合、素数リストおよび探索リストに残っている数が素数となる。

この判定をする理由については、「エラトステネスの篩い」の説明、「エラトステネスの篩いの原理」の「２．どの数の倍数を取り除くか」がわかりやすい。しかし、ここではこの判定を省略し、「素朴」に倍数を消す作業をリストの終りまで続けることにした。

 

ループを使って

はじめは、ごく普通に ループを使って実装してみる。

def sieveByHead(L):
    """ 先頭の要素で割り切れない要素のリストを返す """
    result = []
    for e in L[1:]:
        if e % L[0] != 0 :
            result.append(e)
    return result

def sieve(L):
    """ 渡されたリストの中の素数を返す """
    result = [L[0]]
    while L:
        sieved = sieveByHead(L)
        if sieved: result.append(sieved[0])
        L = sieved
    return result

print sieve(range(2,100)) 

 

上記の sieveByHead 関数をリスト内包表記で置きかえるとコンパクトになる。

def sieve(L):
    """ 渡されたリストの中の素数を返す """
    result = [L[0]]
    while L:
        sieved = [x for x in L if x % L[0] != 0]
        if sieved: result.append(sieved[0])
        L = sieved
    return result

 

ジェネレータを使って

最初に挙げた再帰的な表現だと、有限のリストにしか適用することができない。 Haskell のように無限リストを扱うには、ジェネレータで書き直す必要がある。

再掲すると、

def sieve(L):
    if not L: return []
    else:
        return [L[0]] + sieve([x for x in L[1:] if  x % L[0] != 0])

これをジェネレータに変更すると、

def sieve(L):
    head = L.next()
    yield head
    for e in sieve(x for x in L if x % head != 0):
        yield e

ジェネレータは next() の呼出しによって、対象となる要素が一つ先へ進む。ジェネレータを代入する変数 L をリストと見たてるなら、最初の next() の呼出しによって先頭の要素がなくなったとイメージするとわかりやすい。また、リスト内包表記を ジェネレータ式 で置き換えていることにも注意。

上記の関数を使うには、無限リストを生成する関数を定義して、その呼出し結果を sieve 関数に渡す。

def ints(n):
    """ n 以降の自然数の無限リスト """
    while True:
        yield n
        n += 1

primes = sieve(ints(2))
for i in range(10):
    print primes.next()

または、有限のリストであるなら、iter 関数を適用してから呼出す。

print list(sieve(iter(range(2,100))))

 

しかし…

ここまで来ても、再帰的な定義を見ると、やはりどこかイメージしきれないという感じがする。 ^^; 答えが得られた後もスッキリとしない。なぜだろう。 (+_+) 単に慣れていないのか、そもそも根本的にどこか理解の仕方が違うのだろうか？ わかっている人にとってみれば、「何を当り前のことを…」と思うのだろうけれど、その「当り前の考え方」が自分には感覚的に納得しきれないのでこだわってしまう。また、ツールとして再帰を利用することができない。

パタッ(o_ _)ｏ~†

もう一度別の角度からアプローチしていこう…。

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) を参照。

Python で flatten - ネストしたリストをフラットにする

「Python でリスト内のリストを連結」 のつづき

1. Ruby の flatten メソッドと同じ関数を書きたい

前回、Python で「リスト内のリストを結合する」処理を書いた。

Ruby で「ネストしたリストを結合する」メソッドは Array#flatten 。Ruby の flatten は、どれだけネストが深くてもフラットな配列にして返す。また、リスト内の要素のネストの深さが異なっていても、フラットにしてくれる。

irb(main):001:0> [1,[2,3,[4],5],6].flatten
=> [1, 2, 3, 4, 5, 6]

このような Ruby の flatten メソッドと同じ関数を、Python で書きたい。

 

2. ネストしたリストを平坦化する関数 flatten

「ネストしたリスト」に対する処理を書いたことがある。

• cf. Python でリストに対する再帰的な関数の適用
• ネストしたリストを受けとったときに、何もしないで返す関数

def map2(L):
    if isinstance(L, list):
        if L == []:
            return []
        else:
            return [map2(L[0])] + map2(L[1:])
    else:
        return L

print map2(L)

これを元にコードを考える。

def flatten(L):
    if isinstance(L, list):
        if L == []:
            return []
        else:
            return flatten(L[0]) + flatten(L[1:])
    else:
        return [L]

L = [1,[21,22],3,[41,[421,422],43,44],5]
print flatten(L)

参考にしたコードとの違いは、対象がリストの場合の処理。リストの先頭要素に対する、関数の呼出し部分が異なる。この関数 flatten では、返ってきた結果をリストにしていない。もし、リストにしたら、ネストした構造を保ってしまう。

リストでない場合は、要素１つのリストにして返す。これは再帰的に呼び出されたときに、呼び出し元にリストを返し、他のリストと結合させるため。

上記を実行した結果は、以下のようになる。

[1, 21, 22, 3, 41, 421, 422, 43, 44, 5]

 

3. リストに対する処理を reduce で置き換える

前回と同じように、リストの要素に対する処理を、組込み関数 reduce に置き換えて実装する。

def flatten2(L):
    if isinstance(L, list):
       return reduce(lambda a,b: a + flatten(b), L, [])
    else:
        return [L]

print flatten2(L)

 

4. ジェネレータを使って定義する

次に、ジェネレータを使って定義してみる。

Python で順列を生成するときに読んだ

• Generator for permutations, combinations, selections of a sequence « ActiveState Code

を参考にした。

def gflatten(L):
    if isinstance(L, list):
        for i in xrange(len(L)):
            for e in gflatten(L[i]):
                yield e
    else:
        yield L

print list(gflatten(L))

ジェネレータを使うと、動作のイメージがしにくい。 (+_+) なぜこれで動いているんだろう？

デバッガを利用して動作を見ると、実際に値を取得するために yield が 2 回呼出されているのが確認できる。あたかも、yield 間で値を受渡しているような感じに見える。

 

ジェネレータについて再考

これを理解するために、ジェネレータについて復習。

例えば、次の 2 つのジェネレータを作成。

• “hoge” と出力する hoge ジェネレータ
• ジェネレータを受けとると、ジェネレータを返す piyo ジェネレータ

そして、次のようなジェネレータの動作について考える。

1. piyo ジェネレータに hoge ジェネレータを渡し、
2. piyo ジェネレータから hoge ジェネレータを呼出すためには、
3. next () の呼出しを 2 回呼ばなくてはならない。

def hoge():
    yield "hoge"

def piyo(g):
    yield g

print piyo(hoge()).next().next()

 

gflatten 関数の見直し

これを前提に、上記の gflatten 関数を見直す。

次のように、一つの要素 100 があるリストに対して、gflatten関数を適用したとき、

1. [100] はリストなので、for 文において、 gflatten(100) が実行される。
2. 再帰呼出しがされたので、gflatten(100) が独立した文脈で実行される。今度は引数が値なので、 yield 100 が実行。これは、next() の呼出しで 100 が返されるジェネレータが作成されたということ。
3. gflatte(100) の呼出しに戻り、 for 文がジェネレータの next() を呼出し、e に 100 が渡される。これで next() を呼出すと 100 が返されるジェネレータが作成された。
4. 呼出し元の list 関数において、ジェネレータの next() 呼出しによって値が取り出される。

多分、このような動作かな… QQQ

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

Python のジェネレータ (3) - 数字にコンマを振る のつづき

1. 有限リストに対して有限の繰り返し

「有限のリストを走査する」ためのジェネレータは、次のように書く。関数 g は、引数としてリスト L を受け取るとする。

def g(L):
    for e in L:
        yield e

関数の中で yield が使われているので、ジェネレータが返される。これをジェネレータ関数と呼ぶ。

 

2. 無限リストに対して無限の繰り返し

関数 g の中では、与えられたリストを走査するために、for ループを利用した。 for ループの代わりに

while True

を用いて、延々と回る無限ループに置き換えると、「無限リストを対象としたイテレータを生成する」ジェネレータとなる。

例えば、

「 3 の倍数の無限リスト」

が欲しい場合、次のように書くことができる。

def m3():
    i = 0
    while True:
        i += 3
        yield i

Python では、無限リストを表現する特別な記述方法はない。その代わり、「３の倍数」を延々と計算するループを利用する。関数の中で return ではなく、yield を用いることにより、１回のループごとに呼び出し元に制御が戻る。これにより、ループが最後まで終了するのを待たずに済む。

上記のジェネレータを for 文に渡した場合、ループが止まらない。ジェネレータに対する next() の呼出し回数を指定することにより、無限ループに陥らないようにする必要がある。

例えば、「 3 の倍数の無限リスト」の先頭から 10 個要素が欲しい場合は、

g = m3()
for i in range(0,10):
    print g.next()

結果は、

3
6
9
12
15
18
21
24
27
30

 

無限リストを有限のリストと重ね合わせる

リスト内包表記を用いると、

g = m3()
print [g.next() for x in range(0,10)]

リスト内包表記で生成するのは有限のリストで、これを無限のリストと重ね合わせる。

結果は、上記と同じ要素がリストとして返ってくる。

[3, 6, 9, 12, 15, 18, 21, 24, 27, 30]

zip 関数を使うなら、

print [b for (a,b) in zip(range(0,10), m3())]

• cf. Python の zip と map の違い

 

3. ジェネレータをクラスから類推する

ジェネレータは、動作のイメージがつかみにくい。(+_+) しかし、クロージャを理解したときと同じ要領で、関数をクラスに見立てると理解しやすい。

例えば、上記の関数 m3 の場合で考える。

1. 関数名 m3 をクラス名と見立てる。
2. 変数 i は、インスタンス変数に相当する。
3. while ループは、next() によって呼出されるメソッド。呼出される度に、インスタンス変数を更新する

と見なすことができる。

 

n の倍数に一般化

上記の関数 m3 を、

「n の倍数を返すジェネレータ」

に変更する。

def m(n):
    i = 0
    while True:
        i += n
        yield i

先ほどと同じく、ジェネレータ関数 m をクラスと見なすと、引数 n を読み取り専用のインスタンス変数と見ることがでできる。

 

4. 指定した要素数を取得する関数

次に、無限リストを生成するジェネレータから、

指定した要素を取得する関数

を作ってみる。 Haskell であれば take 関数に相当する。

 

有限リストを対象にする場合

まずは、対象を有限リストで考えてみる。指定した要素の数だけリストから取得するには、

def takeL(n,L):
    result = []
    for i in range(0,n):
        result.append(L[i])
    return result

print takeL(3, [1,2,3,4,5])

リスト内包表記を使うなら、

def takeL2(n,L):
    return [L[x] for x in range(0,n)]

print takeL2(3, [1,2,3,4,5])

リスト内包表記は、必要とする分だけ要素を重ね合わせて取得するための手段として用いた。

 

ジェネレータを渡して無限リストを対象にする

有限リストの代わりに、「無限リストを生成するジェネレータ」を渡すなら、

def take(n,g):
    result = []
    for i in range(0,n):
        result.append(g.next())
    return result

print take(10, m(3))

ただし、関数 m は先に定義した「n の倍数を返すジェネレータ」を指す。

 

ジェネレータを渡し、ジェネレータが返される場合

次に、「無限リストを生成するジェネレータ」を渡したら、「有限リストを走査するためのジェネレータ」が生成される関数を定義してみる。

def gtake(n,g):
    for i in xrange(0,n):
        yield g.next()

print list(gtake(10, m(3)))
print [x for x in gtake(10, m(3))]

この関数の動作イメージは、次のように理解すれば良い。 例えば、

gtake(5, m(3))

の場合で考える。関数の呼び出しを見ると、無限リストから 5 つ要素を取得する形をとっている。しかし、実際には無限リストを生成するジェネレータから、要素を順に計算した結果を得ている。

比喩的に言えば、gtake のジェネレータにより生成されたイテレータが動くと、それに伴なって m のジェネレータが生成したイテレータも呼応するように動く。

take 関数は、実行すると、要素がリストとして返された。もし、take するリストが巨大であれば、要素数に応じたメモリが必要となる。それに対して、gtake 関数は、ジェネレータが返されるので、走査するためのメモリがあればよい。

極端な例で言えば、

「3 の倍数を 1000万個」 take 関数によって取得し、その後、10 で割り切れる数を 1 つだけ必要である

とする。 take 関数の場合、

for e in take(10000000, m(3)):
    if e % 10 == 0:
        print e
        break

「1000 万個の 3 の倍数のリスト」が生成されてから、その要素に対して 10 で割りきれるか確認することになる。

これに対して gtake 関数では、

for e in gtake(10000000, m(3)):
    if e % 10 == 0:
        print e
        break

実際には、「1000 万個の 3 の倍数のリスト」は生成されず、「 3 ~ 30 までの 3 の倍数」だけを確認して終了する。上記のコードにおいて break がなければ 1000 万個の 3 の倍数の要素を走査することになる。要素の末尾に到達せずに処理が終了するほど、gtake 関数の動作は有利となる。もし、末尾まで走査したとしても、メモリの使用量は take 関数よりも少ない。

 

5. Haskell の場合

Python で書いたコードを、Haskell で置き換えてみる。

m3 n = n : (m3 $ n+3)
-- 3 の倍数の無限リスト
m3' = m3 3

m x n = n : (m x $ n+x)
-- n の倍数の無限リスト
m' n = m n n

main = putStrLn $ show $ take 10 $ m' 3

遅延評価により、必要なときに必要なだけ処理されるので、無限リストを自然に扱える。

Python のジェネレータ (5) 再帰とジェネレータと Composite につづく…

Python で map 関数の第 2 引数を操作の対象ではなく手段として使う

操作対象としてのリスト

map 関数は、2.1 組み込み関数 によると、

map(function, list, ...)

function を list の全ての要素に適用し、返された値からなるリストを返します。

操作対象のリストがあり、それを操作する関数を定義するというイメージ。

 

例えば、リストの各要素を 2 倍したいなら、

print map(lambda x: x*2, [1,2,3,4,5])

map 関数の第 2 引数のリストに対して、第 1 引数の関数を適用する。

リスト内包表記を使うなら、(cf. Python のリスト内包表記)

print [x*2 for x in [1,2,3,4,5]]

対象のリストがあって、そこから一つずつ取り出して関数を適用する。

 

リストは「料理される側」であって、関数はそれに対する「包丁」というイメージが自分の頭に固定された。 (+_+)

 

手段としてのリスト

そういう固定観念があったので、前回「Python のジェネレータ (3)」で参考にした「数字にコンマを振る」の記事のコメントにあった map 関数の使い方を見て、なるほどと思った。なぜかと言うと、 map の第 2 引数が「関数全体の目的」に対して「手段」として使われていたから。具体的には、他のリストを参照するための手段としてのリスト。

例えば、

a = "hogepiyofuga"
print map(lambda x: a[x], [1,4,7,8])

結果は、

['o', 'p', 'o', 'f']

map 関数の第 2 引数が、他の変数を参照するための手段として使われている。 map 関数の外にある変数を、無名関数 lambda の中から参照。

リスト内包表記で書くなら、

print [a[x] for x in [1,4,7,8]]

頭が固いので、こういうイメージ、 map に対して全然わかなかった。 (+_+)

 

普通に書くとすると、対象を中心に考え、

print [e for i,e in enumerate("hogepiyofuga") if i in [1,4,7,8]]

map と filter 関数を使うならば、

print map(lambda (i,e): e,
          filter(lambda (i,e): i in [1,4,7,8],
                 enumerate("hogepiyofuga")))

 

Ruby では？

Ruby で書くなら、

str = "hogepiyofuga".split(//s)
p [1,4,7,8].map{|e| str[e]}

あ～、そうだ。これ書いていて、以前から違和感を感じていたコードの理由がなんとなくわかった。脱線してしまうが、 Ruby では 繰り返しの for が内部で呼出しているというイテレータ。例えば、ブロックを 5 回実行するには、

(0...5).each{|i| p i}

for 文の書き方に比べて感覚的にしっくり来なかった。 ( 10.times do … という書き方はしっくり来るんだけど ^^; )

繰り返しの処理を行うとき、意識の中ではブロックの中に記述されているコードが処理・関心の中心にある。繰り返す回数は、あくまでも回数をこなすためにカウントする手段に過ぎない。問題に対して脇役というイメージ。だから、その手段となっている Range オブジェクト が最初に来て、主語のように居座り、それに対して処理をお願いするという形がピンと来なかった。上記の map の使い方もイメージとしては同様に感じていたために、何か微妙な感じがしたのかな。

ついでなので、対象の方を「主」にして書くと、

result = ""
"hogepiyofuga".split(//s).each_with_index do |e,i|
  result << e if [1,4,7,8].any?{|elem| elem == i}
end
p result

あれ？思ったよりも長くなった… (@_@;) 書き方違ってるのかな？

 

lambda

ちなみに、Python の 5.11 ラムダ (lambda) によると、

ラムダ形式で作成された関数は、実行文 (statement) を含むことができないので注意してください。

代入は、「代入文 (assignment statement)」、つまり statement の一種なので (cf. 6. 単純文 (simple statement))、 lambda の中に含むことはできない。 Ruby の proc{}, lambda{} とは異なる。(cf. Ruby のブロックと Proc)

だから、次のコードを実行しようとすると、「exceptions.SyntaxError: lambda cannot contain assignment」 というエラーが表示されてしまう。

a = list("hogepiyofuga")
map(lambda x: a[x] = "X", [1,4,7,8])

まぁ、しかし上記のような目的にそんな風には書かないか ^^; 普通は、

result = ""
for i,e in enumerate("hogepiyofuga"):
    result += "X" if i in [1,4,7,8] else e
print result

 

ジェネレータを使うなら、

def g():
    for i,e in enumerate("hogepiyofuga"):
        yield "X" if i in [1,4,7,8] else e

print "".join(x for x in g())

上記のジェネレータを一般化すると、

def g2(str, L, x):
    for i,e in enumerate(str):
        yield x if i in L else e

print "".join(x for x in g2("hogepiyofuga", [1,4,7,8], "X"))

 

どうしても、 lambda の中で外の変数を変更したいなら、オブジェクトのメソッド呼出しにすればいいか～。

class StringWrapper:
    def __init__(self, str):
        self.str = str
    def __getitem__(self, key):
        return self.str[key]
    def __setitem__(self, key, value):
        self.str = self.str[:key] + value + self.str[key+len(value):]
    def set(self, key, value):
        self.__setitem__(key, value)
    def __str__(self):
        return self.str

s = StringWrapper("hogepiyofuga")

# 参照
print map(lambda x: s[x], [1,4,7,8])

# 変更 
map(lambda x: s.set(x,"X"), [1,4,7,8]) 
print s

(cf. Python で要素を添字で参照する - 特殊メソッドを使って)

しかし、もうこれは lambda を使う意味がなくなってる  … ^^; これなら StringWrapper に、先ほどのジェネレータ g2 に相当するメソッドを作って、オブジェクトに対して普通にメソッド呼出しをするよね…。

 

余談

map 関数のドキュメントを読みなおしてはじめて気がついたけれど、これって複数のリストに対して適用できるのかぁ～ (@_@)

map(function, list, ...)

… 追加の list 引数を与えた場合、 function はそれらを引数として取らなければならず、関数はそのリストの全ての要素について個別に適用されます; 他のリストより短いリストがある場合、要素 None で延長されます。

(2.1 組み込み関数 の map より)

例えば、

print map(lambda x,y: x+y, [1,2,3],[10,20,30])
print map(lambda x,y,z: x+y+z,
          [1,2,3],[10,20,30],[100,200,300])
print map(lambda *x: [a*2 for a in x],
          [1,2,3],[10,20,30],[100,200,300])

結果は、

[11, 22, 33]
[111, 222, 333]
[[2, 20, 200], [4, 40, 400], [6, 60, 600]]

function が None の場合、恒等関数であると仮定されます (同上より)

恒等関数 – Wikipedia とは、

変数を全く変えずにそのままの値で返す関数のこと。

zip 関数の説明には次のようにある。

zip() は初期値引数が None の map() と似ています。

例えば、

print map(None, [1,2,3],[10,20,30])

結果は、

[(1, 10), (2, 20), (3, 30)]

追記(2008.9.25) : 違いについては、Python の zip と map の違い参照。

Python のジェネレータ (3) - 数字にコンマを振る

Python のジェネレータ (2) のつづき

1. ジェネレータを使う方法

前回と同じく、ジェネレータを使う例を考える。

• 数字にコンマを振る (via 巡回 - 常山日記)

Python のチュートリアル 5.5.7 レシピ に、moneyfmt() という関数が書かれている。とりあえず、これは横に置いておく。

「数字にコンマを振る」ために、ジェネレータを使うことをイメージする。

1. 数をリストに見たて、末尾から 3 つずつ要素を返すジェネレータを作成。
2. そのジェネレータからリストを生成し、
3. 要素を逆順にして、
4. 最後にコンマで要素をくっつける。

実装。

def gCommaStr(num):
    result = ""
    for i,e in enumerate(reversed(str(num))):
        if not i == 0 and i % 3 == 0:
            yield result
            result = ""
        result = e + result
    yield result

print ",".join(list(reversed([x for x in gCommaStr(1234567890)])))

一応、コンマを打つ位置を可変にしておくと、

def gCommaStr2(num,n):
    result = ""
    for i,e in enumerate(reversed(str(num))):
        if not i == 0 and i % n == 0:
            yield result
            result = ""
        result = e + result
    yield result

print ",".join(list(reversed([x for x in gCommaStr2(1234567890,3)])))

 

2. 再帰を使った方法

リスト操作なので、ついでに再帰の練習もしておこう。

数が小さいときは、

1 --> 1
12 --> 12
123 --> 123

そのまま返す。

コンマがつけられる最小の数値のリストは、

1234 --> 1,234

これが再帰をするときの基本的なコンポーネントになりそうだ。

続きを考えると、

12345 --> 12,345
123456 --> 123,456
1234567 --> 1,234,567
12345678 --> 12,345,678

ぼ～っとながめていると、何となく繰返しになっている構造が見えてくる。 (@_@;) 上記の最後のパターンを見ていたら、 「2,345」 と 「5,678」 というように分割して考えれば、先ほど考えた基本的なコンポーネントが結合した形と見ることができることに気がついた。  「5」  が重複しているが、これは再帰呼出しの後に削除すればいいような感じ。 「12345」 なら、 「12」 と 「2,345」 。 「123456」 なら、 「123」 と 「3,456」 というような部分に分割できると考える。

これで数値が大きくなっても、基本的なコンポーネントとそれ以外の部分に分けて考え、関数を再帰的に適用すればいいような気がしてきた。

さて、実装～ (+_+)

def recCommaStr(L):
    if len(L) <= 3:
        return L
    elif len(L) == 4:
        L.insert(1, ","); return L
    else:
        return recCommaStr(L[:-3])[:-1] + recCommaStr(L[-4:])

num = 1234567890
print "recCommaStr(L): " + "".join(recCommaStr(list(str(num))))

引数 L は、数値を文字列にした後、リストにしたものを渡すようにした。

何も知らずにこのコードを見たら、読む気が失せるけれど ^^; 、わかっていれば再帰的な実装はやり方を素直に実装しているように感じる。

これも同じくコンマが打たれる位置を指定できるように拡張すると、

def recCommaStr2(L,i):
    if len(L) <= i:
        return L
    elif len(L) == i+1:
        L.insert(1, ","); return L
    else:
        return recCommaStr2(L[:-i],i)[:-1] + recCommaStr2(L[-(i+1):],i)

num = 1234567890
print "recCommaStr2(L,i): " + "".join(recCommaStr2(list(str(num)),3))

引数 i がコンマの位置を現わす。

 

3. 割り算で分割する方法

あ～、そうだ。数値を 1000 で割っていけば、コンマの打ちたい分の数値だけ取得できるかぁ。

def divCommaStr(num):
    result = str(num) if num < 1000 else ""
    while num > 1000:
        result = "," + str(num % 1000) + result
        num /= 1000
        if num < 1000:
            result = str(num) + result
    return result

print "divCommaStr(1234567890): " + divCommaStr(1234567890)

あれ？何かややこしい。 (+_+) こういうの考えるの苦手。脳みそ混乱してきた。 パタッ(o_ _)ｏ~†

 

コンマの位置を可変にすると、

def divCommaStr2(num, i):
    assert i > 0
    divNum = 10 ** i
    if num < divNum: return str(num)

    result = ""
    while num > divNum:
        result = "," + str(num % divNum) + result
        num /= divNum
        if num < divNum:
            result = str(num) + result
    return result


print "divCommaStr2(1234567890, 3): " + divCommaStr2(1234567890, 3)

 

4. クラスを使った方法

クラスを使って実装してみる。コンマ付きの数字を表わす CommaStr クラスを作成。コンマを付けるのは、文字列としてオブジェクトの情報を出力するときに、末尾から数値を 3 つ置きに走査する時点でつけることにした。

class CommaStr:
    def __init__(self, num, i):
        self.i = i
        self.nums = str(num)
            
    def __str__(self):
        result = ""
        for i,e in enumerate(reversed(self.nums)):
            if not i == 0 and i % self.i == 0:
                result = e + "," + result
            else:
                result = e + result
        return result

print "CommaStr(1234567890, 3):", CommaStr(1234567890, 3)

これだとクラスを使う意味があまりないなぁ。 ^^; グローバル変数と関数を組み合わせる方法と大差なし。でも、クラスで考えるというのは何となくイメージしやすい。

 

自分の好みとしては、同様にコンマ付きの数字全体を CommaStr クラスで表わし、各数字を Num クラスとする。 Num クラスには、インスタンス変数として数値とコンマをつけることができるフィールドを用意しておく。

実装。

class CommaStr2:
    def __init__(self, num, i):
        self.i = i
        self._createNums(num)

    def _createNums(self, num):
        self.nums = []
        for e in str(num):
            self.nums.append(Num(e))
        self.setComma(",")
            
    def setComma(self, comma):
        for i,e in enumerate(reversed(self.nums)):
            if not i == 0 and i % self.i == 0:
                e.comma = comma

    def __str__(self):
        return "".join(str(x) for x in self.nums)

class Num:
    def __init__(self, num, comma=""):
        self.num = num
        self.comma = comma
    
    def __str__(self):
        return str(self.num) + self.comma

print "CommaStr2(1234567890, 3):", CommaStr2(1234567890, 3)

全体は長くて効率も悪いけれど、全体の構造の見通しがよく、各メソッドはシンプルでええわぁ～。 ^^

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

Python のジェネレータ (2) - リストの走査

Python のジェネレータ (1) - 動作を試す のつづき

1. ジェネレータをどこで使うのか？

ジェネレータの動作について、何となく雰囲気を理解できた。しかし、どのような目的に使うのか、今一分からない

「あ！これはジェネレータを使うと、問題を解くのが楽だ。」

「ジェネレータを使った方がシンプルに書ける」

ということが分かるようになりたい。

 

イテレータを置き換えるジェネレータ

最初に覚えたことは、

ジェネレータを使うと、イテレータを簡単に作成できる。

ということ。イテレータとは、複数のオブジェクトに対して、要素を一つづつ辿るための手段。よって、ジェネレータは、複数の要素を辿るために利用できる。

例えば、Group クラスが Person クラスに対して責務があるとする。イテレータを自前で実装するには、境界条件を考えながら、イテレータプロトコルに沿うようにする。

• Python のイテレータ

自前で実装したイテレータは、ジェネレータで置き換えることができる。

• Python のイテレータ (3)

イテレータを自前で実装することと比べると、ジェネレータを使った方がシンプルに書ける。

 

2. ジェネレータを使い、リストを走査する例

ジェネレータを使うことができる例を挙げる。

• Pythonのenumerateでハマった - ponkan lab (via 巡回 - 常山日記)

には、「リストの各々の要素に対して、右隣の要素との差をリストとして返す」処理の例が書かれている。

>>> a = [0,1,2,3,4,5] (略)

… 一つ前の要素との差を求めたかった。a[1]とa[0]の差は1といった感じで、a=[0,1,1,1,1,1]になって欲しい。0番目は何もしない。

ジェネレータを使わずに定義するなら、

def sa(ary):
    result = []
    for x in zip(ary[:-1], ary[1:]):
        result.append(x[1] - x[0])
    return result

def sa_wrapper(ary):
    return ary[:1] + sa(ary)
    
print sa_wrapper([0,1,2,3,4,5])

関数 sa をリスト内包表記で置き換えると、

def sa(ary):
    return [b-a for a, b in zip(ary[:-1], ary[1:])]

この問題に対して、ジェネレータを使ってみる。

最初に、ジェネレータを利用したときのイメージを考える。

1. 対象のリストの要素に対して、0 番目と 1 番目の要素から走査するジェネレータを2つ想定する。
2. 各々のジェネレータから要素を順に取り出し、関数 zip でジェネレータ g1 から取り出した値を g2 から引いた値をリストにする。
3. 最後に、元の先頭の要素を求めるリストの先頭にくっつける。

ジェネレータを使わない場合、

ary[:-1], ary[1:]

のようにして部分リストを取得する。この処理をジェネレータで置き換える。

def gen(ary, i):
    u""" リストの i 番目の要素から走査するジェネレータ """
    for e in range(i, len(ary)):
        yield ary[e]

a = [0,1,2,3,4]
print [a[0]] + [a-b for a,b in zip(gen(a,1), gen(a,0))]

 

ジェネレータを使うメリット

ジェネレータは、イテレータのように要素を1つずつ取り出しては処理を行う。そのため、ジェネレータを使うメリットは、

ary[:-1], ary[1:]

のように部分リストを完全に取得する必要がないこと。もし、対象のリストがとても長く、

「要素を検査した結果、すぐに値を返す」

というような処理が含まれる場合、効率的に計算が行われる。

 

3. 再帰的な処理で置き換える

以下、ジェネレータとは関係がない。上記の例を再帰的な処理で置き換えてみる。

1. 空のリストが来たとすると、そのまま返す。
2. 要素が一つの場合も、何もせずにそのまま返す。
3. 要素が二つのときは、2 番目の要素から先頭の要素を引いた値をリストにして返す。
4. 要素が三つ以上のときは、同様に2 番目の要素から先頭の要素を引いた値をリストにしたものと、2 番目以降の要素を再帰的に呼出した結果のリストと結合して返す。

def rec(ary):
    if len(ary) <= 1:
        return ary
    elif len(ary) == 2:
        return [ary[1] - ary[0]]
    else:
        return [ary[1] - ary[0]] + rec(ary[1:])
    
def rec_wrapper(ary):
    if ary == [] or len(ary) == 1: return ary
    return [ary[0]] + rec(ary)

a = [0,1,2,3,4]
print rec_wrapper(a)

先頭の要素を、リストの先頭に持ってくる処理も再帰呼出しの中に含めるように変更する。

def rec2(ary):
    if len(ary) <= 1:
        return ary
    elif len(ary) == 2:
        return [ary[0]] + [ary[1] - ary[0]]
    else:
        return rec2(ary[:-1]) + [ary[-1] - ary[-2]]

print rec2(a)

 

要素を指定できるようにする

上記では、ジェネレータを使って書いたときの柔軟さが失われている。

ジェネレータを使った書き方は、引数 i によって隣接する要素だけではなくて、i 個離れた隣の要素から引いた値のリストを返すことができる。上記の再帰関数も、同じように指定された i だけ隣の要素から引いたリストを返すように変更してみよう。

まずは、具体的な例で考える。例えば、i = 3 で、3 つ隣の要素から各要素を引いた値のリストを得る場合。このとき、リストが返されるために、元になるリストは少なくとも 要素を 4 つ持っていないといけない。 要素が 3 つ以下であれば、何せずに元のリストをそのまま返すとする。逆に 5 つ以上であれば関数を再帰的に適用する。

これを一般的に書くならば、

1. 引数 i + 1 と、リストの大きさが同じ場合、 i 番目の要素から先頭の要素を引いた値をリストにして返す。
2. 引数 i  >= リストの大きさであれば、何せずにそのまま返す。
3. それ以外のときは、再帰的に関数を適用

def rec3(ary,i):
    if len(ary) <= i:
        return ary
    elif len(ary) == i+1:
        return [ary[i] - ary[0]]
    else:
        return [ary[i] - ary[0]] + rec3(ary[1:],i)

def rec_wrapper3(ary,i):
    if len(ary) <= i: return ary
    return [ary[0]] + rec3(ary,i)

print rec_wrapper3(a,1)

同じように関数 rec2 も変更してみる。

def rec4(ary,i):
    if len(ary) <= i:
        return ary
    elif len(ary) == i+1:
        return [ary[0]] + [ary[i] - ary[0]]
    else:
        return rec4(ary[:-1],i) + [ary[-1] - ary[-1-i]]

print rec4(a,1)

シンプルに見えるけど、見直してもすぐに理解できなくなってしまった。 パタッ(o_ _)ｏ~†

 

処理を分割する

上記の定義は複雑すぎる。理由は、処理が適切に分割されていないため。

行なっている処理は、２つに分かれている。

1. リストの各々の要素に対して、右隣の要素との差をリストとして返す。
2. 対象の先頭要素を、結果の先頭に追加する。

予め Haskell で書いてみる。

sa (x:[])   = []
sa (x:y:xs) = y-x : sa (y:xs)

sa_wrapper xs | length xs <= 1 = xs
              | otherwise      = head xs : sa xs

Python で書きなおすと、

def sa(ary):
    if len(ary) <= 1: return []
    else: return [ary[1]-ary[0]] + sa(ary[1:])

def sa_wrapper(ary):
    if len(ary) <= 1: return ary
    else: return ary[:1] + sa(ary)

これで読みやすくなった。

Python のジェネレータ (3) につづく…

Python のジェネレータ (1) - 動作を試す

1. イテレータとはコンテナの要素を走査するためのオブジェクト

これまでに Python の リスト内包表記、イテレータ について調べた。 次は、「ジェネーレータ」。

Python のジェネレータを理解するには、イテレータの理解が不可欠。ジェネレータについて調べる前に、イテレータの復習から行う。

 

a. イテレータの役割

Python のドキュメント「9. クラス」 における「9.8 イテレータ」の説明を確認すると、

イテレータの使用は Python 全体に普及していて、統一性をもたらしています。背後では、for 文は コンテナオブジェクトの iter() を呼び出しています。…

イテレータは、Python において特別扱いされており、for 文と密接な関わりを持っている。

… この関数は next() メソッドの定義されたイテレータオブジェクトを返します。 next() メソッドは一度コンテナ内の要素に一度に一つづつアクセスします。コンテナ内にアクセスすべき要素がなくなると、next() は StopIteration 例外を送出し、for ループを終了させます。

(太字は引用者による)

まとめると、

1. コンテナの役割を持つオブジェクトを for 文で利用すると、
2. コンテナオブジェクトの iter() メソッドが呼びだされ、
3. イテレータオブジェクトが返される。
4. イテレータオブジェクトは、コンテナが持つ要素を一つずつアクセスするための操作 next() が定義されている。
5. イテレータオブジェクトが要素を最後まで辿りきった後、next() が呼び出されると、StopIteration の例外が投げられる。

 

b. イテレータの例と、動作イメージ

イテレータを使った例を「Python のイテレータ 」で試した。この例では、

1. Person クラスと、そのコンテナである Group クラスを想定し、
2. Group クラスでイテレータプロトコルを実装。
3. Group クラスに __iter__() と next() メソッドを実装し、
4. Group オブジェクトに対して、for ループを適用。

動作イメージを、先ほどのドキュメントと照らし合わせると考えると、下図のようになる。

この例では、コンテナである Group クラスが、イテレータの役割も担うように実装した。Group クラスとは別のクラスをイテレータオブジェクトとして生成していない。

Group クラスのオブジェクトに対して、for 文が適用されると、

1. 組込み関数 iter() に「コンテナである Group オブジェクト」が渡されて、
2. イテレータの役割をするものが返され 、
3. next() の呼出しに応じて、コンテナの中身である Person オブジェクトが引き渡される。

 

c. イテレータ型は、後から追加された特別な機能

イテレータ型は、 Python に最初から備わっていた機能ではなく、

バージョン 2.2 で 新たに追加 された仕様です。(2.3.5 イテレータ型 より)

今使っている Python のバージョンは 2.5.2 。 バージョンを見ると、イテレータが追加されたのは、ちょっと前のようだ。Releases を見ると、2002 年くらいに追加された仕様であることが分かる。

 

d. イテレータを使う組み込みの関数

イテレータ型は、Python の組み込み型の中で重要な位置をしめている。

• cf. Python の シーケンス型に慣れる

例えば、イテレータを使う関数に、2.1 組み込み関数 の list() がある。list 関数の引数は、

「シーケンス、反復処理をサポートするコンテナ、あるいはイテレータオブジェクトです。」

と書かれている。enumerate, filter, tuple もイテレータを利用する。

その点からして、イテレータは「Python 全体に普及していて、統一性をもたらしています」ということ。

複数の要素を持つオブジェクトを、操作する利便性のために存在するイテレータ。その代わり、利便性と引き換えに、イテレータを書くための特別なルールを把握しておく必要がある。

 

2. ジェネレータとはイテレータオブジェクトをお手軽に作成する手段

a. ジェネレータの存在意義

なぜ、最初にイテレータについて理解しておいたのか？

理由は、ジェネレータには、イテレータを生成するための手段に過ぎないから。

9. クラス の 9.9 ジェネレータ によると、

ジェネレータは、イテレータを作成するための簡潔で強力なツールです。

ジェネレータでは、特別な構文である yield を使用する。

ジェネレータは通常の関数のように書かれますが、何らかのデータを返すときには yield 文を使います。 …

突然、「関数のように」と言われても、何のことやら... (@_@;)

とりあえず、重要な点を読み進めておく。

… next() が呼び出されるたびに、ジェネレータは以前に中断した処理を再開します (ジェネレータは、全てのデータ値と最後にどの文が実行されたかを記憶しています)。

 

b. 基本的な動作を確認する

まずは、ジェネレータがどのように動作するのか確認する。

• Pythonの技法：ジェネレータを用いた遅延リストの構築 - builder by ZDNet Japan

にある、サンプルが理解しやすい。

>>> def generator1():
... yield "first"
... yield "second"
... yield "third"
...
>>> gen = generator1()
>>> gen
>>> gen.next()
'first'
>>> gen.next()
'second'
>>> gen.next()
'third'
>>> gen.next()
Traceback (most recent call last):
File "", line 1, in ?
StopIteration
>>>

(上記サイトより、装飾は引用者による)

最初に注目したのは、関数において return ではなく yield と書かれていること。

yield と言えば、Ruby の yield を連想する。Ruby では、ブロック付きメソッドが呼出されたときに、ブロックに制御を渡すためのものだった。

• cf. Ruby のイテレータ - yield の働き

Python の yield は、Ruby の yield とは機能が違う。

ちなみに、JavaScript は、ジェネレータを Python から仕入れている。

• cf. New in JavaScript 1.7 – MDC

 

c. まるでイテレータオブジェクトが存在するようだ

上記のサンプルに戻り、コードを眺めていると、yield を使って定義した関数が、

あたかもオブジェクトのように振る舞っている

ように見える。

1. generator1() の呼び出しによって、インスタンス化されたオブジェクトが存在し、
2. そのオブジェクトが next() メソッドを持ち、
3. next() を呼出す度に、yield で動作を止め、
4. そのとき yield に与えた値を返す。
5. 最後の yield 呼出しが終ると、次回 next() の呼出しで、StopIteration を投げる。

next() による呼出しと、StopIteration を投げる機能は、イテレータの仕様と同じ。

動作をイメージすると、

1. yield を関数内で使うことによって、
2. 関数の背後に関数を監視する誰かが存在するようになり、
3. 関数との交渉は、すべてその誰かを通してやりとりをする

といった感じ。

この辺り、特別なルールと仕組みが存在するところは、個人的に好みではない。。

 

3. ジェネレータの型を調べてみる

では、これらの型がどのようなものか、組み込み関数である type() を使って調べてみる。

2.1 組み込み関数 によると、

type(object)

object の型を返します。返される値は型オブジェクトです。

以下のコードを検査してみたら、

def func():
    return "func()"

def gen():
    yield "gen()"

print type(func)
print type(gen)

print type(func())
print type(gen())

結果は、次のようになった。

<type 'function'>
<type 'function'>
<type 'str'>
<type 'generator'>

func(), ge() の両者とも関数だけれど、返り値の型が異なっている。

1. 普通の関数は、返される文字列の型である str 。
2. yield を使った方は generator

となっている。

 

4. yield 文によりジェネレータ関数となる

関数の中で yield を使うと、return により値を返す、普通の関数ではなくなってしまう。

6.8 yield 文 によると、

yield 文は、ジェネレータ関数 (generator function) を定義するときだけ使われ、かつジェネレータ関数の本体の中でだけ用いられます。関数定義中で yield 文を使うだけで、関数定義は通常の関数でなくジェネレータ関数になります。

ジェネレータ関数が呼び出されると、ジェネレータイテレータ (generator iterator)、一般的にはジェネレータ (generator) を返します。ジェネレータ関数の本体は、ジェネレータの next() が例外を発行するまで繰り返し呼び出して実行します。

(太字は引用者による)

yield がどのように実装されている、説明を読むと、

yield 文が実行されると、現在のジェネレータの状態は凍結 (freeze) され、expression_list の値が next() の呼び出し側に返されます。ここでの ``凍結'' は、ローカルな変数への束縛、命令ポインタ (instruction pointer)、および内部実行スタック (internal evaluation stack) を含む、全てのローカルな状態が保存されることを意味します:

(太字は引用者による)

簡単にいえば、呼出しの途中で冷凍パックして、後でチンして解凍ということ。

関数の呼出しにおいて、処理の途中で動作を止め、そのときの中間状態の値を返すことができるようにした仕組み。それが、ジェネレータ。

 

5. ジェネレータの呼出しを試してみる

a. for ループで呼出し

ジェネレータは、イテレータを作成するためのツールとして存在するので、for ループで利用することができる。

def gen2():
    yield "a"
    yield "b"
    yield "c"

for x in gen2():
    print x

結果

a
b
c

for ループを使えば、呼出し側では next() を使わなくても、ジェネレータの凍結と再開をすることができる。 next() の呼出しは for ループに任せられるため。

ジェネレータの動作ついて順を追ってみる。

1. まず、 yield を関数内に記述することにより gen2() の呼出しでジェネレータが生成される。
2. for 文は内部で  iter() によりジェネレータイテレータを取得し next() を呼出す。
3. next() を呼出すごとに個々の yield で値が返され処理が止まり、関数の実行が凍結される。

 

b. yield を for ループの中で使う

上記は見れば明らかなように、関数内で yield を実行する数だけ、関数外から next() を呼出すことができる。例えば、次にように yield が for ループによって複数回繰り返された場合、その回数だけ next() が呼出されることになる。

def gen3():
    for i in range(1,6):
        yield i

for i in gen3():
    print i

結果、

1
2
3
4
5

 

c. リスト内包表記を使って

これまでに書いたジェネレータを、リスト内包表記を使って記述するなら、

print [x for x in gen()]
print [x for x in gen2()]
print [x for x in gen3()]

結果は、

['gen()']
['a', 'b', 'c']
[1, 2, 3, 4, 5]

 

6. イテレータをジェネレータで作成する

「ジェネレータはイテレータを生成するためのツール」

ということに目を向ける。

「Python のイテレータ」では、クラスをイテレータにするために、Group クラスに next(), __iter__() メソッドを実装した。これをジェネレータで代用してみる。

1. Group クラスの __iter_(), next() の代わりに、ジェネレータ関数である iter() を作成し、
2. インスタンス変数である Person オブジェクトを要素とする配列をイテレートする

ように変更してみた。

class Person:
    def __init__(self, name, age):
        self.name = name
        self.age = age

    def __str__(self):
        return self.name + " " + str(self.age)
        
class Group:
    def __init__(self):
        self.persons = []

    def add(self, person):
        self.persons.append(person)
        return self
    
    # ジェネレータ。__iter__(), next() の置き換え。
    def iter(self):
        for person in self.persons:
            yield person
        

group = Group().add(Person("Tarou", 21)).add(
                    Person("Hanako", 15)).add(
                    Person("Jiro", 15))

# iter() を呼出す
for person in group.iter():
    print person.name

for a in group.iter():
    print a.age

こうすれば、next() を実装する手間は減る。

追記(2008.8.25) : 上記を少し変更 → Python のイテレータ (3)

 

7. ジェネレータの独立性

ところで、作成されるジェネレータは、作成されたジェネレータごとに独立している。

上記の gen4() のコードの続きに、以下のように書くと、

g = gen4()
g2 = gen4()

try:
    print "g:" , g.next()
    print "g:" , g.next()
    
    print "g2:", g2.next()
    print "g2:", g2.next()
    
    print "g:" , g.next()
    print "g:" , g.next()
except StopIteration:
    print "StopIteration"
    
print "g2:", g2.next()

結果は、二つのジェネレータが各々の文脈を持っていることがわかる。

g: Tarou
g: Jirou
g2: Tarou
g2: Jirou
g: Hanako
g: StopIteration
g2: Hanako

 

8. ジェネレータ関数の中で return

ジェネレータというと、 最初に return を yield で置き換えるというイメージが強かった。そのため、 return を併用することができないかと思いきや、そうではない。 yield と return は同居できる。ただし、 return で値を返そうとするとシンタックスエラーとなるので注意。

例えば、 ジェネレータ関数の中で return “hoge” と記述すると、

exceptions.SyntaxError: 'return' with argument inside generator (line 80, offset 0): 'return "hoge"'

また、ジェネレータ関数内で return に到達すると、そこでおしまい。それ以降のコードは実行されないようだ。

例えば、次のジェネレータ関数において、 値 hoge3, hoge5 は返されない。

def gen5(n):
    if(n < 10):
        yield "hoge"
        yield "hoge2"
        return
        yield "hoge3"
    else:
        yield "hoge4"
        return
        yield "hoge5"

 

9. ジェネレータに値を渡すsend

7 PEP 342: New Generator Features によると、

In Python 2.3, yield was a statement; it didn't return any value. In 2.5, yield is now an expression, returning a value that can be assigned to a variable or otherwise operated on:

val = (yield i)

Python 2.5 で yield は式になったとある。

ちなみに、式とは Statement (programming) - Wikipedia, the free encyclopedia には、

In most languages statements contrast with expressions in that statements do not return results and are executed solely for their side effects, while expressions always return a result and often do not have side effects at all.

式とは、値を返すもの。 Haskell の let 式を思い出した。

let 式は式なので let 自体も値を持ちます。しかし where 節は節なので、値を持ちません。

(ふつうのHaskellプログラミング , p187)

Ruby の if も思い出した。

Rubyでは(Cなどとは異なり)制御構造は式であって、何らかの値を返すものがあります

(制御構造 - Rubyリファレンスマニュアル)

サンプルを試してみる。

def gen6():
    val = (yield "hoge")
    if val is not None:
        yield val + "fuga"
    else:
        yield "fuga"

g6 = gen6()
print g6.next()
print g6.send("piyo")

5.2.8 Yield expressions によると、

send(value)

Resumes the execution and ``sends'' a value into the generator function.

next() と同じように、ジェネレータを再開するときに send を用いることができる。 next() との違いは、呼出し側からジェネレータに値を渡すことができること。

上記のコードでは、

1. 最初の next() の呼出しにより、yield “hoge” で一時停止し、
2. 次の send(“piyo”) によって処理が再開されたときに、val に値が設定される。
3. そして、もし send() ではなく、next() が呼出されたときは、val の値は None となってしまうのでそれに対応するために if で場合分けを行い対応している。

 

10. Ruby の yield と比較する

「Ruby のイテレータ」 と、Python のジェネレータは類似している。

Ruby の例では、

1. Person クラスは Group クラスに所属し、
2. Group は Enumerable モジュールをインクルードすることによって、イテレータを実現。
3. その際、Enumerable モジュールの機能を利用するために、 Group クラスで each メソッドを実装。
4. このとき each メソッド内において、Group の要素である個々の Person を yield で引数としてブロックに渡し、制御を呼出し側に委ねる。

Python のジェネレータでは、

1. yield を関数の中で使うと、
2. ジェネレータが生成される。

繰り返しになるが、ジェネレータは

「イテレータを簡単に作成するためのツール」。

Ruby は、クラスとインスタンス変数により、イテレータを実現している。この対比としてジェネレータを捉えると、Python では Ruby と同じような動作を、関数とローカル変数で簡便に行うことができる仕組みが備えられていると言える。ただし、同じようなと言っても、関数の呼出しにおいて相互に制御が移るという点だけだけれど。

Ruby のイテレータ で書いた例と、類似するコードを考えてみる。

def gen4():
    persons = ["Tarou", "Jirou", "Hanako"]
    for person in persons:
        yield person

for person in gen4():
    print person

print ["Hello! " + person for person in gen4()]

結果は、

Tarou
Jirou
Hanako
['Hello! Tarou', 'Hello! Jirou', 'Hello! Hanako']

Ruby で記述した Group クラスが ge4() 関数に相当し、Person クラスがローカル変数 persons に相当すると考えればいいかな。

 

内部イテレータなのか？

まつもと直伝 プログラミングのオキテ 第5回（2） - まつもと直伝 プログラミングのオキテ：ITpro によると、

Rubyのブロックのような個々の要素ごとの処理を表現するものをコンテナ・オブジェクトのメソッドに渡し，メソッドが要素ごとの処理を呼び返すタイプの繰り返し方法を「内部イテレータ」と呼びます。

イテレータ – Wikipedia によると、

内部イテレータとは、要素を格納したオブジェクトが、自身の要素に対して繰り返しながらユーザコードを逐一呼び出す方式である。繰り返しの記述が（オブジェクトの）内部にあるためこの名がある。一般にForeach文などとして言語で用意されている。

Ruby のイテレータは、処理をコンテナのメソッドに渡し、要素を保持しているオブジェクト側で繰り返しの記述があるので内部イテレータ。Python のジェネレータでは、繰り返しの記述はジェネレータ関数にある。しかし、呼出し側で for 文を使い、繰り返し next() で一時停止を解除している。これをどちらに分類すればいいのだろうか？

 

11. まとめ

追記 (2009.11.25):

• 関数の中に yield があったら、そこで一時停止して値が返される。
• 再開するには呼出側で next() を呼出す。
• for は内部でジェネレータの next() を呼出してくれる。
• 呼出し側からジェネレータに値を渡したい場合、send() を使う。

Python のジェネレータ (2) につづく…