Bowling in Haskell: A response to Ron Jeffries
Posted by Eric Kidd Sat, 28 Apr 2007 11: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
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
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 (
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 to get
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
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.
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
would fit together.
Do you have a more elegant solution? Please feel free to share it!