ニューラル株式会社|ハイブリッドOS|File System|ARM|Android|Java|制御システム|オープンシステム

 

技術者コラム

 
フォーム
 
第12回目:Haskellで問題を解く (Part3)
2014-05-05

筆者:村田

 

こんにちは。

 

GW終盤ですが皆さんいかがお過ごしでしょうか。天気もいいですし、充実した休暇であることと思います。私はお出かけはしていませんが、友人と飲みに行ったり、積ん読本を手に取ったりしていました。

 

さて今回は素数のリストをちゃんと作りましょう。型は最初に考えた通りprimes :: [Int] のままでいきたいです。

 

素数を求めるには整数のリストから素数の倍数を消してふるいに書ける方法が有名ですね。簡単に説明しておくと

2,3,4,5,6,7,8,9,10...

から最初の素数2を残し2の倍数を消すと

2,3,  5,  7,  9,  ...

次の素数3を残し3の倍数を消すと

2,3,  5,  7,      ...

とこんなアルゴリズムです。

 

これもループが必要になりそうですね。ふるいにかける素数を変えて繰り返し処理を行っています。したがって前回の手法と同じくループ用の下請け関数を作りましょう。まずは型から考えます。ループ用下請け関数は、変わる素数(2,3,5,7...)を引数に渡して、ふるいにかけた後の素数リストを返して欲しいので以下の型を考えました。

 

primes' :: Int -> [Int]

primes' = undefined

 

うーん・・・しかしよく考えるとprimes'の引数は上記ではうまくいかなそうです。前回お話した通り、haskellの関数の挙動を変えるには引数で渡すしかありません。上の定義の引数Intは割る素数(2,3,5...)ですが『割られるリスト』も変化しますよね。最初は2,3,4,5...、次の呼び出し時には2,3,5...と2の倍数は消えているはずです。したがって引数に『割られる整数リスト』も一緒に渡す必要があります。

 

primes' :: Int -> [Int] -> [Int]

primes' = undefined

 

こんな感じですかね。よし進めましょう。

 

続きを考えてまたちょっと困りました。割られる整数リストを素数で次々割るのでここにもループがあります。このプログラムは2重ループが必要です。また下請け関数(primes'')を作って2重ループにしても書けるのですが、分かりにくいプログラムになりそうなので別の方法でループさせます。haskellにはリストの各要素に対してループする便利な関数がたくさんあります。その内の一つfilter関数を使いましょう。filterはリストの全要素をなめて条件式を適用し、結果が真のリストを作り上げます。ここでhaskell学習のコツですが、新しい関数が出たら型を見て勉強しましょう。

 

> :t filter

filter :: (a ->Bool) -> [a] -> [a]

 

えー、また新しい要素ですね。aってのは型変数と言い、任意の型を表しています。正式な型はIntのように大文字から始まりますが、型変数は小文字で始まっていますね。任意の型というのはIntであったりStringであったりどんな型でもいいということです。Javaのジェネリクス、C++のテンプレートみたいなものでしょうか。[a]の部分には同じ型のリストであることを表していますのでaがIntだとすると、その時のfilterはfilter :: (Int -> Bool) -> [Int] -> [Int] となります。

 

もうひとつ注意して型をよく見ましょう。filter :: a -> Bool -> [a] -> [a] ではありません。最初の引数の型はaではなく(a -> Bool) と括弧でくくられています。これはaを引数にBoolを返す『関数』を引数にするということを表します。ちょっと横道ですが関数そのものを引数に渡したり戻り値にすることを容易にできることが関数型言語の特徴です。

 

filter関数を使ってリストの全要素に関数を適用する例を一つ示します。インタプリタですぐに実行できますよ。

 

> filter (\x -> x `mod` 2 == 0) [1,2,3,4,5]

[2,4]

 

えっとこの例でも新しい要素がありますね。filterの引数に関数を渡すわけですが、きちんと名前のある関数でなくてもいいのです。上の例のように無名関数、ラムダ式を使えます。\x -> x `mod` 2 == 0 というラムダ式は引数xをもらって引数が偶数ならTrue、奇数ならFalseを返す関数です。filterと偶数判定のラムダ式を組み合わせてリストから偶数を集めて返すコードになります。

 

話を戻して引数(p)の倍数は除く(ふるいにかける)ようにfilterして新しいリストを返す関数を考えましょう。なお、引数(p)は素数なので結果から落とさず、リストの先頭にくっつけて含める必要があります。

 

primes' p ns = p : filter (\n -> n `mod` p /= 0) ns

 

引数名は少し工夫しました。短い方が見やすいことがあります。pは素数です。nは自然数です。nsは自然数のリストです。haskellでは、ある値のリストを表す変数名にはps, ns, xs, ysのように末尾にsを付ける慣習があります。また、途中のコロンは演算子です。これもインタプリタで確認してみましょう。

 

