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

 

技術者コラム

 
フォーム
 
第14回目:Clojureで8クイーン問題にチャレンジ (Part1)
2014-05-18
筆者:村田
 
こんにちは。
 
今回から8クイーン問題にチャレンジしたいと思います。8クイーン問題は有名な問題として名前だけは知っていましたが、その内容と解法を初めて見たのは情報処理試験の過去問でした。情報処理試験は覚えることが多くて大変ですが、アルゴリズム問題は記憶問題では無いので考えていて楽しいです。ま、実際の試験では時間制限があって楽しめる余裕なんかありま温泉ですがTT
 
過去問では手続き型の疑似言語を使用してforループで書かれていましたが、今回は関数型言語Clojureを使用して再帰ループで考えてみようと思います。
 
はじめに8クイーン問題について簡単に説明しておきます。8x8マスの盤面において縦・横・斜めの線上に駒(クイーン)が1つしか無いように8個の駒を配置するという問題です。並べ方は複数通りありますが、そのうちの1通りを求めることを目標にしたいと思います。具体例を見た方が分かりやすいです。マス目を減らして4クイーン問題の解答を以下に示します。
 
+-+-+-+-+
| |Q| | |
+-+-+-+-+
| | | |Q|
+-+-+-+-+
|Q| | | |
+-+-+-+-+
| | |Q| |
+-+-+-+-+
 
次はClojure言語について紹介したいと思います。一言でいえばJavaVM上で動作するLispです。以上です。。。えー語れるうんちくがありません。つまらないです、残念です。うんちくといえば、かつてうんちく王を名乗っていた某芸人コンビが、私の好きな芸人さんです。昔オールナイトニッポンでパーソナリティをされていたのですが、それを今でもPCやiPhoneで聞いています。電車の中では顔がニヤニヤしてしまうので、空いているときしか聞けません:)
 
さてもろもろ始める前に環境準備についてポイントがあります。前回のHaskellはどんなエディタで書いても特に困ることはありませんが、ClojureというかLispは括弧のネストが複雑になりやすいのでエディタのサポートが欲しいところです。()のハイライト表示や自動インデントがあると便利です。私はemacsでclojure-modeを試していますが、VimやEclipseでもツールがあるみたいです。実行環境については、Clojure本体(clojure-1.6.0.jar)をダウンロードして以下のようにjavaコマンドで起動できます。JavaVMとClojure本体以外必要なものが無いので簡単です。
 
$ java -cp clojure-1.6.0.jar clojure.main
...
user=> (対話モードで起動します)
 
またleiningenというclojureのプロジェクト管理・ビルド管理ツールがあります。リッチな環境が欲しければこちらをインストールしても良いです。leiningenで対話モードを起動するコマンドは以下の通り。
 
$ lein repl
...
user =>
 
REPLとはread-eval-print-loopの頭文字です。なんて読めばいいのでしょうか。れぷる?あーるいーぴーえる?、私は最初に心の中で浮かんだのが「りっぷる」でしたのでそう呼んでます。学生時代に初めて組んだバンド名がそんな名前だったのです。そんなことより意味ですね。入力読み込み、式の評価、結果表示を繰り返す対話環境のことです。前回まで使っていたhaskellのインタプリタ(ghci)のように式を入力してちょこちょこ実験できます。あと細かいことですが、RubyのirbやHaskellのghciなどインタプリタとして実行できる環境とREPLは同義ではありません。Clojureはインタプリタ言語ではなく、Javaバイトコードにコンパイルして実行されます。
 
今回のプログラムも小さく、1ファイルに書くだけになりそうです。凝ったことをやらないので上記どちらの方法でも問題ないと思います。
 
さあ何はともあれプログラム言語を覚えるには手を動かさなければなりませぬ。早速いくつか試してみましょう。
 
$ lein repl  (または $ java -cp clojure-1.6.0.jar clojure.main)
...
user=> (println "Hello, maittane!")
Hello, maittane!
nil
 
動きました!実行方法を確認できたので一歩前進です。構文は(関数 引数)という形で、()で括ります。この()で括ったものをフォームといいます。Clojureはフォームをネストしたり並べたりしてプログラムを書いていきます。
 
出力内容を見ると2行ありますね。1行目はprintln関数の出力した文字列です。(println関数の副作用ともいいます) 2行目がフォームの値です。println関数は値としてnilを返したということです。ClojureもHaskellのように関数型言語として雰囲気が強いですね。プログラムの構成要素の中心は関数・式であり、あらゆるものが式として値を返すというのが関数型言語の特徴です。次は簡単な演算を試しましょう。
 
