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

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

前回、再帰的な表現を関数からオブジェクトのメソッドに移すことにより、再帰関数のイメージを複数のオブジェクトの連鎖として理解しようと試みた。実際にオブジェクトが連鎖する場合の実装を Python でしてみたが、今回はこのイメージに沿うように Haskell のコードを変更してみる。

問題はオブジェクト指向的な視点を関数型へ持ち込むとき、どのようにして考えたらいいのだろうか … (@_@;)

状態がない

ところで、関数型言語に触れてみたいと思い、Haskell をいじりはじめて最初に驚いたのは、

純粋関数型言語はチューリングマシンをベースとしたCやJavaなどの手続き型言語と違い、状態という概念をもたない。そのため参照透過性が保たれる。

(関数型言語 – Wikipedia より)

え… (@_@;) 状態なくてどうやってプログラミングをするんだろ？と。どうしてもプログラミングというと、内部的に状態を持った小人さんたちが、インターフェイスを通してコラボレーションすることにより、

わぁい♪ヽ(▽￣ )ﾉ/(＿△＿)ヽ( ￣▽)ﾉわぁい♪

と計算を進めていくというイメージが強いので、「状態がない」ということに違和感を感じた。

Referential transparency

ふつうのHaskellプログラミング (p.113) の「参照透明性」のコラムには次のように書かれている。

… 呼出すごとに返り値の違うメソッドが作れるのは、Java に (再) 代入があるからです。言語に (再) 代入があると、ある式を、それと等しい値で置き換えられなくなります。つまり、参照透明でなくなります。

再代入についての話は、本の冒頭から書かれており、

… 代入を排除することでプログラムは明解に、わかりやすくなえります。… なぜグローバル変数を濫用すると読みにくくなるかと言えば、それは、その変数がいつ変更されるかわからないためです。(p8)

Real World Haskell においてもその冒頭で、Why functional programming? Why Haskell? として、

In Haskell, we de-emphasise code that modifies data. Instead, we focus on functions that take immutable values as input and produce new values as output. Given the same inputs, these functions always return the same results. This is a core idea behind functional programming.

(太字は引用者による)

「変更不能な値を入力として受けとり、新しい値を出力する」という関数型言語としての特徴が述べられている。

変数のスコープ

ちなみに、なぜそのような方法を採用したかということについて、「ふつうのHaskellプログラミング」ではグローバル変数を例に挙げて説明している。つまり、「グローバル変数の弊害から逃れる方法」には二つの方法があると。一つは「変数のスコープをできるだけ小さくして、変数が変更される場所を制限すること」(p.8) 。それからもう一つは「変数の値を変更できないくしてしまうこと」。前者はその通りだと思えても、後者の選択は何て大胆なんだとびっくりした。

考えてみると、前者は当然ながらグローバル変数に限った話ではない。インスタンス変数然り、ローカル変数もまた然り。例えばもし、巨大なクラスがあり、そこにたくさんのインスタンス変数があって、複数のメソッドからいじられているコードを見たら、変更する気が失せる。(+_+) 加えて、テストコードが付属してないなら最悪で、そのままふたをして地中深くに埋めておきたくなってしまう。^^; ローカル変数にしても同じ。「リファクタリング」の「問合わせによる一時変数の置き換え」の対象くらいのものだったらいいけれど、複数の仕事を長々と、 for や if のネスト祭りで、一画面以上に渡り変数がボカスカとひっかき回されているメソッドを見たら、脳みそ沸騰、そして卒倒。(o_ _)ｏ~† インスタンス変数と呼んではいるけれど、人の認識にとってグローバル変数と等価なものは本当に勘弁してほしい。

正直、自分の容量の小さい脳みそでは、成長過程にあるクラスにおいてインスタンス変数が画面から徐々に見えない位置になるに従って徐々にやばくなる。複数のメソッドからインスタンス変数に変更を加えたり、状態に応じたコードを書く段になると目が回りだし、テストコードを書きながらでないとエラー連発。ストレス爆発。昔、「リファクタリング」を読んでいなかったらと思うと、ぞっとする。(@_@;) 長いメソッドや、巨大なクラスを書いて平気な人は、きっと記憶力がいいか、もしくは頭がいいのだろうと思う。自分のように、昨日書いたコードの内容なんて忘れてしまうタイプの脳みそでは全く無理。^^; そういった意味で、もしかすると Haskell が書けるようになったら楽できるかも、という密かな期待が…。

