Navigate / search

Learning to think functionally: Iterating, Incrementing and Accumulating

This entry is part 1 of 11 in the series Learning to think Functionally

Another F# session this evening and some more deliberate practice of Functional Thinking. To be fair, this post isn’t really about anything new. If you’ve ever used recursion, even in non-functional languages, this will be old news. If you are new to Functional Programming and/or recursion then this may be useful.

Here’s a really simple function. It accepts a number n and sums all the numbers from 1 to n.

let SumUpToValue n = [1..n] |> List.sum

I create a range up to n and then it’s a simple matter to sum the numbers in the range.

What if I wanted to start from a target value, and work back to the range of numbers?

> SumTo 10;;
val it : int list = [1; 2; 3; 4]

Let’s agree one little ground rule here. Not every target number can be reached exactly by summing a range. Our function will get us as close as possible to the target without exceeding it.

If I was back in Imperativeland I’d create a loop starting from 1 and add to an accumulator until I reach the target. But here in Functionalville that’s apparently not how things are done. So, how are things done? How can I implement this function without iterating over a series of numbers, summing them, and using a loop guard so I know when to stop?

It turns out I can’t. That’s not to say it can’t be done, but the most “functional” solution I could come up with is basically the same solution as the loop described above, albeit with a cunning disguise.

Here was my first attempt

let rec DoSumTo t nums =
    let currentSum = List.sum nums
    let nextNumber = nums.Head + 1
    match currentSum + nextNumber > t with
    | true -> nums
    | false -> DoSumTo t (nextNumber::nums)

let SumTo target =
    DoSumTo target [1]


> SumTo 21;;
val it : int list = [6; 5; 4; 3; 2; 1]

‘DoSumTo’ is a recursive function that is passed the target value (t), and the list of numbers found so far (nums). The list of numbers provides us with two useful pieces of information. Adding one to the number at the head of he list gives us the next number that we need to add. So, the list is actually doubling up as the variable we would normally use as a loop counter.

Summing the contents of the list allows us to check if we’ve reached the target value yet, so the list is also doubling as the accumulator we would use if we were writing this using imperative code with mutable variables.

The function checks whether adding the next number to the list would cause us to exceed the target. If it would, we return the list as it currently stands, and that’s our answer. If adding the next number doesn’t exceed the target, the function recursively calls itself to try the next number.

The only reason I’m using pattern matching here rather than if..else is that as part of my practice I’m trying to avoid using If statements and While statements.

When ‘DoSumTo’ calls itself recursively it passes the target (t) unchanged, but it creates a new list consisting of the next number as the head, and the existing list of numbers as the tail. In other words, each new number is added at the head of the list.

This of course means that the resulting list of numbers is in reverse order. I don’t really care about this. The numbers are correct and reversing the list is trivial.

There is one potentially big problem with this code. Every call to ‘DoSumTo’ causes the list of numbers to be summed. That’s quite wasteful, and easily fixed. Let’s take another stab at this.

let rec DoSumTo t nums currentSum =
    let nextNumber = nums.Head + 1
    match currentSum + nextNumber > t with
    | false -> DoSumTo t (nextNumber::nums) (currentSum + nextNumber)
    | true -> nums

let SumTo target =
    DoSumTo target [1] 1

We’ve eliminated the summing of the whole list for each new number, by passing the currentSum as a parameter. Each run of the function increases the currentSum for the next run creating an accumulator.

We can go further. We don’t even need to pass the full list of numbers. The function uses the head of the list to keep track of what the next number should be, but we don’t use the full list until we’ve reached the target. Manipulating a full list when we don’t need to is wasteful.

let rec DoSumTo t currentNum currentSum =
    let nextNum = currentNum + 1
    match currentSum + nextNum > t with
    | false -> DoSumTo t nextNum (currentSum + nextNum)
    | true -> [1..currentNum]

let SumTo target =
    DoSumTo target 1 1

Now, instead of passing the full list, we just pass the number we’ve reached as we count up from 1. We also pass the target and the current sum of numbers up to that point. Now instead of using the head of the list of numbers, we just use currentNum.

The only other change is that when we reach the target number, we need to create a range for numbers from 1 to currentNum. This has the added bonus that the resulting list of numbers happens to be in the right order.

> SumTo 28;;
val it : int list = [1; 2; 3; 4; 5; 6; 7]

Learning to think functionally – Unfolding Sequences

This entry is part 2 of 11 in the series Learning to think Functionally

In my last post I worked through an example that finds the range of numbers that sum to a target value, or gets as close as possible without exceeding the target. I mentioned that the solution felt a little too like the loopy code I would have written in non-functional languages. I felt that there might be a more “functional” way of solving the problem, but I didn’t know what it was.

Ross McKinlay kindly added a comment to point out how the problem could be solved using the ‘unfold’ feature of sequences. When I first looked at the example, I felt like I often do when I see unfamiliar F# code. Utterly confused.

I eventually figured it out and thought it might be worth a further post. Let’s go back to where we left the code at the end of the last post.

let rec DoSumTo t currentNum currentSum =
    let nextNum = currentNum + 1
    match currentSum + nextNum > t with
    | false -> DoSumTo t nextNum (currentSum + nextNum)
    | true -> [1..currentNum]

let SumTo target =
    DoSumTo target 1 1

> SumTo 28;;
val it : int list = [1; 2; 3; 4; 5; 6; 7]

Let me say at the start, there’s a bug in this code. If you try SumTo 0, you get a wrong answer. We’ll address that bug in this post.

Here’s the alternative “unfold” solution that Ross provided.

let sumTo target =
    Seq.unfold(function
    | (current,total) when total >= target -> None
    | (current,total) -> Some(current,(current+1,total+current))) (1,0) 

Ross’ code has some issues too. For example…

> sumTo 2 |> ToList;;
val it : int list = [1; 2]

In this case the function returns a list of numbers that sum to more than the target. No biggie, a misplaced ‘=’, an easy fix. That aside, I really like the Seq.unfold feature. So, let’s step back for a second and explain some terminology, then we’ll continue.

The following is a very quick, incomplete, and probably inaccurate description of Ranges, Lists and Sequences. It will be just enough to allow you to understand the rest of the post, but I’d urge you to read up on these things yourself for a fuller picture.

Range
A Range Expression is simply a notation for defining a series of numbers from a low value to a high value. By default the increment is 1, but the Range notation also allows us to define a step size. For the purpose of this blog post we’re interested in using Range expressions to define the contents of Lists and Sequences.

List
A List is an ordered series of elements. Lists are immutable, and finite. To put it bluntly, lists actually contain stuff. All the elements in a list will be of the same type, but that can be pretty much anything. Numbers, words, tuples, types, or even other lists.

There are numerous ways of specifying the contents of a list. You can explicitly say what it contains…

let explicitList = [ 1; 2; 3 ]

You can also use a Range expression to define the contents of a list.

