素朴にエラトステネスのふるい (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_ _)ｏ~†

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