ボウリングの得点計算

実行例：

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 [] = 0
score (x:[]) = x
score (x:y:[]) = x + y
score (x:y:z:[]) = x + y + z
score (x:y::z:xs)
  | x == 10 = x + y + z + score (y:z:xs)
  | x + y == 10 = x + y + z + score (z:xs)
  | otherwise = x + y + score (z:xs)

プログラムの解読

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

score ([]) = 0, score (x:[]) = x, score (x:y:[]) = x + y, score (x:y:z:[]) はいずれも終了条件。最終のボーナスフレームだ。１フレームに３回までボールが投げられる。

ボールを投げなかったら0点、１投だけの時はその時に倒れたピンの数。２投だけの時は1回目と2回目のスコアの和、３投のときは３投の合計が得点になる。

５行目以下のプログラムは再帰的定義になる。x == 10 はストライクのとき、x + y ==10 はスペアのとき、otherwise はストライクでもスペアでもないときだ。

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

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

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

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

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