let rangeList = [ 1 .. 10 ]

If you want to change the increment size you can. The following range runs from 0 to 100 in steps of 5.

let skipList = [ 0..5..100 ]

Sequences
A Sequence is similar to a list. We can enumerate the items in the sequence, apply aggregate functions, etc. Sequences can be created using Range Expressions in much the same way that Lists can.

let rangeSequence = {1..10}

Note, that the only difference from Lists is that we use braces {} instead of the square brackets [].

The killer feature of Sequence is that the terms of the sequence are generated on an “as needed” basis. So, if a sequence defines a potential range of 1,000,000 items, but a particular function only accesses the first 10 terms, then only the 10 terms are generated. This allows for potentially infinite sequences.

Unfolding Sequences
And, with that very quick primer, we go back to the code from Ross and another much more interesting way to generate a Sequence, Unfolding.

Unfolding a sequence is actually a very simple notion. We use a function to generate the next term in the sequence based on the current term. An example is worth a thousand words, so let’s have one.

let TwoAtATimeFrom n =
    n
    |> Seq.unfold(function x -> Some(x, x+2))

val TwoAtATimeFrom : int -> seq<int>

> TwoAtATimeFrom 11;;
val it : seq<int> = seq [11; 13; 15; 17; ...]

The function accepts a number and pipes it into our unfold function. This value n is used only as the starting point for the sequence. Every subsequent term is calculated based on the previous term.

The key line of code is the unfold function, highlighted above. The result of this line of code is a sequence that starts at 11 (the value of n), and increases in steps of 2. But how? Let’s tear it apart.

It’s the ‘unfold’ method from the Seq module, so this bit is obvious enough.

Seq.unfold(...)

The interesting stuff is what goes on between those parenthesis.

function x -> Some(x, x+2)

We pass a function to unfold that accepts a number and generates the next number. To do that you might think (as I did) that it would be a simple function along the lines of

function x -> x + 2

But, the function actually contains ‘Some(x, x+2)’.
Why the ‘Some’ why both x and x + 2?

As with all things, it’s simple when you understand it, and it’s difficult until then.

‘Some’ indicates that we’re generating an Option value. By this I mean an item that may have a value, or may have none. In C# we’d call these Nullable. As long as the function produces some value the unfolding will continue. If it produces a ‘None’ value, the unfolding stops. Since the example above never produces a ‘None’ value, it is an infinite sequence.

Let’s modify it so there’s an upper limit of 1000.

let TwoAtATimeFrom n =
    n |> Seq.unfold(function 
    | x when x > 1000 -> None 
    | x -> Some(x, x+2))

We start with the value n, but now our unfold function has two options when generating the next term. If the term is greater than 1000, the function returns None, which stops the Sequence unfolding any further. As long as we’re less than 1000, new terms will be created.

Before we move on, let’s look at that “Some” syntax.

    x -> Some(x, x+2))

This says that as the sequence unfolds we take the value x (the first x), we add that value to the sequence (the second x) and then we generate the next value in the sequence by adding two to x (the x + 2). To really make this clear, lets generate another sequence.

let SeqFromTuple (x, y) =
    (x, y) |> Seq.unfold(function 
    (x, y) -> Some(y, (y, x+y)))

This function accepts a tuple, which is used as the starting value of the sequence that will be unfolded. As there is no provision to encounter a ‘None’ value this sequence has no set upper limit.

Each iteration creates a new tuple using the following transformation (x, y) -> (y, x+y). The following shows how that might look.

(1, 1) (1, 2) (2, 3), (3, 5), …

While these tuples are created, this does not reflect the actual sequence that is produced by the code. If you look at the first parameter of the ‘Some’, you’ll see it’s just ‘y’. So, while the unfold function produces a new tuple with each step, only the ‘y’ part of the tuple is actually realised into the Sequence. So the sequence actually looks like this.

> SeqFromTuple (1,1);;
val it : seq<int> = seq [1; 2; 3; 5; ...]

Before I finish let me return to the concept of Option types. These are used in situations where a value may or may not exist. An option will either have “Some” value or “None”. We’ve seen above how None can be used to flag the end of a process of unfolding a sequence. That’s not really a great example of the power of Option types.

Let’s go back to the exercise that started all of this. Given a number, find the range of numbers that sums to the target value. And recognising that not all values can be summed to exactly, we get as close as possible without exceeding the target.

Now, having learned about Option types we can improve this.

Given a number, find the range of digits that sum to the target number, and where no range sums exactly to the target, the function should indicate this by returning None.

Here’s the code.

let ThatSumClosestTo x =
    (0, 0)
    |> Seq.unfold(function 
        (total, num)-> if (total + num > x) 
                       then None 
                       else Some(num,(total + num, num + 1)))

let ThatSumsTo x =
    let closest = 
        ThatSumClosestTo x
        |> Seq.toList
    if closest |> List.sum = x 
    then Some(closest)
    else None

val ThatSumClosestTo : int -> seq<int>
val ThatSumsTo : int -> int list option

> 28 |> ThatSumsTo;;
val it : int list option = Some [0; 1; 2; 3; 4; 5; 6; 7]
> 29 |> ThatSumsTo;;
val it : int list option = None

Attempting to find a range of numbers, starting at 0 that sums to 28, gives 1 to 7, but for 29 there is no range of numbers that sums exactly, and so, the function indicates this by returning None.

I won’t go into detail about how this last version of the code works. I’ve presented enough explanation in this and previous posts for you to work it out, and it’s a worthwhile exercise. If you have any questions, feel free to leave a comment. If you can see opportunities to clean up the code, or simplify it, please leave a comment with suggestions.

Learning to think functionally – Currying

This entry is part 3 of 11 in the series Learning to think Functionally

Warning, novice functional thinker here. If you know your stuff, what follows may cause distress.

I was messing with F# last night and I got a gentle reminder that I’m still a long way from thinking functionally, it still takes a lot of effort.

I started with this

let evens r = List.filter (fun x -> x % 2 = 0) r

> evens [0..10];;
val it : int list = [0; 2; 4; 6; 8; 10]

Simple enough. Even numbers are multiples of 2. Rekindling childhood memories of typing code from books by Tim Hartnell into a ZX81, I did what I would have done then. I tried to make the code do something slightly more complicated. What about a function that can find multiples of any number, not just 2.

So, how would I write this next function?

> multiplesOf 3 [0..10];;

I played with the ‘even’ function for a while. Clearly I needed to replace the 2 with a variable, but no matter what I tried I couldn’t find a way of getting a variable into the filter predicate.

I was missing the point. The filter predicate takes one argument, a member of the list being filtered. There is, to the best of my knowledge, no way of adding extra parameters. You need to take a different (more functional) approach.

Currying
What we need to do is create a function that accepts an item from the list and checks if it’s a multiple of a variable, without passing that variable into the function. In other words, we need to lock the variable in when the function is created. What we’re talking about here is Currying, which is something I thought I understood, but as with any new concept, reading about it is one thing, having it pop into your mind automatically when you need it is another matter entirely.

