Picking the Right Tool for the Job

When your only tool is a hammer, every problem looks like a nail.
– Abraham Maslow

I recently organized a coding dojo where we solved the bowling kata. In short, the bowling kata is about programming a score-keeper for a game of ten-pin bowling. At any given time during the game, the score-keeper must be able to yield the current score for all players. Additionally, the program must be able to tell which player is the current player, in order to assign scores correctly.

I began solving the kata in my programming language of choice, C#. The solution naturally converged to an imperative state machine, incrementing scores as the game progressed. This lead to entangled code with many special cases, struggling with the tracking of arbitrary strikes and spares.

Then I realized that the problem is in fact two-fold. One part of the problem is to keep track of which player knocks over which pins, while the other part is the actual calculation of the scores. Given a sequence of numbers representing the amount of pins knocked over, the score can be calculated as a relatively simple function. At this point, I reached for my .NET toolbox and picked the tool best suited for writing functional code, F#.

module BowlingCalculator

[<CompiledNameAttribute("CalculateScore")>]
let calcScore pins =

    let rec calcScore pins frame =

        match pins with

        // Strike with determined bonus
        | 10 :: y :: z :: rest -> 10 + y + z + calcScore (y :: z :: rest) (frame + 1)

        // Strike -without- determined bonus
        | 10 :: y :: [] -> 0

        // Spare with determined bonus
        | x :: y :: z :: rest when x + y = 10 -> 10 + z + calcScore (z :: rest) (frame + 1)

        // Spare -without- determined bonus
        | x :: y :: [] when x + y = 10 -> 0

        // Open frame
        | x :: y :: rest -> x + y + calcScore (rest) (frame + 1)

        // Special last frame
        | x :: y :: z :: [] when frame = 10 -> x + y + z

        // Otherwise
        | _ -> 0

    calcScore pins 1

If you are familiar with functional programming and pattern matching, the code above should be pretty obvious. I will not go into much depth explaining it, but suffice it to say that it is a recursive function traversing the list of pins knocked over, aggregating the score as it goes.

The rest of the program, responsible for keeping track of state, was kept in C#. After adding a reference to the F# module, calling into the calculating function is as simple as:

public class Player
{
    private readonly List<int> pinsKnockedOver;
    
    // snip...
    
    public int CalculateScore()
    {
        var pins = ListModule.OfSeq(pinsKnockedOver);
        return BowlingCalculator.CalculateScore(pins);
    }
}

Both being first class .NET citizens, interoperability between C# and F# is a breeze. The only hitch at this point was that my F# function required an F# list as its argument, while the Player class uses a regular List<T> to keep track of the pins knocked over. ListModule.OfSeq() converts any IEnumerable<T> into an F# list, solving that problem with ease.

The complete source code is available on GitHub at https://github.com/tormodfj/katas/tree/master/mixed/Bowling.

In my opinion, this solution takes the best from two worlds, using the imperative C# for state tracking and the functional F# for calculations. Learning the functional paradigm is like acquiring a new tool in your toolbox, enabling you to view problems from other points of view.

Advertisements

Converting an IList<T> to an FSharpList<T>

When calling F# functions from other .NET languages, you may encounter situations where you need to pass parameters of type 'T list. F# lists are immutable linked lists, appearing as the type FSharpList<T> in other .NET languages. Hence, passing a typical IList<T> is not possible. Luckily, converting an IList<T> to an FSharpList<T> is easily accomplished by recursively calling FSharpList<T>.Cons, passing each element of the source list. I keep the following code around for those occasions:

public static class Interop
{
	public static FSharpList<T> ToFSharpList<T>(this IList<T> input)
	{
		return CreateFSharpList(input, 0);
	}

	private static FSharpList<T> CreateFSharpList<T>(IList<T> input, int index)
	{
		if(index >= input.Count)
		{
			return FSharpList<T>.Empty;
		}
		else
		{
			return FSharpList<T>.Cons(input[index], CreateFSharpList(input, index + 1));
		}
	}
}

Note how F# lists are terminated using FSharpList<T>.Empty. Using this piece of code is as simple as:

var list = new List<int> { 1, 2, 3, 4 };
var fsharpList = list.ToFSharpList();

Update: @rickasaurus made me aware of the List.ofSeq<'T> function in the F# core library. This function solves the same issue. And, unlike my solution, its implementation is not prone to stack overflows when the input list grows large. In C#, this function is called like this:

var list = new List<int> { 1, 2, 3, 4 };
var fsharpList = ListModule.OfSeq(list);