Bowling is a tricky game to score. It’s just complicated enough to act as a good programming exercise. And Ron Jeffries has performed this exercise many times, in C#, Smalltalk, and other languages. He’s been searching for a tidy and elegant solution, one which makes the rules of bowling as clear as possible.

In the past, though, Jeffries has been a bit skeptical of Haskell implementations of bowling:

The recursive [Haskell] solution, however, is questionable on more fundamental grounds. A game of bowling consists of ten frames, not less or more, and the "ten-ness" of the game is not represented in the recursive solutions at all. Even if we let that slide, the recursive solutions make it a bit hard to understand what's going on.

Let’s see if we can do better. No knowledge of bowling is required–if we do this right, our program should be at least as clear as an English-language version of the rules.

Along the way, we’ll encounter lazy lists, an interesting recursion combinator, and Hoogle, the Haskell search engine.

The rules of bowling

In bowling, we roll balls down a lane, trying to knock down pins. If we know how many pins we knock down with each ball, we can compute the final score. So our program looks something like this:

-- Pins knocked down by each ball.
type Balls = [Int]

-- Number of points scored.
type Score = Int

scoreGame :: Balls -> Score
scoreGame balls = ???

But how do we implement scoreGame?

Scoring a frame

A bowling game is divided into 10 frames. Ordinary frames consist of 1 or 2 balls. The 10th frame may have an additional 1 or 2 bonus balls, which we discuss below.

To score an individual frame, we need to do two things: (1) calculate the score for our frame, and (2) figure out where the next frame starts. Our scoring function will return both pieces of information:

-- Score one frame and return the rest.
scoreFrame :: Balls -> (Score, Balls)

If we knock down all 10 pins with the first ball in a frame (x1), we call it a strike, and move on to the next frame immediately. But we also get a bonus—we’re allowed to count balls y1 and y2 from the next frame towards this frame’s score:

scoreFrame (x1:    y1:y2:ys) | x1 == 10 =
  (x1+y1+y2, y1:y2:ys)  -- Strike

If we knock down all the pins using two balls (x1 and x2), we call it a spare. And we get to count one ball from the next frame as our bonus:

scoreFrame (x1:x2: y1:ys) | x1+x2 == 10 =
  (x1+x2+y1, y1:ys)     -- Spare

If we don’t manage to knock all 10 pins with two balls, we call it an open frame. And we don’t get any bonus:

scoreFrame (x1:x2: ys) =
  (x1+x2,    ys)        -- Open frame

What happens if we have a strike or a spare in the 10th frame? We get to roll our bonus balls anyway. Conventionally, these extra balls are recorded as part of the 10th frame (making it 3 balls long), but they’re really just phantom balls hanging off the end of the game.

Next, we need to turn scoreFrame into a recursive function.

Tying it all together

Let’s take another look at the type declaration for scoreFrame, and expand our type aliases:

scoreFrame :: Balls -> (Score, Balls)
scoreFrame :: [Int] -> (Int, [Int])

We can abstract this type even further, replacing the types with type variables:

[a] -> (b,[a])

Given a function of type [a] -> (b,[a]), and a list of type [a], we want to apply our function repeatedly, collecting all the values of type b into a list. So we’re looking for a function of type:

reduce :: ([a] -> (b,[a])) -> [a] -> [b]

Whenever we need an abstract function like this, our first stop should be Hoogle, the Haskell search engine. Unfortunately, Hoogle can’t find a function with this type, so we’ll need to write it ourselves:

reduce f ys = x:reduce f ys'
  where (x,ys') = f ys

This says, “Given a function f and a list ys, apply f to ys to get x and ys'. Then build a list starting with x. To get the rest of the list, call ourselves recursively on ys'.” Notice that we never bother to specify a base case! Because Haskell is a lazy language, we only compute as much of the list as we need.

If we apply reduce to scoreFrame, we get the recursive function we’re looking for:

reduce scoreFrame :: Balls -> [Score]

And now we’re ready to tie it all together:

scoreGame :: Balls -> Score
scoreGame balls =
  sum (take 10 (reduce scoreFrame balls))

Given a list of balls, we reduce it to a list of individual frame scores. Then, we take the scores of the first 10 frames and sum them.

(The full program is available in my darcs repository.)

Unit Testing in Haskell

Of course, we need some unit tests. We’ll want functions to generate lists of good and bad throws:

-- A list of 'n' perfect balls.
perfect n = replicate n 10

-- A list of 'n' gutter balls.
gutter n = replicate n 0

Here are some sample games, with the desired scores. We pay careful attention to the 10th frame:

testData :: [(Balls,Score)]
testData = [
  (10:  perfect 11, 300), -- Strike
  ( 9:1:perfect 11, 290), -- Spare
  ( 8:1:perfect 11, 279), -- Open frame
  ( 8:1: 9:1:perfect 10,  269),
  ( 7:2: 6:3:perfect 10,  258),
  (perfect 9++[10,10, 0], 290),
  (perfect 9++[10, 5, 5], 285),
  (perfect 9++[10, 0,10], 280),
  (perfect 9++[10, 0, 0], 270),
  (perfect 9++[ 9, 0],    267),
  (perfect 9++[ 9, 1, 5], 274),
  (gutter 20, 0)]         -- Missed all

We can run our tests using HUnit:

-- Construct a unit test asserting that
-- we calculate the expected score.
testFromData (balls, score) =
  ("Scoring " ++ show balls) ~:
    score ~=? scoreGame balls

-- Build a list of tests and run it.
tests = test (map testFromData testData)
main = runTestTT tests

A note on test-driven design

Few programmers are willing to write programs in public. It’s too embarrassing—too many false starts, too much confusion. We’d rather polish our programs in secret, and release only finished work.

Ron Jeffries, though, is an exception to this rule. He designs programs in public, muddling through all the obstacles. And this admirable habit does make him look bad at times.

But Jeffries takes these risks, willingly, to promote test-driven development (TDD). He begins with test cases, and grows a program organically, extending and refining it as he goes. It’s an admirably hands-on style, and I’ve seen it produce some beautiful programs.

But for this program, all the design work happened in my head, while I was away from the computer. I wrote the actual code test-first, but there was never any doubt about how scoreFrame and reduce would fit together.

Do you have a more elegant solution? Please feel free to share it!