When the currying idea had made it’s way into my mind coming up with something that works was relatively easy (that’s progress I suppose).

let multipleOf x y = y % x = 0;

let multiplesOf m r =
    let multipleOfm = multipleOf m;
    List.filter (fun x -> multipleOfm x) r;

The multipleOf function takes care of figuring out if any number is a multiple of another. It takes two parameters for obvious reasons. But through the magic of Currying we can use this function to create a curried version ‘multiplesOfm’ (highlighted). ‘multiplesOfm’ locks in whatever value was in the variable m, so that it need only be passed one number, which it checks against m to see if it’s a multiple.

In other words, our curried function ‘multiplesOfm’ will work as the predicate filter, allowing us to create the ‘multiplesOf’ function that all this started with.

That all felt like a tiny breakthrough in ‘functional thinking’ the understanding that in imperative programming we focus on writing functions, in functional programming we will often create the function that we need at runtime, and currying is one tool at our disposal for doing that.

To really lock this idea in, let’s play with it a little more. Let’s rewrite our ‘evens’ function, using the ‘multipleOf’ function.

let multipleOf x y = y % x = 0;

let even x = multipleOf 2 x;

> even 4;;
val it : bool = true

One final thing. In the original problem I created a ‘multipleOf’ function, outside the scope of the function I actually wanted to create. The ‘multipleOf’ function could be useful in other scenarios, so this wasn’t completely unreasonable, but what if we want to keep the whole thing self contained. Well, that’s easy. We just move the function in question into the scope of the larger function.

let multiplesOf m r =
    let multipleOf x y = y % x = 0;
    let multipleOfm = multipleOf m;
    List.filter (fun x -> multipleOfm x) r;

It’s worth looking at why currying works. Something I don’t have time to do right now, maybe another time, but if you are trying to learn how to “Think Functionally” you could do worse than get a solid grasp of currying.

C# to F# Interop – Sharing a Domain Model

This entry is part 4 of 11 in the series Learning to think Functionally
Download
One of the first things I wanted to do with F# was call it from C#. I wanted to be able to take collections of domain objects written in C# and use F# goodness to process them.

It’s actually reasonably easy to do as you’d imagine for two .Net languages. There are one or two speedbumps, we’ll cover those here.

The Assemblies
The attached sample solution includes three projects, a Console Application written in C#, a Domain Model DLL containing two very simple classes, also written in C#, and a Library written in F#. Both the Console App and the F# Library reference the Domain Model, so both are aware of the Domain Objects, and these can be passed between the App and the Library. The Console app also references the F# library, so that it can use its functions.

I don’t know if it’s a problem with Visual Studio (2010) or a problem with me, but to reference the F# library from the C# app, I needed to browse to the DLL. A simple project reference seemed to cause errors.

The Domain Model
The domain model is simply a Product, and a Transaction. A Transaction represents the sale of a Product.

namespace DomainModel
{
    public class Product
    {
        public long Id { get; set; }
        public string Name { get; set; }
        public long Price { get; set; }
    }

    public class Transaction
    {
        public long Id { get; set; }
        public Product Product { get; set; }
        public long quantity { get; set; }
    }
}

The Application is a Console App that creates a list of Transactions and passes it to functions in the F# library, and displays the results.

    class Program
    {
        static void Main(string[] args)
        {
            var transactions = GetTransactions();

            Console.WriteLine("PRODUCTS SOLD");
            var productsSold = Transactions.Stats.ProductsSold(transactions);
            foreach (var product in productsSold)
                Console.WriteLine(string.Format(product.Name));
            Console.WriteLine();

            Console.WriteLine("TOTAL REVENUE PER PRODUCT");
            var totalRevenuePerProduct = Transactions.Stats.TotalRevenuePerProduct(transactions);
            foreach (var productRevenueSummary in totalRevenuePerProduct)
                Console.WriteLine(string.Format("{0} : {1}", productRevenueSummary.Item1.Name, productRevenueSummary.Item2));
            Console.WriteLine();

            Console.WriteLine("TOTAL REVENUE");
            var totalCost = Transactions.Stats.TotalRevenue(transactions);
            Console.WriteLine(totalCost);
            Console.WriteLine();
        }

        private static IEnumerable<Transaction> GetTransactions()
        {
            var banana = new Product {Id = 1, Name = "Banana", Price = 2};
            var apple = new Product {Id = 2, Name = "Apple", Price = 1};
            var pear = new Product {Id = 3, Name = "Pear", Price = 3};

            var transaction1 = new Transaction {Id = 1, Product = banana, quantity = 5};
            var transaction2 = new Transaction {Id = 2, Product = apple, quantity = 10};
            var transaction3 = new Transaction {Id = 3, Product = pear, quantity = 6};
            var transaction4 = new Transaction {Id = 4, Product = apple, quantity = 5};
            var transaction5 = new Transaction {Id = 5, Product = pear, quantity = 7};
            var transaction6 = new Transaction {Id = 6, Product = pear, quantity = 8};
            var transaction7 = new Transaction {Id = 7, Product = apple, quantity = 4};

            return new List<Transaction>
                                   {
                                       transaction1,
                                       transaction2,
                                       transaction3,
                                       transaction4,
                                       transaction5,
                                       transaction6,
                                       transaction7
                                   };
        }
    }

Running the app, shows a distinct list of the products sold, the total sales revenue for each product, and an overall total revenue figures.

PRODUCTS SOLD
Banana
Apple
Pear

TOTAL REVENUE PER PRODUCT
Banana : 10
Apple : 19
Pear : 63

TOTAL REVENUE
92

There’s nothing Earth shattering here. You don’t need to use F# to get any of these figures. The point of this exercise is simply to demonstrate HOW to use F# to process your C# Domain Objects. You can figure out yourself WHEN it’s appropriate.

The F# Library

The F# library defines a namespace ‘Transactions’, and within that a module ‘Stats’. We open the DomainModel to get access to the Transaction and Product classes.

namespace Transactions

module Stats =

    open DomainModel

    let Revenue (t : Transaction) = 
        t.quantity * t.Product.Price

    let TotalRevenue (s : seq<Transaction>) = 
        s |> Seq.sumBy Revenue

    let TotalRevenuePerProduct (s : seq<Transaction>) =
        s |> Seq.groupBy(fun t -> t.Product)
          |> Seq.map (fun (key, values) -> (key, values |> TotalRevenue))

    let ProductsSold (s : seq<Transaction>) =
        s |> Seq.groupBy(fun t -> t.Product)
          |> Seq.map (fun (key, values) -> key)

I’ll take each of the functions in turn.

    let Revenue (t : Transaction) = 
        t.quantity * t.Product.Price