user=> (+ 1 2)
3
user=> (* 2 3 4)
24
user=> (- 10 2 4 1)
3
user=> (/ 10 2)
5
user=> (rem 10 4)
2
user=> (/ 10 3)
10/3
 
ふ〜ん。ほ〜ん。って感じでしょうか。(1 + 2)と書くとエラーです。Clojureは演算子も関数なので特別扱いはありません。最初のprintln関数と同じようにフォームの第一要素に演算子を書きます。2、3番目の例では3つ以上の数を渡しています。(10 - 2 - 4 - 1)と書くよりもタイプ数が減りますが、ちょっと慣れが必要ですね。remは余りの演算です。最後の例は面白いですね。割り切れない場合は分数で表示されました。約分とかしてくれるのかな?
 
user=> (/ 20 6)
10/3
 
ほほほ〜。では分数同士の足し算も試してみたいですね。
 
user=> (+ (/ 1 3) (/ 1 2)) ;; 1/3 と 1/2 の足し算
5/6
 
ちゃんと通分して計算できます。ついでにコメントの書き方も覚えます。;で文末までコメントが書けます。Lispと同じです。1個だと見づらいので;;と2個続けて書いています。
 
REPLの終了方法ですが、javaコマンドで起動した場合はCtrl-Dでぶちっと終了しちゃってください。leiningenの場合は(quit)って入力すると終了できます。
 
user=> (quit)  or Ctrl-D
 
そろそろ8クイーンに関連させていかなければ。ファイルに書けるようにならなくちゃ。
 
$ emacs -nw eightqueens.clj
 
(println "eightqueens solver!")
 
と書いて保存。拡張子はClojureの略でcljです。
 
以下のようにしてjavaコマンドを起動すれば直接スクリプトとして実行できます。
 
$ java -cp clojure-1.6.0.jar clojure.main eightqueens.clj
eightqueens solver!
 
leiningenではプロジェクトを作成しないといけないので割愛します。今回は直接実行するのではなくREPLからファイルを読み込んで実行するようにしたいと思います。これならjavaコマンドでもleinでもどちらでも同じように動きます。REPLから読み込むには以下のようにload-file関数を実行します。
 
user=> (load-file "eightqueens.clj")
eightqueens solver!
nil
 
今後は基本的にファイルに書きためていきますが、REPLにフォームを入力して実験したりもします。REPLで実験し、うまくいったらファイルに書いてのループでプログラミングしています。それでは8クイーンに取りかかりましょう。まず盤面の大きさの定数を作ってみます。
 
(def board-size 8)
 
defを使って変数に値を設定します。簡単。REPLで読み込んで確認してみましょう。
 
=> (load-file "eightqueens.clj")
#'user/board-size
=> board-size
8
 
2行目はload-fileの値です。ファイルを読み込んだときに最後に実行したフォームの結果です。つまり(def board-size 8)というフォームの実行結果です。3行目で変数が定義されているか確認してみました。
 
っていうところで今回は終わりにします(~_~) 全然8クイーンに絡んでいませんが、次回こそは解決に絡むコードを書きたいと思います。よろしくお付き合い下さい。
 
以上。
 
第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はプロジェクトにする程じゃないサンプルコードを書けるので便利です。
 
・今回書いたプログラム
 
 
・上記をもう少し奇麗に書いたプログラム
 
以上。
 
第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でしたね。それで問題回答プログラムを完成させたいと思います。

 

以上。

 
第11回目:Haskellで問題を解く (Part2)
2014-04-27
筆者:村田
 
こんにちは。
 
早速プログラムの続きを書いていきたいと思います。
 
[Haskellでループを書く]
前回のif式では素数で割り切れなかった時の処理が書きづらいので以下のように書き直しました。
 
largePrimeFactorOf x =
   if x `mod` prime == 0 then
     if x `div` prime == 1 then prime
     else undefined
   else undefined
   where prime = head primes
 
次に2つのundefinedの部分ですが最初の方から考えてみます。素数で割り切れたけど商は1でないので、まだ割れるかも?ってことで処理を「繰り返し」たいです。ここが一つ難所です。Haskellの変数は再代入できないので、forやwhileといった関数内で処理を繰り返す方法がありません。そこでHaskellでは再帰を使ってループを書きます。
 
再帰でループを書くとき、以下の2点を考えることがポイントになります。再帰は自分自身を呼ぶわけですが、ただ呼ぶだけなら無限ループになっちゃいますよね。
1. 呼ぶ際には引数の値が変わること。
2. 引数の変化を見てどこかでループを停止させること。(自分自身を呼ばない)
 
