人気ブログランキング | 話題のタグを見る

Haskell によるボウリングの得点計算プログラム

Haskell Bowling という記事にあったボウリングの得点計算プログラム

実行例:
Main> score [10,10,10,10,10,10,10,10,10,10,10,10]
300
Main> score [7,2,6,4,10,5,2,7,3,8,1,6,3,9,1,10,7,2]
128

プログラム:
score :: [Int] -> Int --read as "score has the type int list mapped to an int"
score ([]) = 0
score (x:[]) = x
score (x:y:[]) = x + y
score (x:y:z:[]) = x + y + z
score (x:y:z:xs) = if  (x == 10)             then x + y + z +  score(y:z:xs)
                   else if (((x + y) == 10)) then x + y + z +  score(z:xs)
                   else x + y + score(z:xs)

例によって再帰的定義だ。

score ([]) = 0, score (x:[]) = x, score (x:y:[]) = x + y はいずれも終了条件。ボールを投げなかったら0点、1投だけの時はその時に倒れたピンの数。2投だけの時は1回目と2回目のスコアの和が得点になる。

score (x:y:z:xs) = ... が再帰的定義の部分で、 x == 0 の時はストライクなので、得点10に次の得点とその次の得点を加えて、score (y:z:xs) つまり、次の回以後の得点に加算する。x + y == 10 すなわちスペアの時は、x + y つまりスペアの10点と次の一投の得点を加算して、score (z:xs) の次の回以降の得点に加算する。ストライクでもスペアでもない時は、その回の2投分の得点を次の回以降の得点 score (z:xs) に加算する。

上の再帰的定義では右側の score 関数の引数のリストが、ストライクの時は (y:z:xs) でその他の時は (z:xs) になっているのがポイントだ。これがストライクとその他の場合の一回に投げるボウルの個数の違いを吸収している。

どうやら Haskell で繰り返しの操作をコンパクトに記述するコツは、問題をどうやって再帰的な定義で表現できるかを発見するかにかかっているようだ。手続き型の言語では繰り返しをループで記述するが、Haskell ではそれを再帰関数で定義するだけのことだ。

再帰関数は等号の左側にも右側の定義する当の関数が現れて戸惑うが、「求める関数がすでに分かっていると仮定して、引数の減少が起きる前後のその関数の関係だけを記述する」という再帰的定義のポイントをつかんでしまえば、アルゴリズムをループの時と同様に簡単に発見できる。

要は慣れの問題だ。「求める関数は既に分かっていると仮定する」という発想を受け入れてしまえば再帰的定義も案外わかりやすい。

ところで、このボウリングのスコア計算の問題点は、すべてのゲームが終了してからでないと計算ができず、途中経過が分からないという所だが、これも遅延評価とエラートラップを利用すれば解決できるような気がするがまだプログラムとして実現するほどの知識がない。

リアルワールドの問題になってくると Haskell も手続き型の言語もそう差がなくなってくるのかもしれない。Haskell であろうと手続き型の言語であろうと、得意とする処理は簡潔にかけるし、苦手な部分は冗長になってしまうのだろう。適材適所ということだ。
by tnomura9 | 2009-09-03 20:27 | Haskell | Comments(0)
<< 差分をプログラムする Haskell と意味論と統語論 >>