そうえいば、Haskell をさわっていて、はじめに連想したのがリファクタリングだった。メソッド一つの意味を明確にするという動機が、結果的にあらゆるローカル変数・インスタンス変数のスコープを小さくすることに貢献し、問題の局所化と変更への耐性を上げていく。コンパクトでシンプルなものは、理解しやすいし変更しやすい。Haskell に慣れて書けるようになったら、自然とそういたったコードに落ち着くのかな (？) とか思いつつ、未だコンパクトな再帰で目を回しているので、先は長い… ^^;

値をまるごと更新

JavaScript

さて、そんな状態を持たない関数型言語ではどのようにプログラミングをしていったらいいのだろう？内部的な変数を操作する考え方にどっぷりとつかっているので、そんなことを突然言われても、うーん… (@_@;)

と、ここで以前に「まるごと JavaScript」の「Flash の ActionScript で関数型風プログラミング」の記事に「関数型プログラミング」の説明が書かれていたことを思い出した。それによると、

関数がグローバル変数に頼らないようにする方法のひとつは、… 関数が遷移前の状態を引数として受け取り、関数の実行が終了したら新しい状態を返すというものです。 (p.183)

上記の次頁には「状態を受け取って返す関数」としてのカウンタの例があった。これを少しだけ変更して定義してみる。

function next_counter(counter){
    // 渡されたカウンタを新しいオブジェクトで置き換える
    return {state : counter.state + counter.step,
            step  : counter.step}
}

var counter = {state:0,       // カウンタの値 
               step:1}       // 増分

// カウンタの値を 10 進める
for (var i=0; i<10; i++){
    console.log(counter);
    counter = next_counter(counter);
}

counter 変数はカウンタを表現しており、内部でカウンタの値の状態(state) とカウンタの増分 (step) を持っている。next_counter 関数は、与えられたカウンタオブジェクトの値から新しくオブジェクトを作って返す。

これを Firefox の Firebug 上で実行すると結果は、

Object state=0 step=1
Object state=1 step=1
Object state=2 step=1
Object state=3 step=1
Object state=4 step=1
Object state=5 step=1
Object state=6 step=1
Object state=7 step=1
Object state=8 step=1
Object state=9 step=1
Object state=10 step=1

関数を呼出す度にオブジェクトが新しいオブジェクトに置き換えらているが、結果だけ見ると、あたかも状態を持っているかのように見える。

Java

これを見て更に思い出したのが、Joshua Bloch の Effective Java の「項目 13 不変性を選ぶ」という節。そこでは複素数 (Complex) クラスにおける不変性について説明されていた。(p.62) 以下は Complex クラスにおける足し算の例。

	public Complex add(Complex c) {
		return new Complex(re + c.re, im + c.im);
	}

ここでは計算の結果を、渡された Complex オブジェクトの内部を変更して返すのではなく、新たなオブジェクトを生成して返している。

こういった実装の代表例としては、

イミュータブルなオブジェクトの古典的な例はJavaのStringクラスのインスタンスである。
String str = "ABC";
str.toLowerCase();
メソッドtoLowerCase()は変数strの値"ABC"を書き換えない。代わりに新しいStringオブジェクトがインスタンス化され、生成時に"abc"という値が与えられる。

(イミュータブル – Wikipedia より)

Effective Java (p.63) によると、

これは、関数的(functional)方法として知られています。なぜならば、メソッドは、そのオペランドを修正することなく、オペランドに対して関数を適用した結果を返すからです。…

不変オブジェクトは単純です。不変オブジェクトは、正確に一つの状態にあることができますし、それはオブジェクトが作られた時の状態です。もし、すべてのコンストラクタがクラスの不変式(invariant)を確立することを保証するならば、それらの不変式がずっと真のままであることが保証されますし、…

一方、可変オブジェクトは任意の複雑な状態空間を持つことになります。もし、ミューテーターメソッドにより行われる状態遷移の正確な記述を、ドキュメンテーションが提供していなければ、可変クラスを信頼して使用することは、困難か不可能になります。

(太字は引用者による)

これに加えて「項目 24 必要な場合には、防御的にコピーする」(p.114) も参考に。実装例は以下を参照。コンストラクタにおいて可変オブジェクトを受け取ったら、それを元にして新しくオブジェクトを生成してフィールドに設定。また、get メソッドにおいても、同様にクライアントに渡す前に新しくオブジェクトを生成して渡している。

