The Bowling Kata in F# - Yup, More Bowling Katas

I actually have another non-bowling blog post almost ready to go (really!), but I had to present F# to my coworkers recently, and so I resorted to my favorite little code kata to use as an example. We didn't get much time for it in our meeting, so I said I would put it online in a blog post as well. So here it is.

I haven't gotten so far as to really get going on writing unit tests in F#, and from what I've read, it seems that there are still some issues using the MS test runner and F#, so my unit tests are written in C#. This does, however, show how the .NET languages tie neatly together for most intents and purposes.

Whether we will begin to use F# or not, I don't know. Functional programming is fun, but getting everyone proficient at using both C# and F# could prove a challenge. A decent piece on the benefits of F# was written by Kevin Hazzard, Microsoft MVP, which at least highlights some of the key things it provides.

If nothing else, functional programming is a fun and different way to think of programming compared to imperative languages like C#, C/C++, Java, etc. It's well worth the time to check it out.

So, without further ado, here is the bowling kata, written for F#.

The C# to F# Extension Method
I used my tests from my C# version of the scorer as my basis for the tests here. The content of each test is identical, but code had to change a little to accommodate F#'s immutability. That is, variables and collections in F# cannot be changed after they've been created, just as with other functional languages. However, there are ways to convert the lists, and what I finally did was to write an extension method in C# that converts a C# list into an F# list.

using System.Collections.Generic;
using Microsoft.FSharp.Collections;

namespace BowlingKataTest
{
    public static class FSharpInteropExtensions
    {
        public static FSharpList<t> ToFSharpList<t>(this IEnumerable<t> list)
        {
            return ListModule.OfSeq(list);
        }
    }
}

This allows me to just tack on .ToFSharpList() on any collection that implements IEnumerable and turn it into an immutable F# list.

Making My Rolling Easier
Also, to make my rolling of multiple balls easier, I made a short utility method as follows:

private static IEnumerable<int> RollManyBallsWithSameNumberOfPins(int numberOfBalls, int pins)
{
    for (var i = 0; i < numberOfBalls; i++)
        yield return pins;
}

The Bowling Scorer
As usual, I begin with a test, rolling all gutterballs and receiving a score of 0. Note the extension method.

[TestMethod]
public void CalculateScore_AllBallsAreGutterBalls_0()
{
    var rolls = RollManyBallsWithSameNumberOfPins(20, 0);
    var score = Scorer.CalculateScore(rolls.ToFSharpList());
    Assert.AreEqual(0, score);
}

This is solved with a simple function in F#. But first of all, let me explain the F# module header code.

#light

module Scorer

The #light keyword tells the compiler to compile this class using lightweight syntax. What this basically means is that you don't have to use as many keywords, and that whitespace formatting matters. While that sounds counter-intuitive to a c/c++/c#/java programmer, it's pretty typical in functional languages, and generally the code reads better that way. You get used to it.

"module Scorer" declares the module, which works in many ways like a C# static class. Since all methods and values in functional programming are immutable, having properties or class members doesn't make any sense. All are static. Writing a whole C# program where everything is static could make for an interesting exercise in itself.

The actual function is short and sweet.

let CalculateScore rolls = 0

I think this is pretty self-explanatory, but the most notable is that "rolls" is a parameter to the function. Note that no type is declared, and while it is possible to declare the type, the best is to let the compiler figure that out on its own.

This does not mean that F# is weakly typed, but rather that the type is determined at compile time. This is similar to using the "var" keyword in C#. If the type cannot be deduced by the compiler, you'll have to cast the value. If possible, your code will be more flexible if you can let the compiler figure it out on its own. However, you can cast it as follows.

let CalculateScore (rolls : List<int>) = 0

The test passes, so we move on testing for knocking down one pin for each roll.

[TestMethod]
public void CalculateScore_AllBallsKnockDownOnePin_20()
{
    var rolls = RollManyBallsWithSameNumberOfPins(20, 1);
    var score = Scorer.CalculateScore(rolls.ToFSharpList());
    Assert.AreEqual(20, score);
}

To solve this test, we just have to sum up all the rolls, so we do. Note that at this point it does become necessary to specify what type the "rolls" parameter is, so that the summation call understands how to use it.

let CalculateScore (rolls : List<int>) = Seq.sum rolls

