Uncle Bob’s Bowling Kata in Functional C#

During the session on functional programming at OpenVolcano10 this week, Uncle Bob Martin spoke of a particularly elegant functional solution to his bowling game kata. Proposed by Stuart Halloway, the solution regards the bowling game itself as a (potentially infinite) sequence of ‘rolls’ (balls), and then uses some nicely elegant list manipulation to extract ten valid scoring frames from the sequence of balls and calculate the score of the game.

C# and IEnumerable<T> allow you to do some very similar things in .NET – basically, you can define operations in terms of mapping one infinite list to another infinite list, and you don’t have to worry about stack overflows or out of memory errors because, thanks to the wonder of lazy evaluation, nothing is actually allocated or returned until you start asking for the resulting values.

Take a look at this code snippet:

static IEnumerable<Int64> Integers {
    get {
        for (var i = 1; true; i++) yield return (i);
    }
}

If you’re thinking “but that’s just an infinite loop!” – you’re partly right. Yes, it’s infinite, but no, it’s not a loop. The magical yield return operator there actually breaks the loop, and allows you go to infinity (and beyond!) – one step at a time. Using the LINQ Take() method, you can easily slice’n’dice this infinite list into useful pieces:

// Calculate the sum of the first 20 positive integers:
var sum = Integers.Take(20).Sum();

// Calculate the product of the first 10 positive integers:
var product = Integers.Take(10).Aggregate((a, b) => (a * b));

By throwing some extensions methods onto Int64, you can use the same approach to filter the list:

public static class ExtensionMethods {
    public static bool IsPrime(this Int64 candidate) {
        if ((candidate & 1) == 0) return (candidate == 2);
        var num = (int)Math.Sqrt((double)candidate);
        for (var i = 3; i <= num; i += 2) {
            if ((candidate % i) == 0) return false;
        }
        return true;
    }
}

// now we’ve defined myInt64.IsPrime(), we can do this:
var primes = Integers.Where(i => i.IsPrime());

We now have a C# variable – primes – that, for all intents and purposes, contains all the prime numbers. If we try to print the entire list, our program will never terminate – but that’s what we’d expect, because the list of prime numbers is infinite. We can, however, do things like printing a list of the first 100 primes:

foreach(var prime in primes.Take(100)) Console.WriteLine(prime);

or calculating the product of the first 50 primes:

var product = primes.Take(50).Aggregate((a,b) => (a*b));

So, what’s all this got to do with bowling? Well – using this approach, we can store the progress of a bowling game as a (potentially infinite?) list of rolls, and by using a couple of useful extension methods on IEnumerable<int>, we can calculate the resulting ten-pin bowling score in a single LINQ statement:

var score = rolls.ToFrames().Take(10).Sum(frame => frame.Sum());

Here’s the supporting extension methods  - which basically capture the scoring quirks of spares, strikes, frames and the other idiosyncracies of ten-pin-bowling. The ToFrames() method is particularly interesting – it’s translated from the cons operator in Lisp/Clojure, and effectively returns a list (the rolls that count towards the current frame), followed by a list of lists (where each list represents a subsequent frame in the game):

public static class BowlingRules {
    public static IEnumerable<IEnumerable<int>> ToFrames(this IEnumerable<int> rolls) {
        yield return (rolls.Take(rolls.BallsToScore()));
        foreach(var frame in (rolls.Skip(rolls.FrameAdvance()).ToFrames())) {
            yield return(frame);
        }
    }

    private static int FrameAdvance(this IEnumerable<int> rolls) {
        return (rolls.IsStrike() ? 1 : 2);
    }

    private static int BallsToScore(this IEnumerable<int> rolls) {
        return (rolls.IsBonus() ? 3 : 2);
    }

    private static bool IsStrike(this IEnumerable<int> rolls) {
        return (rolls.Take(1).Sum().Equals(10));
    }

    private static bool IsSpare(this IEnumerable<int> rolls) {
        return (rolls.Take(2).Sum().Equals(10));
    }

    private static bool IsBonus(this IEnumerable<int> rolls) {
        return (rolls.IsSpare() || rolls.IsStrike());
    }
}

The project – including the unit test from Uncle Bob’s kata translated to NUnit / C# – is up on Google Code if you want to take a look.