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

 

技術者コラム

 
フォーム
 
第13回目:Haskellで問題を解く(Part4)
2014-05-11
筆者:村田
 
こんにちは。
 
前回は素数のリストを作るためのループ用下請け関数primes'を作りました。これから完成させたい素数リストの型と下請け関数を再掲します。
 
primes :: [Int]
primes = undefined
 
primes' :: Int -> [Int] -> [Int]
primes' p ns =
  if null ns then []
  else p : primes' (head ns') ns'
    where ns' = filter (\n -> n `mod` p /= 0) ns
 
それではこの下請け関数を使って素数リストを完成させるところから始めたいと思います。primesからprimes'をどう呼べばいいのか考えます。とりあえず引数にプレースホルダを置いてみると以下のようになります。
 
primes = primes' undefined undefined
 
primes'の第1引数は素数です。最初の素数を渡すので2です。
 
primes = primes' 2 undefined
 
ここまではいいとして、第2引数の自然数リストはどうしましょう。2から始まるとして終端は問題文の数600851475143でもいいです。答えの素数がこの数より大きいことはあり得ませんから。(600851475143の平方根まででもいいです)
しかし、これでは問題によって終端をハードコーディングすることになり、うまくないですね。終端の数をprimes関数の引数として貰えばいいのですが、primes::[Int]から型を変えたくないので、今回はhaskellならではのトリックを用いて、終端を決めずに無限リストにすることにしました。[2..]と書きます。haskellは遅延評価という評価戦略を取っており無限リストや無限ループでも正しく動くのです。無限が扱えるというのは違和感があると思いますが、そういうもんだって程度で進みましょう。primesはprimes'に無限リストを渡して完成です。
 
primes :: [Int]
primes = primes' 2 [2..]
 
試しにprimesを使ってみましょう!
 
> primes
[2,3,5,7........大量の出力に慌てずCtrl-c連打で止めてください!
 
無限素数リストですから出力が止まりませんので、出力数を100個にしてみましょう。
 
> take 100 primes
[2,3,5,7 省略 521,523,541]
 
takeとは何?と思ったら型を調べます。
> :t take
take :: Int -> [a] -> [a]
 
数値とリストを渡してリストをもらう。これだけだとよくわかりません。型を調べる癖は必要ですが、結局マニュアルみたりググったり実験は必要ですね。
 
> take 1 [1,2,3]
[1]
 
> take 5 [1,2,3]
[1,2,3]
 
> take 0 [1,2,3]
[]
 
色々実験してみてください。
 
さあ、とうとう無限素数リストを手に入れたので問題の回答に使ってみましょう。largePrimeFactorOfはすでにprimes関数を呼んでいるので実はこれで完成です!どきどきしながら最初は例題13195を与えてみましょう。
 
> largePrimeFactorOf 13195
29
 
おお、いけてそうです。さて随分完成までに時間がかかりましたが、いよいよEular問題の数を与えてみましょう。
 
> largePrimeFactorOf 600851475143
 
答えはでましたか?Project Eularのサイトで答えを入力して正解すると結構嬉しいですよ~
 
以上ですがどうでしょうか。私がHaskell初心者なので本格的なコードの解説はまだ書けないですけどHaskellの雰囲気がほんの少し伝わればいいなと思います。
 
[まだまだこのネタ終わらせない・・雑談]
今回のコードの大きなポイントは素数"リスト"を使ったことです。無限リストではなくても問題の数までの素数リストがあれば良いので、他の言語でも素数リストを作り、問題に回答するプログラムを作れます。しかし、今回の問題のように6000億超えの数に含まれる素数リストを作るとなるとメモリ・実行時間がとても大きくなってしまいますので、実際には別のアルゴリズムを考える必要があります。
 
今回のhaskellのコードはすぐに回答が返ってきます。ここが遅延評価のいいところです。primesは無限リストとして定義されていますが、『必要になるまで』計算を行いませんのでメモリや実行時間の無駄はありません。無限素数リストであるprimesを使ったアルゴリズムは分かりやすいです。"そこに素数リストがある"という前提でプログラムを書くことができ、素数リスト生成の実装はprimes::[Int]からは見えてこない、というか見せていないのです。このように関数型プログラミングでは、アルゴリズムの手続きを見せず、宣言的にプログラムを書きやすい傾向があります。おまけに、Haskellでは遅延評価により効率もいいのです。
 
最後に今回のコードの全体と、パターンマッチなどを使ってもう少し整理したコードを載せます。Gistは色が付いて見やすいですね。Gistはプロジェクトにする程じゃないサンプルコードを書けるので便利です。
 
・今回書いたプログラム
 
 
・上記をもう少し奇麗に書いたプログラム
 
以上。