Unlike languages based on C-syntax, there is no need for parentheses around the parameter when making a function call unless the call is ambiguous.

This passes both tests so far. So we move on to the next test, where the first roll is a strike, but all following rolls are ones.

[TestMethod]
public void CalculateScore_FirstFrameIsStrikeRestOnes_30()
{
    var rolls = new List<int> {10};
    rolls.AddRange(RollManyBallsWithSameNumberOfPins(18, 1));
    var score = Scorer.CalculateScore(rolls.ToFSharpList());
    Assert.AreEqual(30, score);
}

To solve this in F#, we need to make the function recursive, which allows us to score by frame. So first I rewrite the current functioning code and make sure the previous tests still pass.

let rec CalculateScore rolls = 
    match rolls with
        | x::y::rest -> x+y + CalculateScore rest
        | _          -> 0

This looks a bit more complex, but really isn't too bad. The match statement is a lot like a switch statement in imperative languages like C#, but with a wider range of match possibilities.

The rec keyword tells the compiler that this function is recursive. Then I tell the method to match the pattern x::y::rest from the rolls list, which means that x and y are split off the front of the list, and the remaining list is stored in rest. I then add together x and y and then add the result of passing rest to the recursive call.

Finally, I have to add a catchall condition, in case the x::y::rest pattern isn't matched. The underscore matches anything, like an asterisk (*) in file systems, or percent (%) in SQL. In this case I tell the call to return zero. With our current tests, this shouldn't be hit, but to compile, F# requires that you've covered all match possibilities.

I run the tests, and they pass, so then I add the strike functionality, which is a new pattern to match.

let rec CalculateScore rolls = 
    match rolls with
        | 10::y::z::rest -> 10+y+z + CalculateScore (y::z::rest)
        | x::y::rest     -> x+y    + CalculateScore rest
        | _              -> 0

The new pattern to match is 10::y::z::rest, which represents a ten, followed by two rolls y and z, and then the rest of the list. If so, it adds the ten and the next two rolls, and then calculates the score for the next frame, which includes y and z. Passing y::z::rest puts y, z and rest together into a new list that is passed to the recursive call.

Now that we've seen that we can handle one strike, we should check to see that we handle all strikes, most importantly the last one, with the two bonus balls at the end that should only be counted to score the strike.

[TestMethod]
public void CalculateScore_AllFramesAreStrikes_300()
{
    var rolls = RollManyBallsWithSameNumberOfPins(12, 10);
    var score = Scorer.CalculateScore(rolls.ToFSharpList());
    Assert.AreEqual(300, score);
}

The problem here is that the last two rolls get counted when they shouldn't, so the current code scores 320 instead of 300. The easiest way to solve that is with a frame counter. The client shouldn't have to worry about tracking frames, so I extract the frame rolling to its own function and have the original function call it with initializing values.
The first goal is to make the already passing tests pass with the new arrangement.

let rec CalculateFrame rolls frame  =
    match rolls with
        | 10::y::z::rest -> 10+y+z + CalculateFrame (y::z::rest) (frame+1)
        | x::y::rest     -> x+y    + CalculateFrame rest         (frame+1)
        | _              -> 0        

let CalculateScore rolls = 
    CalculateFrame rolls 0

Note that the order of functions is important. F# seems to evaluate from the bottom up, so CalculateFrame has to appear above CalculateScore in the source file. As you can see, CalculateScore simply calls CalculateFrame, initializing it with the starting frame, which is zero.

CalculateFrame recurses until it runs out of frames, then totals up the score as it resolves back to the calling function. Since, as I mentioned above, this causes it to total up the bonus frames for the last strike incorrectly, we'll put in a frame cap so the function knows when to stop. We do this in the form of another case, with a qualifier that once the frame count reaches 10, the recursion unfolds and the score is totaled.

let rec CalculateFrame rolls score frame  =
    match rolls with
        | _ when frame = 10 -> 0
        | 10::y::z::rest    -> 10+y+z + CalculateFrame (y::z::rest) (frame+1)
        | x::y::rest        -> x+y    + CalculateFrame rest         (frame+1)
        | _                 -> 0

Now the score for all strikes is 300, as it should be. All that remains is handling spares. So we test for a single spare followed by ones in each following roll.

