Bowling in Haskell: A response to Ron Jeffries

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!

score [r1,r2,r3] = r1 + r2 + r3 score [r1,r2, b1,b2,b3 :rs] | r1 == 10 | b1 == 10 = 10 + 10 + b3 + score [b1,b2,b3:rs] = 10 + b1 + b2 + score [b1,b2,b3:rs] | r1 + r2 == 10 = 10 + b1 + score [b1,b2,b3:rs] | otherwise = r1 + r2 + score [b1,b2,b3:rs]

Tony Morris wrote on Apr 28, 2007:

You make an interesting final point. I hadn't read the article you refer to but the refutation re: Haskell (ten-ness) is really quite amateur and a failing to understand some simple type systems. Your final point refers to your ability to perform an accurate thought experiment (design and write the code) without using TDD. I have long conjectured that these hyperbolic development processes (TDD, XP, etc.) exist *entirely* to make up for one's lack of spatial cognitive abilities. Clearly, your abilities exceed the minimal requirement for writing this particular application and a TDD zealot might frown, unable to comprehend this fact. Keep up the good work.

Eric wrote on Apr 28, 2007:

Jeffries actually had a very good point, regarding the lack of "ten-ness" in the earlier Haskell solutions. In particular, he described two test cases that break the first Haskell implementation: (gutter 16++[0,0, 10,2,3], 15), (gutter 16++[10, 2,3], 20), If you're processing frames recursively (with no frame counter), you can't tell these two cases apart. In my version, I use take 10 to ensure that the program processes exactly 10 frames. All in all, I'm quite fond of TDD. At least for certain problems, it's a big win. But other problems, it's better to just go for a walk and think a bit.

Dan wrote on Apr 28, 2007:

As it happens, reduce is in the standard library, although its type is somewhat disguised. The function is:

unfoldr :: (a -> Maybe (b, a)) -> a -> [b]

Of course, scoreFrame doesn't wrap its results in Maybe, and in fact, many of the standard functions that would be useful with unfoldr (splitAt, divMod...) don't either. However, we can write a function to augment these with a stopping predicate:

stopOn :: (a -> Bool) -> (a -> b) -> a -> Maybe b
stopOn p f a =
  if p a
    then Nothing
    else Just (f a)

Now, scoreGame becomes:

scoreGame balls =
  sum . take 10
    $ unfoldr (stopOn null scoreFrame) balls

Of course, defining stopOn is just about as much work as defining reduce, so I suppose it's a bit of a wash. It might be handy if stopOn were in the standard library for just such an occasion (although stopOn probably isn't the best name, but I haven't thought of a better one yet; my initial thought was 'unless', but that's taken already), but to my knowledge, it isn't. (Apologies for the code formatting. I couldn't figure out which tag to use to get it to come out like yours (and the code tags were causing line wrapping).)

lsb wrote on Apr 28, 2007:

reduce looks kind of hairy; why not "iterate (snd . scoreGame)" ?

dmead wrote on Apr 29, 2007:

hey I'm the Dan Mead he wrote about in the original bowling article I actually wrote another implementation which we debated over email for a few weeks (similar to this, but has the same bugs as the first version). Ron seems very adamant that FP techniques are exactly the same as OOD design and theres no point in investigating recursion and all that jazz. I'd like to see if someone can some up with a recursive solution that doesn't use a counter or have the problems my version did that would be quite impressive :)

Eric wrote on Apr 29, 2007:

Thanks, dmead, for inspiring this article! I think Jeffries was right when he said that:

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.

While I'm sure it's possible to write a (correct) recursive bowling program that doesn't mention the number 10, you would have to add more complexity to scoreFrame, or add sentinel values at the end of the game. So that's why I went with take 10—it's the shortest way to build "ten-ness" into the program, and it keeps any trickiness out of scoreFrame or reduce. Also, it's better karma. ;-) Other Dan: Thanks for pointing out unfoldr! I don't always think of it when I should. In production code, it's probably better to define reduce in terms of unfoldr (or build?), if only so we get access to fusion.

Tom Moertel wrote on Apr 29, 2007:

Eric, Back when Mr. Jeffries first posted his article about the Bowling Game, I had a rather lengthy email correspondence with him, during which I attempted to argue against his claim that the "recursive style" fosters programming mistakes such as failing to account for ten-ness in the Bowling Game. I tried to show that iteration and recursion were actually equivalent and that you could even solve the problem without using either. To demonstrate the last point, I sent him a new version of "my earlier, somewhat-golfed solution":http://blog.moertel.com/articles/2006/04/05/the-bowling-game-kata-in-haskell. The new version had an interesting way of accounting for ten-ness, which I'll post below in hopes you find it amusing: -- compute score of a full game of bowling score2 rs = fst . s.s.s.s.s.s.s.s.s.s $ (0, rs) where s = uncurry sc2 -- consume and score 1 frame from 'rs', accumulating score in 's' sc2 s rs = case rs of 10:rs' -> sc' 3 rs' x:y:rs' | x + y == 10 -> sc' 3 rs' | otherwise -> sc' 2 rs' _ -> error "ill-formed sequence of rolls" where sc' n rs' = ((s + sum (take n rs)), rs') Cheers,
Tom