This simple little function calculates the revenue for an individual Transaction. Because we’re accessing properties, it’s important to specify the type. This function doesn’t get called directly from out C# code (although there’s no reason why it couldn’t be), it’s used by the TotalRevenue function.

    let TotalRevenue (s : seq<Transaction>) = 
        s |> Seq.sumBy Revenue

TotalRevenue is called from our C# app. Again, we use a type annotation to indicate that we’ll be receiving a Sequence of Transactions. Sequences are compatible with IEnumerable, so as long as our C# app is sending an IEnumerable this function will be able to work with the items. In the C# app we have a List which is of course compatible with IEnumerable.

The TotalRevenue function itself is very simple, it leverages the Revenue function described above to calculate the revenue for each Transaction. So, the TotalRevenue function really does exactly what it says on the tin. It sums the revenue for the Transactions. This highlights something that you should keep in mind when coding in F# (or indeed any language), it rarely hurts to break out a small specific piece of functionality and put it in it’s own function. It’s particularly true in Functional languages.

Breaking down the Revenue by product is a little trickier, but still pretty straightforward.

    let TotalRevenuePerProduct (s : seq<Transaction>) =
        s |> Seq.groupBy(fun t -> t.Product)
          |> Seq.map (fun (key, values) -> (key, values |> TotalRevenue))

Again we use a type annotation to indicate that the function receives a Sequence of Transactions. Our goal here is to return a sequence of tuples where the first value in the tuple is the Product, not just the name of the product, but the whole thing. The second item in the tuple will be a number indicating the total revenue for that product.

To produce the desired results we first group by the Product, we then take the Transactions grouped under each product and get the Total Revenue for that particular subset of Transactions.

The groupBy function takes a function that returns the key that we want to group by. The code here uses ‘fun t -> t.Product’ which means that for a Transaction t we take the product. The result of Seq.groupBy is a Sequence of tuples in which the first item is the key (the Product) and the second item is a Sequence containing the Transactions for that product.

Because the second item in the tuple is a Sequence of Transactions, it’s valid input for our TotalRevenue Function. It’s worth deconstructing the line of code that actually creates the sequence that we’re ultimately interested in.

Seq.map (fun (key, values) -> (key, values |> TotalRevenue))

It’s Seq.map which means it takes a sequence at applies the specific function to each item. In this case each item is a Tuple, so we assign the name ‘key’ to the first item in the tuple, and the name ‘values’ to the second item, which is itself a Sequence of Transactions. The function creates a tuple as it’s output, the first item of the output Tuple is ‘key’, which means it will be the Product.

The second item of the tuple shows ‘values’ being piped to TotalRevenue, which will return a number indicating the Total Revenue.

If you can get your head around the groupBy example above then you will have no problem with the final example.

    let ProductsSold (s : seq<Transaction>) =
        s |> Seq.groupBy(fun t -> t.Product)
          |> Seq.map (fun (key, values) -> key)

Again we use Type annotations, again we group by Product. This time we just want a distinct list of the Products that were sold. Out Seq.map function works like it did in the last example, except that instead of mapping to a tuple, we map to one value, which is the groupBy key, i.e. Product.

Bowling Game Kata in F#

This entry is part 5 of 11 in the series Learning to think Functionally

I’m on an ongoing quest to get competent with F#. I’m also on an ongoing quest to get competent with TDD. Interestingly until now those two quests hadn’t crossed paths. I had written no unit tests in F#. Why you might ask?

When I started writing Unit Tests I found the biggest win wasn’t the design that tests drive, nor was it catching regression bugs. The biggest win was the huge saving on time spent in the debugger.

When I started playing with F# using the REPL, I found that I wasn’t spending any time in the debugger. I mean literally none. After a few weeks of playing with It I actually consciously tried using the debugger to see what it was like. To date I still have had no problem in F# that required me to debug the code.

I recognise that that’s possibly a result of working on “relatively” simple code. I’d hope code would always be simple, but, there will probably come a time when I’ll need to either debug code, or use tests to avoid debugging. So, it’s time to bring F# and TDD together.

The Bowling Game kata seemed like a good start. The attraction of this Kata is that it seems perfectly set up for a functional solution. You have an input (a list of scores from frames) and a desired output (the score for that game) and your job is to write a transformation from one to the other. A list of tuples seems like a really nice way to represent the rolls in a game of bowling, and, I initially thought I may be able to write some sort of ‘fold’ or ‘reduce’ function that would reduce the list of tuples to the correct score. As you’ll see, it didn’t quite work out like I had hoped.

Let’s start with a test for the simplest type of games, one with no Spares or Strikes.

    [<TestCase(Result=30)>]
    member x.RegularGame() =
        let rolls = 
            [(1,2); (1,2); (1,2); (1,2); (1,2); (1,2); (1,2); (1,2); (1,2); (1,2)]
        ScoreGame rolls

My first thought for this was to just use a fold function.

let ScoreGame (frames: List<int * int>) =
    List.fold (fun score frame -> score + fst frame + snd frame) 0 frames 

This does get the test passing, but having played with this I found it virtually impossible to add support for strikes and spares. I’m going to back up and show you the route I eventually settled on, but please feel free to let me know if you manage to make something of the ‘fold’ approach.

let rec ScoreGame (frames: List<int * int>) =
    match frames with
    | [] -> 0
    | frame::rest -> fst frame + snd frame + ScoreGame rest 

This is essentially the same as the fold, but the pattern matching allows us a way of handling special cases. Let’s take a look at one of those now, Spares.

    [<TestCase(Result=38)>]
    member x.ContainsSpares() =
        let rolls = [(1,2); (1,2); (1,2); (5,5); (1,2); (1,2); (1,2); (1,2); (1,2); (1,2)]
        ScoreGame rolls

A frame is a Spare when the two rolls add up to 10. If the first frame on it’s own is 10 then that’s a Strike. We’ll ignore Strikes for now. The following code gets us to green.

let rec ScoreGame (frames: List<int * int>) =
    match frames with
    | [] -> 0
    | frame::rest when fst frame + snd frame = 10
        -> 10 + fst rest.Head + ScoreGame rest
    | frame::rest 
        -> fst frame + snd frame + ScoreGame rest 

When a Spare occurs, the first subsequent roll is added as a bonus.

We can refactor a little bit to make things clearer.

let ScoreFrame (roll:int * int) =
    fst roll + snd roll

let IsASpare (frame:int * int) =
    ScoreFrame frame = 10

let rec ScoreGame (frames: List<int * int>) =
    match frames with
    | [] -> 0
    | frame::rest when frame |> IsASpare
        -> 10 + fst rest.Head + ScoreGame rest
    | frame::rest 
        -> ScoreFrame frame + ScoreGame rest