まとめとして次のように述べられている。

可変にすべきかなり正当な理由がない限り、クラスは不変であるべきです。 (同上、p.67 より)

スタックの Haskell での実装例を読む

なるほど、中身をいじることができなければ、「渡されたオブジェクトの中身を元に新たに同じ型のオブジェクトを生成」して返せばいいというわけか。(@_@)

ふつうのHaskellプログラミングを見ると、「9.2 代数的データ型」の「多相的な型の宣言」「再帰的な型」(p.232)、また、「フィールドの更新」(p.228) 辺りが参考になりそう。

スタック

Implementation of basic functions にはスタックの Haskell での実装例が書かれていた。

最初に、以下のような多相的な型をフィールドに持つ Stack a 型の定義がある。 (Type declaration より)

data Stack a = MakeStack [a]

push の実装は Implementation of basic functions に、

push :: Stack a -> a -> Stack a
push (MakeStack s) element = MakeStack (element:s)

なるほど、第一引数 Stack a 型の値を `オブジェクト’ 、関数名 push を `メソッド’ と見たてれば、クラスによる実装と同じように見える。ただし、違うのは、返される値が「引数を元に作られた新しい値」であるということ。

また、pop を見ると、返される値がタプルであれば、pop で取り出した値と、pop した後のスタックを返すことができることがわかる。言われてみれば当り前だけれど、「なるほど (@_@) こうすればいいのか」と思った。(同上より)

pop :: Stack a -> (a, Stack a)
pop (MakeStack (h:t)) = (h, MakeStack t)
pop (MakeStack []) = error "Attempt to pop an empty stack."

結局、中身を変更する変わりに、「中身が変更された状態を表わす新しい値」を作って返すということ。これでやっと実装できそうな感じになった。 ^^

実装

前回に書いたクラス図がこちら。これに沿って実装していく。

081023-002

型

まずは、代数的データ型で構造を記述する。

data Sieve = Sieve {
      list :: [Int],    -- ふるいにかける前の数値のリスト
      tail :: Sieve   -- リストの先頭要素でふるいにかけた後、
                        --「このふるいから落ちた数値のリスト」を保持するふるい
    }
           | Empty  
             deriving Show

前回の Python の実装と違うところは、「ふるいにかけるときの基準となるリストの先頭要素」を保持するフィールド head がないこと。これは右図のピンク色の数値に相当するが、「ふるいにかける前のリスト」から取得できるので、わざわざ作る必要がないことに気がついた。

データコンストラクタ Empty は、Python のコンストラクタ内において、self.tail = None と設定していることに相当するものを書きたいため。

これだけ見ると Python におけるクラスの記述とほぼ同じであることがわかる。

sieveByHead 関数

次に、`一つ’ のふるいにおいて、「設定された数値のリスト」の `先頭の要素’ で残りの数値をふるいにかける動作を書く。

sieveByHead :: [Int] -> [Int]
sieveByHead (x:xs) = [n | n <- xs, n `mod` x /= 0 ]

これも素直にそのまま。

sieve 関数

次に、連続してふるいにかけていく動作を書いてみる。ここが Python とは異なるところ。先ほどのスタックの push の実装を真似して、「ふるいにかけたら、ふるい」が返ってくるようにする。当然ながらふるいにかける前とかけた後の中身(値)は異なる。ということで、関数の型宣言は以下のように。

sieve :: Sieve –> Sieve

定義を考えるときは、Python で定義したときのように考える。つまり、注目するのは右図の一番上のふるいと、そのふるいから落ちた数値のリストを拾う、すぐ下のふるいのみ。

最初にした型の定義より、はじめに数値をセットするふるいが以下のようであるとする。この場合、ふるいの一つに「2 からはじまる自然数のリスト」を設定。

Sieve [2..] Empty

ここから下のふるいについて考えていく。 sieve 関数の左側が、上記の型宣言に合わせて以下のようであるとすると、

sieve (Sieve xs s) =

上のふるいから落ちた数値のリストは、先ほど定義した関数を利用して、

sieveByHead xs

これを元に下のふるいは生成されるので、下のふるいは以下のように表現できる。

Sieve (sieveByHead xs) s

