Claudio Cherubino's blog Life of a Googler

18Jan/080

Project Euler in F# – Problem 1

I'm going through two parallel roads to learn F#: I read the "Foundations of F#" book written by Robert Pickering for the theoretical aspects and then I practice writing some code challenging myself with the problems proposed by Project Euler.

There are currently 177 mathematical exercises that can be ordered by difficulty, so I think that as soon as I solved them I'll master all aspects of F#.

Maybe my solutions are not the best at all, but I'll show them to you and I'll try to use them to explain F# programming while I'm still learning it.

Feel free to ask questions, comment or propose alternative solutions, I'll be glad to compare mine with yours.

So, let's start with the first exercise, which says:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

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

This is a very good introductory exercise and can be used to understand the power of the functional paradigm.

Here is the first version of my code, the explanation will be just below:

#light
let rec sum_mul xs =
  match xs with
  | []    -> 0
  | y::ys when y % 3 = 0 || y % 5 = 0 -> y + sum_mul ys
  | y::ys -> sum_mul ys

let sum = sum_mul [1 .. 999]
print_any sum

The #light clause at line 1 allows us to write code with a simpler syntax, without all the symbols and keywords, such as begin and end.

At line 2 we have the definition of a recursive function called sum_mul that accepts an argument called xs.

To define functions and literals (we don't call them variable, since their value never changes) you need to use the let keyword.

Then, in lines 3-6 we have an example of pattern matching, that is a common practice in functional programming similar to the switch statement of the imperative paradigm.

It compares xs with some patterns, which are written one per line, with a | (pipe) in front of each of them.
The first case is matched when xs is an empty list, and in that case sum_mul simply returns 0.

In the other cases xs is matched against a list, with the first element (the head of the list) being called y and the rest of the list (the tail) called ys.

If y is evenly divided by 3 or 5 (using the modulus operator: %) we add the number to our result and then recursively apply the same function to the tail.
Otherwise we just skip the head and call sum_mul on the tail.

At line 8 we actually call the sum_mul function passing a list as the argument. This list is composed by all integers between 1 and 999.

Line 9 is just used to print the output to screen.

If you want to run this code you can use Visual Studio with the F# plugin installed or simply run the F# interpreter, which is a command line tool called fsi.exe and is installed with the F# package.

I hope the explanation was clear and you started to appreciate the power of functional programming.
In the next article I'll show you an alternative (and much faster) solution to the same problem.

Comments (0) Trackbacks (2)

Leave a comment

(required)