This is all fairly straightforward so far. There is one little edge case for Spares and that is how they are handled when they occur in the 10th frame. As mentioned above, when you score a Spare the first roll of the subsequent frame should be added as a bonus. The 10th frame is the final frame, so to allow for bonuses on strikes or spares bowled in the 10th frame, up to two additional balls can be rolled. I handle this by adding an 11th tuple when either a strike or spare is scored in the 10th frame, and scoring accordingly.

    [<TestCase(Result=38)>]
    member x.EndsOnASpare() =
        let rolls = 
            [(1,2); (1,2); (1,2); (1,2); (1,2); (1,2); (1,2); (1,2); (1,2); (5,5); (1, 0)]\\
        ScoreGame rolls

When a strike or spare occurs in an earlier frame the subsequent rolls are counted as a bonus, but they are also scored in their own right. This is different for the “11th frame”. This exists purely for the purposes of determining the bonus in the 10th frame, the rolls are not added to the score in their own right.

We need to keep track of what frame we’re on, so we handle the bonus for Strikes and Spares in the 10th frame correctly. One way to do this would be to turn the tuples into triples by adding a frame number to each one. I don’t like adding that burden to the input data, particularly when it’s relatively easy to have the code keep track itself.

let rec ScoreFromFrame thisFrame (frames: List<int * int>) =
    match frames with
    | [] -> 0
    | frame::rest when frame |> IsASpare && thisFrame < 10
        -> 10 + fst rest.Head + ScoreFromFrame (thisFrame+1) rest
    | frame::rest 
        -> ScoreFrame frame + ScoreFromFrame (thisFrame+1) rest

I’ve added a parameter ‘thisFrame’ that indicates which frame is being scored. For frames prior to the 10th frame we add the first roll of the next frame as a bonus, then score from the next frame onwards as normal. For frame 10 we just add the score for frame 11 (if it exists).

I’ve also renamed the function from ‘ScoreGame’ to ‘ScoreFromFrame’. These changes would break all of our tests. We could go back and change each test, but actually I quite like the way the tests are written. When we want the score of a game, we should be able to call ScoreGame and simply pass it a list of frames.

The following would obviously work as a way of preserving the interface that the tests rely on

let ScoreGame (frames: List<int * int>) = 
    ScoreFromFrame 1 frames

But, with a bit of currying there’s an even nicer solution

let ScoreGame = ScoreFromFrame 1

Time for another test, what happens if we score a Strike?

    [<TestCase(Result=40)>]
    member x.ContainsAStrike() =
        let rolls = 
            [(1,2); (1,2); (10,0); (1,2); (1,2); (1,2); (1,2); (1,2); (1,2); (1,2)]
        ScoreGame rolls

A strike is a frame where all 10 pins are knocked by the first ball. The bonus for a strike is the next two rolls.

let rec ScoreFromFrame thisFrame (frames: List<int * int>) =
    match frames with
    | [] -> 0
    | frame::rest when fst frame = 10
        -> 10 + fst rest.Head + snd rest.Head + ScoreFromFrame (thisFrame+1) rest
    | frame::rest when frame |> IsASpare && thisFrame < 10
        -> 10 + fst rest.Head + ScoreFromFrame (thisFrame+1) rest
    | frame::rest 
        -> ScoreFrame frame + ScoreFromFrame (thisFrame+1) rest

This doesn’t correctly calculate the bonus when we score two or more strikes in a row, as we can see from the next failing test.

    [<TestCase(Result=58)>]
    member x.TwoStrikesInARow() =
        let rolls = 
            [(1,2); (1,2); (10,0); (10,0); (1,2); (1,2); (1,2); (1,2); (1,2); (1,2)]
        ScoreGame rolls

The problem here is that after the first Strike we don’t calculate the bonus from the next two ‘Rolls’ which would be 10 and 1, we calculate from the two items in the next frame (10, 0), which isn’t correct. Let’s clarify exactly what we mean by “Next Two Rolls”

let IsAStrike (frame:int * int) =
    fst frame = 10

let NextTwoRollsFrom (frames: List<int * int>) =
    match frames with
    |this::next::rest when this |> IsAStrike && snd this = 0 ->
        10 + fst next
    |this::_ -> ScoreFrame this

let rec ScoreFromFrame thisFrame (frames: List<int * int>) =
    match frames with
    | [] -> 0
    | frame::rest when frame |> IsAStrike
        -> 10 + NextTwoRollsFrom rest + ScoreFromFrame (thisFrame+1) rest
    | frame::rest when frame |> IsASpare && thisFrame < 10
        -> 10 + fst rest.Head + ScoreFromFrame (thisFrame+1) rest
    | frame::rest 
        -> ScoreFrame frame + ScoreFromFrame (thisFrame+1) rest

We can wrap this all up with a test for a perfect game, which should pass with no further changes. For the record, here’s the full code, plus tests, including one or two minor readability tweaks.

module Bowling

let ScoreFrame (roll:int * int) =
    fst roll + snd roll

let IsAStrike (roll:int * int) =
    fst roll = 10

let IsASpare (frame:int * int) =
    ScoreFrame frame = 10

let NextTwoRollsFrom (frames: List<int * int>) =
    match frames with
    [] -> 0
    |this::next::rest when this |> IsAStrike && snd this = 0 ->
        10 + fst next
    |this::_ -> ScoreFrame this

let NextOneRollFrom (frames: List<int * int>) =
    fst frames.Head

let rec ScoreFromFrame thisFrame (frames: List<int * int>) =
    match frames with
    | [] -> 0
    | frame::rest when frame |> IsAStrike && thisFrame < 10
        -> 10 + NextTwoRollsFrom rest + ScoreFromFrame (thisFrame+1) rest
    | frame::rest when frame |> IsASpare && thisFrame < 10
        -> 10 + NextOneRollFrom rest + ScoreFromFrame (thisFrame+1) rest
    | frame::rest 
        -> ScoreFrame frame + ScoreFromFrame (thisFrame+1) rest

let ScoreGame = ScoreFromFrame 1


module BowlingTests

open NUnit.Framework
open Bowling

[<TestFixture>]
type BowlingTests() =

    [<TestCase(Result=30)>]
    member x.RegularGame() =
        let rolls = 
            [(1,2); (1,2); (1,2); (1,2); (1,2); (1,2); (1,2); (1,2); (1,2); (1,2)]
        ScoreGame rolls

    [<TestCase(Result=38)>]
    member x.ContainsASpare() =
        let rolls = [(1,2); (1,2); (1,2); (5,5); (1,2); (1,2); (1,2); (1,2); (1,2); (1,2)]
        ScoreGame rolls

    [<TestCase(Result=38)>]
    member x.EndsOnASpare() =
        let rolls = [(1,2); (1,2); (1,2); (1,2); (1,2); (1,2); (1,2); (1,2); (1,2); (5,5); (1, 0)]
        ScoreGame rolls

    [<TestCase(Result=40)>]
    member x.ContainsAStrike() =
        let rolls = 
            [(1,2); (1,2); (10,0); (1,2); (1,2); (1,2); (1,2); (1,2); (1,2); (1,2)]
        ScoreGame rolls

    [<TestCase(Result=58)>]
    member x.TwoStrikesInARow() =
        let rolls = 
            [(1,2); (1,2); (10,0); (10,0); (1,2); (1,2); (1,2); (1,2); (1,2); (1,2)]
        ScoreGame rolls

    [<TestCase(Result=40)>]
    member x.EndsOnAStrike() =
        let rolls = 
            [(1,2); (1,2); (1,2); (1,2); (1,2); (1,2); (1,2); (1,2); (1,2); (10,0); (1,2)]
        ScoreGame rolls

    [<TestCase(Result=300)>]
    member x.PerfectGame() =
        let rolls = 
            [(10,0); (10,0); (10,0); (10,0); (10,0); (10,0); (10,0); (10,0); (10,0); (10,0); (10,10)]
        ScoreGame rolls

