素朴にエラトステネスのふるい (2) - オブジェクト指向を手がかりに再帰表現を考える

「素朴にエラトステネスのふるい (1)」の続き。

コードを再掲。Haskell では、

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])

やはり、今日見ても再帰的な表現はどこか理解しきれないと感じる。(+_+) これ以上考えてもらちが開かないので、このままの形で考えるのは諦めた。

 

ふるいの動作

ところで、上記のコードは直接素数を生成するわけではない。`ふるい’ はあくまでも素数を生成するためのツール。「2 からはじまる自然数のリスト」を与えたときに素数のリストが生成される。

main = do print $ take 10 $ sieve [2..]

print sieve(range(2,100))

もし、「1 からはじまる自然数のリスト」を引数に与えたなら、その `ふるい’ の性質上、生成されるのは [1] 。なぜなら、最初の「リストの先頭要素で割り切れる要素をふるいにかける」というところで、1 以降の要素が脱落してしまうため。つまり、上記のコードは `ふるい’ の動作を表現しているということを忘れてはダメ。素数が生成されるのはその結果に過ぎない。

 

ふるいのイメージ

よくわからないときは絵を描くことにしているので、素数を生成するときの `ふるい’ をイメージしてみた …

「このふるいは、近所の量販店で売られているふるいとは違う。小麦粉を `ふるう’ のではなく、「数値のリスト」をふるう。動作も一風変わっていて、数値のリストをザザーっと流し込むと、最初にふるいに落ちた数値がふるいにセットされ、その数値で『割り切れない数値』がふるいを通り抜け、割り切れた数値がふるいに残される。

ある数値のリストをこのふるいにかけたとする。直後、ふるわれた数値が地面に落ちる寸前、同じ種類のふるいを別にもう一つ用意し、落ちていく数値を受けとめる。同種のふるいなので動作も同じ。また落ちてきた先頭の要素がふるいにセットされ、残りの要素に対してふるいをかける基準となる。

手元にふるいが更に何個もあったので、これをどんどん繰り返していたら、最後には落ちていく数値がなくなってしまった。」

 

ふるいのふるまい

この様子を示したの右図。で、このふるいを一つのオブジェクトと見たて、ふるいクラスを作成する。まずはこのふるいに対して何ができるかという視点で。

• 数値のリストをセットする
• ふるいにかける

ここからふるいの内部はどうなっているかと想像すると、

• セットされた数値のリストを持つ
• セットされたリストの先頭要素を持つ

それから、右図のようにふるいをつなげて使っている様子をふるい自身に覚えてもらうことにすると、

• 自分がふるい落とした数値を受けとめるふるいを知っている

そして、各自ふるった後、落ちた数値を受け止めるためのふるいを自分で用意してもらうことに。

 

クラス図

 

実装

class Sieve:
    """ ふるい

    このクラスのオブジェクトが連なって働くことによって
    「エラトステネスのふるい」の振る舞いをする
    
    - 使い方
    1. インスタンスの生成
    2. 値の設定
    3. ふるいにかける
    """
    def __init__(self):
        self.L = []         # ふるいにかける前の数値のリスト
        self.head = None    # ふるいにかける数値のリストの先頭 (ふるいの基準)
        self.tail = None    # Sieve : ふるいにかけた後の数値のリストを保持

    def set(self,L):
        """ ふるいにかける数値のリストを設定 """
        self.L = L
        self.head = L[0]
        return self

    def sieve(self):
        """ ふるいにかける """
        self._sieveByHead()
        if self.tail:
            self.tail.sieve()

    def _sieveByHead(self):
        """ 設定されたリストの要素をその先頭要素で割り、
        割り切れなかったものをふるいから落とし、新たにふるいに設定する

        ※ 設定されたリストの要素が二つ以上ないと tail は None のまま。
        """
        if len(self.L) > 1:
            self.tail = Sieve()
            sieved = [x for x in self.L if x % self.head != 0]
            if sieved:
                self.tail.set(sieved)

    def __str__(self):
        """ ふるいの基準として使われた数値を出力 """
        if not self.head: return ""
        return str(self.head) + ", " + str(self.tail) if self.tail \
            else str(self.head)

s = Sieve().set(range(2,100))
s.sieve()
print s

最初に示したコードと比べるとかなり長くなってしまったが、こちらはイメージしやすい。 ^^ なぜかと言えば、クラス定義で意識するのはオブジェクト単位であり、オブジェクト一つで何ができるかを考えればいいため。sieve メソッドを見ると「自らふるい落とした数値のリストを受けとる`ふるい’」に対して sieve メソッドを呼出している。しかし、メソッドを見ても頭が混乱することはない。単純に `ふるい’ が `ふるい’ に対して 「sieve してくれ」と依頼しているようにしか見えないから。

結局、再帰的な関数において呼出す度に生成される文脈を、オブジェクトというイメージしやすい形に置き換えることにより理解しやすくなった気がする。オブジェクト指向で考えるときの一番基本的な戦略は、「オブジェクトと関わりのあるオブジェクトに対して、どのようにコラボレーションするか？」を問うこと。この方針が `考える範囲を限る’ ということに対して、`オブジェクト‘ という範囲の枠を提供してくれる。

再帰的な関数との違いがもう一つ。それは、やることを分割しているということ。上記のクラスでの実装は、「ふるいにかける動作、ふるう動作、ふるいを連ねる動作、その結果を表示するための動作」を別々にした。そして、それらの動作を `一つのふるい’ というイメージと関連付けて考えた。再帰的な関数では、これを一行で表現する。そうすると、自分の脳みそでは、「一体誰が何をしてその結果どうなったの？」というところで、えっ？(@_@;)？ となってしまう。

 

オブジェクト指向をアナロジーとして用いる

逆に言えば、再帰的な関数を、アナロジーとして上記のような表現とほぼ等価であると見なすことができれば、すんなりと理解できるはず…。明らかな動作の違いは、クラスによる実装では計算が終った時点で計算過程の一部の履歴が残っているのに対して、再帰関数では消えているという点くらいだし。… ということは、えーと、再帰関数である sieve を見たら、次のように見たてればいいということか。

1. 「sieve というメソッドを持つオブジェクト」があると想定。(ふるいに相当)
2. sieve を再帰的に呼出すところは、新しく同種のオブジェクトを生成すると見なす。
3. ただし、そのオブジェクトは最終的に計算の過程を保持することなく、計算の終了とともに消滅して結果 (関数の返り値) のみを残す。
4. 最後に、残された結果を連結。

つまり、関数で呼出された文脈をオブジェクトと見なし、そこで使われているローカル変数をインスタンス変数に見たてるということ。以前より少し理解が進んだような気になれた。 ^^

関連記事

• 素朴にエラトステネスのふるい (3) – Python の実装を Haskell へ