今回は素数で割った商を再帰時の引数に与えることで引数が変化します。また商が1の時、これ以上再帰呼び出しせず素数を返すので停止します。これで先程の2点をクリアしてますね。書いてみましょう。
 
largePrimeFactorOf x =
   if x `mod` prime == 0 then
     if x `div` prime == 1 then prime
     else largePrimeFactorOf (x `div` prime) -- 再帰呼び出し
   else undefined
   where prime = head primes
 
なお、この未完成状態でもundefinedのパスを通らないような数ならばテストできます。
 
> :r
> largePrimeFactorOf 8
2
 
[またもやループで悩む]
さて次はもう一つのundefinedです。ここは素数で割り切れなかったので次の素数で割ってみるという処理です。ここもまたループが必要ですね。次の素数を使って繰り返し処理を行いたいのです。ところが今のlargePrimeFactorOfは常に素数配列の先頭(head primes)の素数、つまり2でしか割れません。どげんかせんと・・
 
Hakellの関数は同じ引数で呼ぶと同じ結果しか返りません。「副作用が無いから」、「再代入が無いから」、といった細かい話は置いておいて、ともかく関数の動きを変えるには"外から引数で渡すしか無い"のです。
 
ということで、2以外の素数に変えて割っていくためには、素数を引数に持っていき関数の外から渡すようにしましょう。largePrimeFactorOfに引数を増やしてもいいですが、この関数は問題文に合わせて引数1個で呼びたいのでlargePrimeFactorOfから呼ぶ下請け関数を作りましょう。
 
またまた関数の型から考えます。割られる数と割る素数を引数に与えて、戻り値は問題の答えとなる最大素数でいいでしょう。
 
largePrimeFactorOf' :: Int -> Int -> Int
largePrimeFactorOf' = undefined
 
関数名は末尾にシングルクォート(プライム)を付けてみました。再帰ループのためだけの下請け関数のように、新しい名前のつけづらい関数によく使います。型は引数->引数->戻り値です。
 
元の関数からこの関数を呼び出す部分の処理を書いてみます。良く分からないところはundefinedにしておきましょう。
 
largePrimeFactorOf :: Int -> Int
largePrimeFactorOf x = largePrimeFactorOf' x undefiend --下請け関数を呼ぶ
 
largePrimeFactorOf' :: Int -> Int -> Int
largePrimeFactorOf' x undefined =
  if x `mod` prime == 0 then
    if x `div` prime == 1 then prime
    else undefined
  else undefined
  where prime = undefined
 
undefinedだらけになってしましいました。下請け関数の2つ目の引数は、素数配列のインデックスにしてうまくいきそうです。リストから先頭を取り出すには head primesとしていましたが任意のインデックスで取り出すには primes!!3 のように!!演算子が使えます。ちなみにインデックスは0から始まります。次は一気に書きます。
 
largePrimeFactorOf :: Int -> Int
largePrimeFactorOf x = largePrimeFactorOf' x 0 -- 最初の素数は0番目
 
largePrimeFactorOf' :: Int -> Int -> Int
largePrimeFactorOf' x primeidx =
  if x `mod` prime == 0 then
    if x `div` prime == 1 then prime -- ここが停止条件
    -- 素数で割った商を引数に再帰呼び出し
    else largePrimeFactorOf' (x `div` prime) primeidx
  -- 割られる数はそのままで次の素数インデックスを引数にして再帰呼び出し
  else largePrimeFactorOf' x (primeidx + 1)
  where prime = primes !! primeidx
 
ロードして試してみましょう
> :r
> largePrimeFactorOf 30
5  (2*3*5)
 
> largePrimeFactorOf 99
11 (3*3*11)
 
うまく動いていそうです。次回は素数のリストをちゃんと作りたいと思います。
 
以上
 
第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]
というところで続きは次回にしたいと思います。明日は情報処理の試験があるのですが、試験前って掃除したりプログラム書いたりしたくなります。その昔、学生だった頃ですが、試験前になるとベースの練習が妙に捗っていたのを思い出しました。なぜか指の調子がいい気がしたのです。
 
以上
 

連載記事のソースコード

連載記事のソースコード
 
・Haskellで問題を解く(Part1〜Part4) ソースコード
・Clojureで8クイーン問題にチャレンジ(Part1〜Part5) ソースコード
・OCamlでへびゲームを作る(Part1〜Part5) ソースコード
・Swiftでオセロを作る(Part1〜Part5) ソースコード
・Processingでシューティング(Part1〜Part4) ソースコード 
Haskellでテトリス(Part1〜Part9) ソースコード
・プチコン3号(BASIC)でさめがめ(Part1〜Part3) ソースコード
・Prologでさめがめを解く(Part1〜Part6) ソースコード