It’s hardly worth mentioning but there’s one little thing that annoys me and that is the definition of a Spare. At the moment any frame with a score of 10 would elicit ‘true’ from the IsASpare function, this means that a Strike would get a true from that function.

Since we check for Strikes before Spares in the Pattern match, this issue doesn’t raise it’s head, but I’d like to make the definition of a Spare more water tight. This would have the added bonus of reducing the dependence of the pattern match on the order of the clauses.

We can modify the IsASpare function quite easily to express it accurately. This isn’t a hugely significant issue in a Kata, but in a business application where you are trying to express concepts in your domain, that little bit of ambuguity (and that isn’t a typo) could have serious implications.

let IsASpare (frame:int * int) =
    not(IsAStrike frame) && ScoreFrame frame = 10

C# is too damn noisy

This entry is part 6 of 11 in the series Learning to think Functionally

I am growing increasingly frustrated with C#. I think the reason for that may be my exposure to languages like F#. In many ways my feelings for C# are quite similar to feelings I had about VB.Net when I was first exposed to C#.

It’s taken me a while to figure out what it is that I find irritating about C# and I think I’m ready to call it. The problem with C# is exactly the same problem I had with VB.Net, it’s too damn noisy.

Take a look at this code from Martin Rosén-Lidholm

This is clearly a good programmer who cares a lot about writing good code. He went through not one but two approaches that he discarded before settling on a somewhat functional approach. His journey mirrors almost exactly my experience of playing with Conway’s Game of Life.

His ultimate solution in C# is almost identical to my F# approach which was itself based on Vagif Abilov’s approach as presented at NDC Oslo in 2012. The similarity in approach makes it an excellent case study on the relative noise levels in C# and F#.

Noise is code that is not related to the problem being solved, but is instead related to the language, tools, frameworks etc being used.

Let me define what I mean by noise. Noise is code that is not related to the problem being solved, but is instead related to the language, tools, frameworks etc being used.

The first thing I note in Martin’s solution is that Coordinate implements IEquatable, which means two functions called Equals and one called GetHashCode.

By any definition, implementing IEquatable and getting hash codes is not about Conway’s Game Of Life, so, this is noise.

Now, ok, maybe you can build Game Of Life without implementing IEquatable, but I’m sure Martin does it simply because it’s the “right” thing to do. He’s using LINQ and IEnumerable and for historic reasons this is something you do in C# for performance reasons or whatever. But, to me, it’s noise.

In the F# version there is none of that.

Let’s look at all that text in blue in Martin’s example.

‘public class’
‘public void’
‘new’
‘private readonly’
‘params’
‘return’
‘private static’
‘private readonly int’
‘public override bool’
‘unchecked’

And all those
{
curly brackets
}

oh the humanity.

I haven’t even mentioned all of the explicit specifying of types for fields, for arguments and for return types.

All this is just the pieces of code that have nothing to do with the problem domain. Let’s look at the code that actually does something.

Here’s Martin’s code for creating the next generation

public Grid CreateNextGeneration() {
    var keepAliveCoordinates = _aliveCoordinates
        .Where(c => GetNumberOfAliveNeighboursOf(c) == 2 || GetNumberOfAliveNeighboursOf(c) == 3);
 
    var reviveCoordinates = _aliveCoordinates
        .SelectMany(GetDeadNeighboursOf)
        .Where(c => GetNumberOfAliveNeighboursOf(c) == 3);
 
        return new Grid(keepAliveCoordinates.Union(reviveCoordinates).ToArray());
}

Here’s the same function from the F# solution.

 let nextGenerationOf existingCells =
        cellsThatSurviveFrom existingCells
        @
        cellsThatAreAddedTo existingCells

OK, perhaps that’s not the fairest comparison, Martin mentions in a comment that he could push some of that LINQ out into helper functions, but even still, there’s a point here I think.

Is the F# code perfect? No, I dislike the following …

let neighboursOfLiveCells pattern = 
    List.map (fun x -> neighboursOf x) pattern 
    |> flattenList 
    |> Set.ofList |> Set.toList

This was the first F# program I wrote, and maybe if I take another swing at it I can tidy that up a bit, but still, this was the first F# program I wrote, and that function is all that annoys me. That’s ‘noise’ in the F# context.

So far, I’m finding that the noise generally in F# code is much lower than in C# code. I don’t know if that will hold true as I scale up the problems I’m working on, but I see no reason why it wouldn’t. There is a lot of ceremony in C# that really only distracts from the work that the code is supposed to be doing.

None of this is a reflection on Martin, he clearly knows his stuff and cares a great deal about the code he writes. I am using his blog as an example for no other reason than it’s a great example of C# code solving a problem in the same way as some F# code that I happen to have to hand.

Learning To Think Functionally – Stuck

This entry is part 7 of 11 in the series Learning to think Functionally

When you learn a new language there’s a phenomenon that happens fairly frequently which is you get it into your head that something “should” work. So you just try it.

There are two possible outcomes.

It may work, in which case you fall a little more in love with the language.

or

It doesn’t work, and you feel a little like you asked somebody to dance and they kind of made a face and carried on talking to their friends.

F# just snubbed me. Everything was going well, I had written the following:

let IsDivisibleBy divisor value =
    value % divisor = 0

let IsFizz = IsDivisibleBy 3
let IsBuzz = IsDivisibleBy 5
let IsFizzBuzz n = IsFizz n && IsBuzz n

let ToFizzBuzzValue x =
    match x with
    | n when IsFizzBuzz n -> "FizzBuzz"
    | n when IsFizz n -> "Fizz"
    | n when IsBuzz n -> "Buzz"
    | n -> n.ToString()

let FizzBuzz first last =
    [first..last]
    |> List.map (ToFizzBuzzValue)

Standard FizzBuzzy goodness. I was particularly pleased with using curried functions for IsFizz and IsBuzz. I still think the pattern matching code is a little clunky, but that’s not todays problem.

I wanted to add a new requirement. Expand the definition of Fizz to also include numbers that contain the digit 3 (e.g. 13), and Buzz to include numbers that contain the digit 5 (e.g. 51), and FizzBuzz to include numbers that contains both (e.g. 35, 53).