[TestMethod]
public void CalculateScore_FirstFrameIsSpareRestOnes_29()
{
    var rolls = RollManyBallsWithSameNumberOfPins(2, 5).ToList();
    rolls.AddRange(RollManyBallsWithSameNumberOfPins(18, 1));
    var score = Scorer.CalculateScore(rolls.ToFSharpList());
    Assert.AreEqual(29, score);
}

To make the test pass, we just add another case in the match list. Simply, it matches the next three balls, if the first two of those add up to 10.

let rec CalculateFrame rolls score frame  =
    match rolls with
        | _ when frame = 10         -> 0
        | 10::y::z::rest            -> 10+y+z + CalculateFrame (y::z::rest) (frame+1)
        | x::y::z::rest when x+y=10 -> 10+z   + CalculateFrame (z::rest)    (frame+1)
        | x::y::rest                -> x+y    + CalculateFrame rest         (frame+1)
        | _                         -> 0

The test passes, so we try for all spares.

[TestMethod]
public void CalculateScore_AllFramesAreSpares_150()
{
    var rolls = RollManyBallsWithSameNumberOfPins(21, 5);
    var score = Scorer.CalculateScore(rolls.ToFSharpList());
    Assert.AreEqual(150, score);
}

This passes right away, since it really just tests that we stop at the tenth frame, which we already implemented for strikes. It's always nice to see that practice matches theory, however.

So anyway, there's another bowling kata, working in F#.

The Tests

using System.Collections.Generic;
using System.Linq;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace BowlingKataTest
{
    [TestClass]
    public class ScorerTest
    {
        private static IEnumerable<int> RollManyBallsWithSameNumberOfPins(int numberOfBalls, int pins)
        {
            for (var i = 0; i < numberOfBalls; i++)
                yield return pins;
        }

        [TestMethod]
        public void CalculateScore_AllBallsAreGutterBalls_0()
        {
            var rolls = RollManyBallsWithSameNumberOfPins(20, 0);
            var score = Scorer.CalculateScore(rolls.ToFSharpList());
            Assert.AreEqual(0, score);
        }

        [TestMethod]
        public void CalculateScore_AllBallsKnockDownOnePin_20()
        {
            var rolls = RollManyBallsWithSameNumberOfPins(20, 1);
            var score = Scorer.CalculateScore(rolls.ToFSharpList());
            Assert.AreEqual(20, score);
        }

        [TestMethod]
        public void CalculateScore_FirstFrameIsStrikeRestOnes_30()
        {
            var rolls = new List<int> {10};
            rolls.AddRange(RollManyBallsWithSameNumberOfPins(18, 1));
            var score = Scorer.CalculateScore(rolls.ToFSharpList());
            Assert.AreEqual(30, score);
        }

        [TestMethod]
        public void CalculateScore_AllFramesAreStrikes_300()
        {
            var rolls = RollManyBallsWithSameNumberOfPins(12, 10);
            var score = Scorer.CalculateScore(rolls.ToFSharpList());
            Assert.AreEqual(300, score);
        }

        [TestMethod]
        public void CalculateScore_FirstFrameIsSpareRestOnes_29()
        {
            var rolls = RollManyBallsWithSameNumberOfPins(2, 5).ToList();
            rolls.AddRange(RollManyBallsWithSameNumberOfPins(18, 1));
            var score = Scorer.CalculateScore(rolls.ToFSharpList());
            Assert.AreEqual(29, score);
        }

        [TestMethod]
        public void CalculateScore_AllFramesAreSpares_150()
        {
            var rolls = RollManyBallsWithSameNumberOfPins(21, 5);
            var score = Scorer.CalculateScore(rolls.ToFSharpList());
            Assert.AreEqual(150, score);
        }
    }
}

The Code

#light

module Scorer


let rec CalculateFrame rolls frame =
    match rolls with
        | _ when frame = 10         -> 0
        | 10::y::z::rest            -> 10+y+z + CalculateFrame (y::z::rest) (frame+1)
        | x::y::z::rest when x+y=10 -> 10+z   + CalculateFrame (z::rest)    (frame+1)
        | x::y::rest                -> x+y    + CalculateFrame rest         (frame+1)
        | _                         -> 0

let CalculateScore rolls =
    CalculateFrame rolls 0