> :t (:)

(:) :: a -> [a] -> [a]

 

:、+、*のような記号のみの演算子の型を見るには()でくくってください。型を見るとaという任意の型の値とそのリストを受け取り、新しいリストを返しています。これで想像できるかもしれませんが、リストに値を追加して新しいリストを返す演算子のようですね。もちろん型だけでは全てはわかりません。実際に実験して試してみましょう。

 

> 3 : [1,2]

> [3,1,2]

 

なるほど、先頭に追加されるのですね。終端に付く実装も考えられるので、こういうのは動かしてみないと型だけでは分からない部分です。

 

さて、新しいprimes'をよく見てみるとどこかおかしいです。もともと考えていた仕様を思い出すと、素数のリストを求めるには次々にふるいにかけるというループ構造になるわけですがループしていません。再帰呼び出しもないですし。

 

えーっとどうすればいいのかな。ふるいに書ける数がどんどんずれていくという部分がループですからそこで再帰呼び出しすれば良さそうです。考え中・・・まず、ふるいにかけたリストに別名を付けておきましょう。このように式が複雑な部分には適宜別名を付けるのはプログラミングの一般的な手法ですね。

 

primes' p ns = p : ns'

  where ns' = filter (\n -> n `mod` p /= 0) ns

 

単純な置き換えをしただけです。filterほにゃららの部分が長いのでns'という新しい名前を付けました。

新しい名前付けのことを関数型言語では束縛って言ったりします。一度しか代入できない変数と見ても大体OKでしょう。

 

さてまだ状況は変わらずです。どうしましょう。考え中・・・(楽しい) とにかくprimes'を再帰呼び出ししてみようかな。

 

primes' p ns = p : primes' undefined undefined

  where ns' = filter (\n -> n `mod` p /= 0) ns

 

primes'の引数にundefiendを置いて再帰呼び出ししました。さてundefinedで仮置きした引数をどうすれば正しいループになりますか?前回書いたポイントのとおり再帰呼び出しは、呼び出しの度に引数が変わらなければなりませんね。

 

primes' p ns = p : primes' (head ns') ns'

  where ns' = filter (\n -> n `mod` p /= 0) ns

 

最初の引数(head ns')はふるいに書けたリストの先頭です。これは次の素数ですね。[2,3,4,5,6,7...]というリストから2の倍数を除くと[3,5,7...]というリストns'が得られます。したがってhead ns'は3です。二つ目の引数はふるいにかけた後のリストns'をそのまま渡します。ちゃんと再帰呼び出し時の引数が変わっていますね!

 

さて再帰呼び出しのもう一つのポイントを考えます。きちんと停止するか?ですが、上記は今のところ停止条件が書かれていません。再帰呼び出しが発生するパスしかありませんね。この場合の停止条件は何でしょう。引数のリストnsはfilterすることでどんどん短くなっていきますね。したがってnsが空になったら再帰呼び出しはせずに停止しましょう。停止すると言っても何もしない訳にはいきません。haskellの関数は何かしら値を返さないといけないのですから。この関数の戻り値の仕様を思い出すと、ふるいにかけた後のリストを返すという仕様です。したがって、nsが空の場合は何も返せないということで空リスト[]を返すのが正解です。

 

primes' p ns =

  if null ns then []

  else p : primes' (head ns') ns'

    where ns' = filter (\n -> n `mod` p /= 0) ns

 

おっと新しい関数を出してしまいました。型を見る癖をつけましょう。

> :t null

null :: [a] -> Bool

 

ついでに実験をしましょう。GHCiでサクサク実験!

> null []

True

> null [1]

False

 

見ての通り、空リストかどうか判別する関数です。

 

primes'は完成したので試してみましょう

 

> primes' 2 [2..10]

[2,3,5,7]

> primes' 2 [2..100]

[2,3,5,7,11,13 省略 89, 97]

 

リストは..で省略表記できます。もう少し細かいルールがありますが、今回は説明しません。ともかく素数リストができてますね!!

 

関数型プログラミングの特徴の一つですが、全てが関数であり引数にしか依存しないのでテストが行いやすいです。今回undefinedを多用して(話がしやすいので)トップダウンで作成してますが、このテストのしやすさはむしろボトムアップの方が向いているかもしれません。といっても今回のようなIOの無いプログラムならどの言語でも大して変わらないかもしれませんが。

 

今回はここまでにして、次回は下請け関数primes'と、本来の関数primesを繋げましょう。まだprimesの方はundefiendでしたね。それで問題回答プログラムを完成させたいと思います。

 

以上。