今定義しているのは、ふるいを連続的にかけていく sieve 関数。しかし、注目するのは上二つのふるいのみでよい。なぜなら、 sieve 関数が一回に適用できるふるいは一つであり、適用された引数によって「ふるいにかける様子」を表現しなくてはならないため。

注目した二つのふるいの内、上のふるいにしてみれば、「連続的にふるいをかけろ！」と言われても、その全体の動作は知らず、自身は下にくるふるいに対して「今自分のところから落ちた数値を元にふるいにかけて！」とお願いするしかない。つまり、上のふるいから見ると、以下のように表現することがふるいを連続的にかけるときの動作の一端を担うことになる。

sieve $ Sieve (sieveByHead xs) s

では、最終的に何が返るのか？それはスタックにおいて、push したときのように sieve 関数をはじめに適用したふるいということになる。

Sieve xs (sieve $ Sieve (sieveByHead xs) s)

しかし、これだけでは関数の呼出しが延々と続いてしまう。そこで、ふるいの一番下の状態のときの様子を表現する必要がある。

sieve (Sieve [] _) = Empty

数値のリストが空になったら、「空ですよ」と返す。

sieve 関数全体を示すと、

sieve :: Sieve -> Sieve
sieve (Sieve [] _) = Empty
sieve (Sieve xs s) = Sieve xs (sieve $ Sieve (sieveByHead xs) s)

headSieve 関数

次に、連続的にふるいにかけた後、ふるいの基準となった数値のみをリストにして返さなくてはならない。上記の関数を適用した後に、ふるいの基準のみを抽出する関数を定義する。型宣言は、連続的にふるいをかけた後のふるいを与えると、数値のリストが返るようにする。関数名は headSieve とした。

headSieve :: Sieve -> [Int]

これも先ほどと同じように上二つのふるいのみで考える。リストを返すパターンなので (:) を使って、

headSieve (Sieve (x:_) s) = x : (headSieve s)

パターンマッチにおいて、与えられたふるいの持っている数値のリストの先頭要素のみを束縛。その後、そのふるいから見て、一つ下のふるいに対しても、同様に「持っているリストの内、先頭の要素のみを返して！」とお願いする。

今回もこのままでは、関数の呼出しが延々と続いてしまうので、空の場合を定義しないといけない。全体では以下のようになる。

headSieve :: Sieve -> [Int]
headSieve Empty           = []
headSieve (Sieve (x:_) s) = x : (headSieve s)

完成

-- ふるい
data Sieve = Sieve {
      list :: [Int],    -- ふるいにかける前の数値のリスト
      tail :: Sieve   -- リストの先頭要素でふるいにかけた後、
                        --「このふるいから落ちた数値のリスト」を保持するふるい
    }
           | Empty  
             deriving Show

-- リストの先頭要素でふるいにかける
sieveByHead :: [Int] -> [Int]
-- sieveByHead (x:xs) = [n | n <- xs, n `mod` x /= 0 ]
sieveByHead (x:xs)
    | x == 1 || x == -1 = [x]
    | otherwise         = [n | n <- xs, n `mod` x /= 0 ]

-- 連続してふるいにかける
sieve :: Sieve -> Sieve
sieve (Sieve [] _) = Empty
sieve (Sieve xs s) = Sieve xs (sieve $ Sieve (sieveByHead xs) s)

-- Sieve に設定されたリストの先頭要素を、すべての Sieve に渡って取得する
headSieve :: Sieve -> [Int]
headSieve Empty           = []
headSieve (Sieve (x:_) s) = x : (headSieve s)

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

sieveByHead 関数は、n = 1, –1 で無限ループになってしまったので、パターンマッチを増やした。

うーん、しかし、sieveByHead 関数は sieve の中に入れた方が読みやすいかなぁ…

sieve :: Sieve -> Sieve
sieve (Sieve [] _) = Empty
sieve (Sieve l@(x:xs) s) = Sieve l (sieve $ Sieve (sieveByHead x) s)
    where
      -- リストの先頭要素でふるいにかける
      sieveByHead x
          | x == 1 || x == -1 = [x]
          | otherwise         = [n | n <- xs, n `mod` x /= 0 ]

しかし、翌日になって上記を見ると、「あれ？これ何やってたんだっけ…」とか思う自分の脳みそに…

パタッ(o_ _)ｏ~†

すぐに忘れる脳みそのためのメモ

2008年10月30日木曜日