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

 

技術者コラム

 
フォーム
 
第10回目:Haskellで問題を解く (Part1)
2014-04-19
筆者:村田
 
こんにちは。
 
『はじめに』
今回はHaskellについて書きたいと思います!前回の続きを書こうと思って前の投稿を見てみると3ヶ月前ですか、うーん。
 
『そして言い訳』
えー突然ですが漫画家十訓というもののインスパイア(?)でプログラマ十訓なるものを見たことがあります。
「まずは書け」
「楽しんで書け」
・・・
とこんな感じの内容だったと思いますが、特に覚えているのが「飽きたら新しいのを書け」です。業務ではさておき、こうして自宅のデスクトップには残骸が生まれるわけです。そんな訳で前回投稿のコードは放置して別のコードにしましょ:P
 
『問題探し』
さてHaskellで何を書こうかということですが、しばらく考えてもいい案が浮かびません。I/Oはしたくないのでファイル、通信、コンソールはパスです。ググってもイマイチ良さげな問題が見つからず、そこで今回はProject eular(オイラー)から探すことにしました。ご存知の方もいるかもしれませんが、計算量が多い数学の問題が出てくるサイトです。以前は別の言語でトライしていたのですが、これならHaskellでいけそうです。
 
『素因数分解!?』
Problem 3 "Largest prime factor" に決めました。
(自分で解きたい場合、以降は後で見た方がいいです)
 
問題は600851475143を因数分解して最大の素数を求めよという問題です。
(例 13195の場合は5*7*13*29なので29です)
 
因数分解、まずはそこからうなってしまいました。小さい素数から順に割っていって、えーっと、、(紙でちまちま因数分解を練習中・・・)素数で割った結果の商が1になったらそれが最後の素数、一番大きい素数ってことでいいかな。自信がないんですけど^^;
 
『実行環境』
さて今回は完成版プログラムをいきなり示すのではなく、どのようにコードを書いていったのかを順を追うように進めたいと思います。投稿数も増やせますし:-)
 
そういえば実行環境について一切触れていませんでした。Haskell Platformってのを入れています。GHCというコンパイラ、GHCiというインタプリタ、その他頼もしいライブラリがたくさん付いてきます。基本的にはGHCiでヌルサク実験する感じで楽しくコーディングしましょう。
 
$ ghci でインタプリタを起動します。まず覚えておくべきコマンドは以下3つです。コロンから始まります。
 
:l ファイル名 ファイルに書いたHaskellコードをロードします
:r              前回ロードしたファイルを再読み込みします(楽チン)
:t 式            Haskellの式(コード)の型を表示します
 
『まずは指ならし』
さて3ヶ月ぶりになりましたが改めてHaskell、Start!!
 
最初にコメントの書き方と基本的な実行を練習です。プログラムを書いているとコメントアウトをしたくなったりしますしコメント化は最初に覚えるスキルですね。
 
$ emacs -nw renshuu.hs   ファイルを開く
 
-- 足し算          コメントはハイフン2つで始まる
add a b = a + b    これは自作のadd関数定義
 
$ ghci                        ghciコマンドでインタプリタ立ち上げ
> :l eularProblem3.hs   ">"プロンプトが出たら:l でロード
> add 1 2                   自作addに引数を与えて呼ぶ
3                               結果表示
 
よし、OKOK
今後上記のようにファイルに書いて :l または :r で読み込み、関数を呼び出してテストすることにします。ガンガン関数を呼んでグイグイ実験してインタプリタと会話するようにコーディングしましょ!
 
『だが早速雑談』
問題に回答する関数を考えてみます。
 
が、その前に。Haskellでは型がとても重要です。強い型付け言語と言われる通り、型チェックは厳しく、そりゃもうしょっちゅう怒られます。しかし嫌がってはいけません。Haskellは型に関する機能が豊富です。特に型クラスという機能は型が持つ振る舞い、制約条件、コンテキストを表現し、そのため値を見ずとも型を見ることで関数の意図を想像することができます。またHaskellは"基本的に"副作用が無いので関数は引数にしか依存しません。関数の引数や戻り値の型を見るだけで関数について多くのことを類推できたりします。グローバル変数や局所性を失った状態クラスに悩まされないというのはいいことですね。
 
『型から考えよう』
そんなわけでHaskellでは関数を作るときも、まず型を考えてみることが有効なやり方です。値ももちろん重要ですけどね。
 