Start easy, let’s just work on numbers that contain 3.
This will figure out if a number contains a given digit.

let ContainsDigit digit value =
    value.ToString().Contains(digit.ToString())

Now what? How do I include the extra constraint into my IsFizz function, which is remember a curried version of IsDivisiblyBy.

let IsFizz = IsDivisibleBy 3

This was my first thought

let IsFizz = IsDivisibleBy 3 || ContainsDigit 3

Note, I originally used && instead of ||, that’s the danger of trying to finish a blog post before a train arrives at a station.
If that had worked I wouldn’t be writing this post. I realise that the following will work, but it just seems a little less elegant than the version that didn’t work.

let IsFizz n = IsDivisibleBy 3 n || ContainsDigit 3 n

I’m going to throw this out there, while I keep playing with it. I suspect that what I tried to do here was very silly indeed and suggests I’m still missing something fundamental about currying and functions in general in F#. It feels like it’s worth thinking about this and getting it straight.

So, if you feel you can answer my question, send me a comment explaining why curried functions can not be combined in this way, and what you would do instead in this situation.

In the meantime I’m going to try and figure it out myself.

Learning to think Functionally: Memoization

This entry is part 8 of 11 in the series Learning to think Functionally

Imagine you have a long running function that you’d like to avoid running unnecessarily. For the purposes of this post you’ll have to suspend disbelief and pretend that negating a number is an expensive task. This example prints out a message so you can see when it actually gets called.

let Negate n =
    printfn "Negating '%A' this is hard work" n
    -n

val Negate : int -> int

> Negate 5;;
Negating '5' this is hard work
val it : int = -5

Now, let’s use that function when writing another. This function takes two numbers, negates the first, then adds the second.

let addNegatedValue x y =
    let n = Negate x
    n + y

val addNegatedValue : int -> int -> int

> addNegatedValue 2 3;;
Negating '2' this is hard work
val it : int = 1

If you call this function repeatedly the telltale message lets you know that the expensive negation function is called every time. We’d like to avoid that.

Perhaps currying can help. Let’s create a curried version of ‘addNegatedValue’ and see what happens.

let negateTwoThenAdd = addNegatedValue 2

val negateTwoThenAdd : (int -> int)

> negateTwoThenAdd 3;;
Negating '2' this is hard work
val it : int = 1
> negateTwoThenAdd 3;;
Negating '2' this is hard work
val it : int = 1

This gives us a new function with the first argument (2 in this case) locked in, so we can call it passing only the 3 (or whatever other number we want to add to -2).

Unfortunately, as you can see above, when you use the curried function ‘negateTwoThenAdd’ a second time, it runs the negation code again. This makes sense. Currying locks in the argument 2 not the result of negating it. It doesn’t and shouldn’t get involved in optimizing out any lines of code in the function.

We need to explicitely ‘cache’ the negated value to avoid recalculating it.

let cachedAddNegatedValue x =
    let n = Negate x
    fun y -> n + y

val cachedAddNegatedValue : int -> (int -> int)

let cachedNegateTwoThenAdd = cachedAddNegatedValue 2

Negating '2' this is hard work

val cachedNegateTwoThenAdd : (int -> int)

This time the Negation function fires when we create the curried version of the function. Of course it does, look at the code, it’s right there. Negate x then return a function.

We now have a handle ‘cachedNegateTwoThenAdd’ to that returned function. All that function does is accept another value and add ‘n’ (the result of negating ‘x’) to it.

> cachedNegateTwoThenAdd 3;;
val it : int = 1

Bingo. We can call this all day and it will add any number we want to -2 without needing to rerun the ‘expensive’ negation operation.

I don’t want to gloss over the significance of this function being able to access ‘n’. It’s not passed as an argument, it’s just there, in scope, available. This is what’s known as a closure and it’s kind of a big deal as we’ll see shortly.

Before we take this code any further, let’s divert slightly to talk about closures and mutability. We’ve seen that ‘cachedNegateTwoThenAdd’ can access the variable ‘n’, however it can’t modify that variable. Even if you flag the variable as mutable. This code isn’t valid.

let addAndRememberTotal =
    let mutable n = 0
    fun x -> 
        n <- x + n
        n

In fact if a variable is flagged as mutable you can’t use it at all in a closure, even if you only read it.

let addAndRememberTotal =
    let mutable n = 0
    fun x -> x + n

Sorry for that little diversion, but mutability and closures are important for the rest of this post.

Where were we?

We have a solution that allows us to lock in a specific result of the expensive operation, we can then use that as many times as we want without needing to run the negate function again. That’s fine in so far as it goes, but it would be nice if we could cache the result for more than one input.

We should be able to throw all sorts of values at a function and have it cache return values so that subsequent calls for the same input don’t require another call to negate.

To do this, we can’t simply use a single cached value like an int. We need something that maps inputs to computed outputs. The snag is this cache needs to be mutable because every time we get a new input we want to compute an answer for it and store it in the cache. But, we just showed that closures can’t access mutable variables.

Except…they can…sort of. We can rope in some old mavericks, guys who don’t play by the rules, guys who eat mutability for breakfast.

Take a look at this little function for a clue to where this is heading.

let rememberTheEvens =
    let theList = List<int>()
    fun n ->
        if n%2 = 0 then theList.Add(n)
        theList 

It’s a closure, but it’s calling the ‘Add’ method on a List. The List in this case is a .Net System.Collections.Generic List. We’re changing the state of the List by adding items to it, but from the perspective of F# it’s still the same list, the mutability is hidden behind a reference to the list, and that’s good enough for F# to get off our backs about it.

Once you realise you can do this it’s a short hop to the following code.

let memoizedNegation =
    let cache = Dictionary<int,int>()
    fun x ->
        if cache.ContainsKey(x) then
            cache.[x]
        else
            let res = Negate x
            cache.[x] <- res
            res

This might look a little complicated but odds are you’ve written code just like this at some point. At it’s heart this is just a function that uses a dictionary to cache the return values keyed by the input values. For a given value the “expensive” function should only need to be called once. Subsequent calls for the same value can use the cached value.

The quirk here is that this is a closure, this function creates the cache then returns a different function that uses that cache. If you’ve followed everything I’ve written above this should be easy enough to grasp.

All this boilerplate code just to add caching to the ‘Negate’ function hardly seems worthwhile. There has to be a better way.

Of course there is. This is where the notion of functions as first class citizens really comes into it’s own. The following code is where this whole post has been heading all along, and it’s lifted directly from this post by Don Syme

Take a look at this code. Play a little spot the difference between this and the ‘memoizedNegation’ function above.

let memoize f =
    let cache = Dictionary<_, _>()
    fun x ->
        if cache.ContainsKey(x) then 
			cache.[x]
        else 
			let res = f x
            cache.[x] <- res
            res