Chris Kuklewicz wrote on Apr 30, 2007:

Converting the list of balls to a score is a simplified parsing problem. I made the intermediate parsed form explicit and I have posted my version of Haskell bowling to the Haskell wiki (along with a link to this blog post). My version uses an inferred (StateT [Int] (Either String) Frame) to keep track of the remaining balls while parsing and handle the possibility of encountering bad input. I ran it through Eric's tests above and it passed. The error checking in my code emphasizes the rules and helps make them "as clear as possible". Since I want to detect errors, a simple (take 10) might have returned fewer than 10 frames. The problem of how to account for exactly 10 frames is handled by using replicateM in the line frames <- replicateM 10 (StateT parseFrame) The above is purely declarative, and there is no need for me to use any kind of counting parameter or write any comparison tests or increment/decrement anything. As a bonus, the parsed frames are stored in an array and can be decoded by 'toBalls' into a list of list of pins.

Eric wrote on Apr 30, 2007:

Tom, Chris: Thank you for the interesting solutions! Tom's solution is pretty twisted, but it contains lots of crunchy bits of Haskell goodness. Chris' solution is a bit more practical. In particular, it reports errors, which is vital if you can't trust your input. If we're going to handle invalid input, it would be desirable to have "negative" test cases--invalid inputs, and the errors they should produce.

Isaac Gouy wrote on May 12, 2007:

iirc all of the bowling game examples assume valid input data (and mostly assume complete games). So in the bowling game examples, the “ten-ness” of the game is not caused by a need to check for the end of the game, it's caused by the need to distinguish bonus rolls from rolls.

The bonus rolls do not themselves contribute to the score, they are only included as part of bonus for some other strike or spare roll. The difference between bonus rolls and rolls isn't captured by [Int] so we have to recover that lost information by frame counting till the tenth frame.

Represent both bonus rolls and rolls in the data, and the need for frame counting disappears.

[ Roll 10 ,Roll 5 ,Roll 5 ,Roll 10 ,Roll 5 ,Roll 5 ,Roll 10 ,Roll 5 ,Roll 5 ,Roll 10 ,Roll 5 ,Roll 5 ,Roll 10 ,Roll 5 ,Roll 5 ,BonusRoll 10 ]

Here's a Clean pattern matching program that will score correct incomplete games and score correct complete games. No doubt it's easy to do the same thing in Haskell. It's recursive. It just stops based on the data coming to an end. It doesn't basically count up to or down from ten.

:: R = Roll !Int | BonusRoll !Int score :: !.[R] -> Int score [] = 0 score [_] = 0 score [r1, r2] = if (roll r1 + roll r2 < 10) (roll r1 + roll r2) 0 score [r1, r2, r3 :rs] | roll r1 == 10 = roll r1 + bonus r2 + bonus r3 + score [r2,r3:rs] | roll r1 + roll r2 == 10 = roll r1 + roll r2 + bonus r3 + score [r3:rs] | otherwise = roll r1 + roll r2 + score [r3:rs] roll (Roll i) = i roll (BonusRoll i) = 0 bonus (Roll i) = i bonus (BonusRoll i) = i

Isaac Gouy wrote on May 16, 2007:

Talking with Dan Mead, I think he was on the right track. Let's go back to the scoresheet used to score bowling games. The top row, where rolls are recorded, is a 9x2 1x3 template. iirc the examples I've seen don't use that template, but extract rolls and ignore implicit information. The examples I've seen use an irregular compressed representation

[10,   10,   10,   10,   10,   10,   10,   10,   10,   10,10,10]

instead of that regular 9x2 1x3 scoresheet template

[10,0, 10,0, 10,0, 10,0, 10,0, 10,0, 10,0, 10,0, 10,0, 10,10,10]

How strange that we're writing scoring programs that don't have all the information available to people using a bowling scoresheet! Let's use those 9x2 1x3 scoresheets!

Seth Tisue wrote on Jan 08, 2009:

Isaac, You write "How strange that we’re writing scoring programs that don’t have all the information available to people using a bowling scoresheet!" I don't agree that it's strange. A bowling scoresheet doesn't think for you; you have to know how to use it. If you're scoring and you see a player knock down 4 pins, you have to know what box to write the 4 in. The input format you suggest assumes that part of the problem is already solved before your code runs. So of course your code is shorter and simpler!

Tracy Harms wrote on May 01, 2009:

The verbal description of bonus for strikes is inaccurate. It says the bonus is two balls from "the next frame" but in fact it is the pin tally from next two balls, regardless of what frames they are in.

The rules of bowling

Scoring a frame

Tying it all together

Unit Testing in Haskell

A note on test-driven design

More posts