関数名はlargePrimeFactorOfにしようと思います。関数名や変数名は小文字から始まります。なお今回は自作の型は出てきませんが、型名は大文字から始まることも覚えて下さい。えーっと引数に600851475143を渡して結果として素数(数値)を返す関数だから、その型は・・・
 
$ emacs -nw eularProblem3.hs
 
-- これから書く関数の型宣言
largePrimeFactorOf :: Int -> Int
 
とこんな感じですね。関数名 :: 引数の型 -> 戻り値の型 と書きます。これは型宣言だけなのでコンパイルできません。これから実装を書いていくわけですが、まず型宣言が合っているかスタブを書いて確かめてみましょう。
 
largePrimeFactorOf :: Int -> Int
largePrimeFactorOf = undefined
 
これでコンパイルは通るようになります。(あ、ちなみに分かりやすいのでさっきからコンパイルと言ってますけどインタプリタに読み込ませてるだけです、ややこしくてすみません)
 
『undefinedの使い方』
ためしに実行(評価)してみましょう。えっとHaskellでは関数に引数を渡して呼ぶことを「式を評価する」って言ったりしますが、まあ細かいことは置いておきましょう。
 
> largePrimeFactorOf 13195
*** Exception: Prelude.undefined
 
これはlargePrimeFactorOfに引数13195を与えて評価してみたところです。スタブに書いた通りlargePrimeFactorOf = undefined ですがから インタプリタによってundefined 13195 に式が変換されます。次にundefinedという関数は何ぞやとインタプリタによってundefinedが評価されます。そこでExceptionが発生するというわけです。ともあれ重要なことはundefinedが含まれた関数でもコンパイルできるということと、undefinedを評価したときにエラーになるということです。これが結構便利でして、スタブにしたいポイントにはとりあえずundefinedを置いてコンパイルだけはやってみるのです。それで少なくとも型は合っているか確認できるわけです。haskellでプログラミングしていて悩んで手が止まったら、undefinedを置いて、まあお茶でも飲みましょう。
 
『道具(素数リスト)の準備』
さて小さい素数から順番に割っていくことになるので、素数の配列があると便利ですね。配列でなくても素数が順番に取り出せれば何でもいいのですけど。ともかくHaskellは配列というかリストが得意なのでリストで考えることにします。最初にバシッと素数生成関数を考えても良いのですがパッと書けなさそうだったので、ひとまず簡単な素数のリストを作ってみました。
 
primes :: [Int]
primes = [2,3,5,7,11,13]
 
型を見てみましょう。[Int]はIntのListを表します。primesは2~13までの素数のリストというわけです。
 
 
『undefinedを使って勢いだけで書いてみる』
このなんちゃって素数リストを使って問題のアルゴリズムを考えましょう。まず素数リストから素数を一つ取り出して問題の数を割ってみます。割り切れれば因数ですね。しかも商が1ならこれ以上割る必要はないのでその時割った素数が答えです。とりあえずここまで書いてみましょう。
 
largePrimeFactorOf :: Int -> Int
largePrimeFactorOf x =
   if x `mod` prime == 0 && x `div` prime == 1 then prime
   else undefined
   where prime = head primes
 
まだまだ未完ですがとりあえずエイやと書いてみました。ちょこっと説明の必要な記述がありますね。+や*のような記号ではない演算子(div,mod)についてです。こいつらを2引数の間にいれて中置演算子として使用するにはバッククォートで囲む必要があります。if文の構文は「if 条件 then 真の処理 else 偽の処理」です。haskellは全ての文が式であり(!!!)、if文も式として必ず値を持ちます。したがってelse句を省略はできません。値を返さないパスは作れないのです。上のプログラムではひとまずundefinedにしました。このように後で考えたい部分にはundefinedでどんどんスタブにしていきます。ちょっと書いたらインタプリタで:rを実行(ッターン)してコンパイルを頻繁に行うのがサクサクしてていい感じです。あとwhere句ですが、これは関数本体で使用する一時変数、一時関数を書きます。primeという変数は素数リストの先頭に束縛(代入)しています。つまりprimeは2です。
 
さて次はどうしよう。うーん最初のif式の条件部分は分けた方が良さそうな気がしますね。
だ、だって勢いで書いた条件式だし!
 
[明日は試験DEATH]
というところで続きは次回にしたいと思います。明日は情報処理の試験があるのですが、試験前って掃除したりプログラム書いたりしたくなります。その昔、学生だった頃ですが、試験前になるとベースの練習が妙に捗っていたのを思い出しました。なぜか指の調子がいい気がしたのです。
 
以上