This function takes an argument f, the previous function specifically executed the ‘Negate’ function, this one executes ‘f’ whatever ‘f’ is. So, we can use this to add caching to any function. The other big difference is that we don’t limit the dictionary to ints, both the key and value are generics.

Other than those two differences, it’s basically the same function.

Here are two simple examples of the memoize function in action. Again, these are trivial examples that aren’t worth the effort, they just illustrate how to use the general ‘memoize’ function.

let increment n =
        printfn "Adding 1 to '%A'" n
        n + 1

let mIncrement =
    memoize (fun n -> increment n)

let add x y =
        printfn "Adding '%A' to '%A'" x y
        x + y

let mAdd =
    memoize (fun x y -> add x y)

There’s one interesting problem with memoization and that is it’s behaviour on recursive functions. Take a look at the following naive recursive implementation of the factorial function. If we memoize it and try to get the factorial of 5 we see that the factorials of 4, 3, 2, 1 and 0 must be calculated. Trying to get the factorial of 5 again gives the result immediately because it’s cached. However the factorials of the lower numbers are not cached. If you try to get the factorial of 4 it must be calculated.

let rec fact x =        
    printfn "Getting factorial of '%A'" x
    if x < 1 then 1
    else x * fact (x - 1)

let mfact = memoize (fun n -> fact n)

> mfact 5;;
Getting factorial of '5'
Getting factorial of '4'
Getting factorial of '3'
Getting factorial of '2'
Getting factorial of '1'
Getting factorial of '0'
val it : int = 120
> mfact 5;;
val it : int = 120

I’ll leave this here as a little exercise. Figuring out why the lower values are not cached is fairly trivial, figuring out what to do about it is a bit more of a challenge. Perhaps that’s a topic for the next post.

Learning to think Functionally -> Why I still don’t understand Single Case Active Patterns

This entry is part 9 of 11 in the series Learning to think Functionally

I won’t lie to you, my burgeoning relationship with F# hit a bit of a rough patch recently.

While I’ve understood pattern matching from the outset, I’ve only had a vague idea about Active Patterns. Nothing I’ve read has really made them click for me. So, I decided to focus and try and get a better understanding.

What I managed to grasp almost immediately is that Active Patterns are functions and there are a few different types

  • Single Case
  • Multi-Case
  • Partial

This is where the trouble starts. Most explanations seem to begin with the Single Case Active Pattern on the basis that it is the “simplest”.

Here’s a typical example

let (|ToColor|) x =
    match x with
    | "red"   -> System.Drawing.Color.Red
    | "blue"  -> System.Drawing.Color.Blue
    | "white" -> System.Drawing.Color.White
    | _       -> failwith "Unknown Color"

This converts the value x to a color.

And here’s how we would use it

let (ToColor col) = "red"

These kinds of examples are everywhere and my overwhelming feeling on seeing them is WHY? Why not simply use a function?

let ToColor x =
    match x with
    | "red"   -> System.Drawing.Color.Red
    | "blue"  -> System.Drawing.Color.Blue
    | "white" -> System.Drawing.Color.White
    | _       -> failwith "Unknown Color"

The only difference seems to me to be the way the function is called.

Instead of

let (ToColor col) = "red"

we have

let col = ToColor "red"

Call me old fashioned but the regular function call looks better and more understandable to me. What on
earth is going on in the Active Pattern? A Function, with and out parameter, that accepts another parameter
using assignment?

It just seems daft compared to the more straightforward function call that we know and love. There has to be some scenario that makes the Active Pattern useful, but I’m pretty sure simple conversions like this aren’t it.

I did send out a cry for help on Twitter and I got a few replies showing cases where the Single Active Pattern is necessary, however the examples were quite complicated (to my novice eyes), leading me to think that far from being the “simplest” Active Pattern, the Single Case actually fulfils quite a niche purpose which is not straightforward at all. The Simplistic examples published on various blogs do nothing to illustrate where this feature is actually useful.

So, let’s park the Single Case, I’ll return to is when I’m able to explain it properly. For now, I still don’t understand it. In the Next post I’ll explain the Multiple Case Active Pattern, which I do understand.

Learning To Think Functionally : Readability

This entry is part 10 of 11 in the series Learning to think Functionally

I’m going to be a little unethical here and disclose an answer to Project Euler problem 6.

It’s one of the easier ones, but even still, if you haven’t done it, head on over and solve it now before reading any further. It’ll only take a few minutes.

Here’s the problem:

The sum of the squares of the first ten natural numbers is: 385
The square of the sum of the first ten natural numbers is: 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 − 385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

Simple, right?

Here are a few C# functions that give us the answer we need.

        static int Square(int n)
        {
            return n*n;
        }

        static int SumOfSquares(int first, int count)
        {
            var total = 0;
            for (var i = first; i <= count; i++)
                total += Square(i);
            return total;
        }

        static int SquareOfSum(int first, int count)
        {
            var total = 0;
            for (var i = first; i <= count; i++)
                total += i;
            return Square(total);
        }

We get the solution to the problem by subtracting one from the other:

SquareOfSum(1,100) - SumOfSquares(1,100)

Or, we take a more functional approach to the whole problem and use LINQ:

        static int Square(int n)
        {
            return n*n;
        }

        static int SumOfSquares(int first, int count)
        {
            return Enumerable.Range(first, count).Select(Square).Sum();
        }

        static int SquareOfSum(int first, int count)
        {
            return Square(Enumerable.Range(first, count).Sum());
        }

And we get result just as before:

SquareOfSum(1,100) - SumOfSquares(1,100)

Those Enumerable ranges are cool. I think it’s easier to figure out what’s going on than with the imperative example. That said, while it’s better, I’ve never found the readability of LINQ to be anything special. It’s ok.

Let’s look at the same code in F#

let square x = x * x
let sumOfSquares range = range |> List.sumBy square
let squareOfSum range = range |> List.sum |> square

And we can get our answer as follows:

squareOfSum [1 .. 100] - sumOfSquares [1 .. 100]

I think that reads a little better. You need familiarity with the concept of ‘mapping’ a List. If you’re using the C#/LINQ example above you probably know all you need to know.

Take a look again at the SquareOfSum function in the LINQ example. Reading left to right we encounter the call to Square first even though it happens last. This is quite common in imperative languages when functions calls are nested within function calls.

In F# the Forward-Pipe operator (|>) gets around that problem quite neatly.

We can go further with the F# example.

Since all we’re doing with those ‘range’ values is piping them into a chain of functions, we can get rid of them entirely and simply compose sumOfSquares and squareOfSum directly from List.sum, List.map and square.

let square x = x * x
let sumOfSquares = List.map square >> List.sum
let squareOfSum = List.sum >> square
squareOfSum [1 .. 100] - sumOfSquares [1 .. 100]

Out sumOfSquares and squareOfSum functions are now “Point Free” in Functional Programming parlance.