Bowling in Haskell: A response to Ron Jeffries
Posted by Eric Kidd Sat, 28 Apr 2007 15:53:00 GMT
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.
