One of the languages I have decided to learn this year is F Sharp. F# is a multi paradigm programming language; it is capable of expressing ideas in an imperative, functional and object oriented fashion. It is the result of some very hard work by Microsoft Research and integrates into VS2005 and 2008. F# rounds out the MS language ecosystem quite nicely i think, as it provides a solid platform for mathematical solutions, as well as maintaining the ability to be used to create windows applications of all types.

I decided to get my head around using it by reading Foundations in F# and by undertaking Project Euler, a series of mathematical puzzles. I'm certainly not alone, and to set myself apart from those who have trod before me, I've decided to compare the solutions in F# to possible solutions in to my favourite language: C# 3.0. Since I am no maths expert, this could be a real trainwreck...

Question 1: Find the sum of all the multiples of 3 or 5 below 1000.

Sounds simple enough. We can use mod 3 and mod 5 to filter a list of positive numbers below 1000 and sum the result. One approach might be:

static int Problem1()
{
  return MultiplesOfThreeAndFiveBelow(1000).Sum();
}

static IEnumerable<int> MultiplesOfThreeAndFiveBelow(int n)
{
  for (var i = 0; i < n; i++)
  {
    if (i % 3 == 0 || i % 5 == 0)
    yield return i;
  }
}

OK, so thats a little expensive, I've used a generic list instead of an array, but hey it works. Its main strength is that its readable. So how about a functional approach? 

let solution = Array.init 1000 (fun x -> if x % 3 = 0 || x % 5 = 0 then x else 0 )
               |> Array.fold_left (+) 0

Array.fold_left is a higher order function, since it accepts a function as a parameter. I am passing it the addition operator (a function in its own right) and an accumulator initialized to 0. The first iteration of the fold function will take the value of first element of the sequence and add it to zero. The result is then added to the value of the next element in the sequence to produce a new result and so on. Essentially, it provides the summation required to complete this problem. The downside with this approach is that it naively overestimates the size of the array required, and folding left doesnt immediately lead the reader to think of summation.

I can do better though, F# provides us some constructs for more efficient array initialisations; a comprehension syntax:

let solution = Array.fold1_left (+) [|
                                       for x in 1 .. 999 
                                       when x % 3 = 0 || x % 5 = 0 -> x
                                    |]

While this is readable, some might complain that Array.fold1_left is a cryptic way to summate, and is therefore hard to maintain, so without much effort we can curry it to look like this:

let summate a = Array.fold1_left (+) a
let solution = summate [|
                           for x in 1 .. 999 
                           when x % 3 = 0 || x % 5 = 0 -> x
                       |]

I've split the array initialization over 4 lines for extra readability but in essence its only 1-2 lines of readable code to solve Project Euler Problem 1 using F#.

So, for those of you interested in speed, using the time honored technique of taking the average execution time over 1 million executions, the C# implementation came in at around 10 times faster than the final F# one. The first F# implementation was faster but was still two times slower than C#. The main bottleneck seemed to be the array initialization; using the comprehension syntax is a little pricey. But, who cares about optimization anyway? It was only the difference between fractions of a millisecond anyhow :)