Claudio Cherubino's blog Life of a Googler

19Nov/083

Project Euler in F# – Problem 19

When someone asks me what are the advantages of F# in comparison with the other functional programming languages, usually the first thing I answer is the .Net Framework.

This framework provides the developers with a plethora of libraries and functions that cover almost all the requirements you can imagine and if you need something that is missing, you will surely develop it on top of solid basis.

I can prove this by showing you the F# solution to Project Euler problem number 19:

How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?

After the first time I read the problem I started wondering on how to check whether a given date is a Sunday and a "smart" solution suddenly came into my mind.

The .Net Framework contains a robust set of classes and functions to work on dates and F# can use them as C#, VB.Net and all the other supported languages.

The algorithm implemented works in the following way: we create a starting DateTime object representing 1 Jan 1901 and then continue adding 1 month (using the AddMonths function) until we get to year 2001.

For each DateTime objects returned by this sequence we check if its DayOfWeek property is equal to DayOfWeek.Sunday (.Net magic!). In this case we keep the value otherwise we simply discard it.

Eventually we just have to count the number of items (i.e. DateTime objects) left and we get the result.

Let's translate the algorithm into F# syntax and we get the following code:

#light
open System

let startDate = new DateTime(1901, 1, 1)

let euler19 = startDate
              |> Seq.unfold (fun (x : DateTime) -> Some(x, x.AddMonths(1)))
              |> Seq.take_while (fun (x : DateTime) -> x.Year < 2001)
              |> Seq.filter (fun (x : DateTime) -> x.DayOfWeek = DayOfWeek.Sunday)
              |> Seq.length
12Feb/082

Project Euler in F# – Problem 22

Unlike pure functional programming languages, F# is a multi-paradigm language, so you can mix object-oriented code with functional one, mainly to exploit the features of the .Net framework.

In Project Euler Problem 22 we are asked to open a file (imperative paradigm) containing a long list of names, sort them and perform some calculation on the characters composing the text.

Here is the description of the exercise:

Using names.txt (right click and 'Save Link/Target As...'), a 46K text file containing over five-thousand first names, begin by sorting it into alphabetical order. Then working out the alphabetical value for each name, multiply this value by its alphabetical position in the list to obtain a name score.

For example, when the list is sorted into alphabetical order, COLIN, which is worth 3 + 15 + 12 + 9 + 14 = 53, is the 938th name in the list. So, COLIN would obtain a score of 938 × 53 = 49714.

What is the total of all the name scores in the file?

In order to open the given file, we rely on the IO functions provided by the .Net Base Class Library (BCL), that we can access thanks the open statement at line 2 of the following code:

#light
open System.IO

let names = File.ReadAllText("names.txt").Split([|','|]) |> Seq.to_list
let couples = names |> List.map (fun x -> x.Replace("\"", "")) |> List.sort compare |> List.zip [1 .. names.Length]

let score (pos, str) =
    let value = str |> Seq.map (fun x -> (1 + Char.code x - Char.code 'A')) |> Seq.fold1 (+)
    value * pos

let answer = couples |> Seq.map score |> Seq.fold1 (+)

At line 4 we read the whole content of the names.txt file, split it on the "," (comma) characters and store the result in a list called names.

Since the names written in the file are enclosed by double quotes, we have to remove all of them with the Replace function before we can alphabetically sort the list.

When names is sorted, we combine (zip) it with another list containing the position of each element inside the sequence itself, i.e. the numbers from 1 to the length of the names list.

The result is a sequence of tuples (position, name) such as (938, "COLIN").

At line 7 we define the main function of this exercise, called score. It takes a couple (position, name) and returns the name score, which is computed multiplying the alphabetical value of the name by its position.

The value of a name is obtained by summing the position in the alphabet of each character composing the name itself.

The Char.code function converts the value of a Unicode character to an integer, so we just need to subtract from it the code of the first letter of the alphabet ("A") to get its alphabetical position.

Please notice that using "A" as the first element works because in the input file all names are written with uppercase characters only.

Then we multiply the alphabetical value of the name by its position to return the score of the couple passed as argument.

The exercise asks us to sum the scores of all elements in the input file, so we map the score function and sum the results with fold1 (+), getting the correct answer.

15Jan/080

let title = "Hello World"

When I was attending the first year of my university course, a teacher of mine used Haskell to teach us the basics of software development.

It was amazing, functional programming makes you think differently about programming.

In the functional paradigm functions are used in their real mathematical sense.
Hence, they are only computation objects and there is no information about state or mutable data.

Functional programming languages exist since more than 50 years ago, LISP is one of them, but they have never been seriously adopted outside the academia.

Now, the computer science world is gradually moving toward functional programming.

There is a lot of hype surrounding Erlang, a functional language originally developed by Ericsson, and in 2007 Microsoft presented F#, which is a multi-paradigm language targeting .Net and largely based on OCaml.

In this blog I'll write down my progresses in learning this language and I hope that you can profit from my experience.

I'll come back to you soon with the first article, if you want in the meanwhile you can start from the links on the right side of the page.

Bye!