Claudio Cherubino's blog Life of a Googler

23Apr/087

Remove duplicate values from a List in F#

Once in a while I give a look at the web server log to find out how people landed in this blog and yesterday there was someone that entered the following search string into Google:

Given a random List of integers, write a function that removes all the duplicate values

This site appears as the first result, even if there is no solution for that problem, but I want to help you anyway, unknown visitor!

In fact, we can make use of the Set data type to easily solve the problem.

According to the definition, a Set represents a collection of elements without duplicates.
So, if we create a Set from the given list, all duplicate values will be automatically filtered.

This can be done in a single line, I'll call the function nub because this is the name of the corresponding Haskell one:

let nub xs = xs |> Set.of_list |> Set.to_list

As I said, to return a List without duplicate values we just need to create a Set from it and then create a List from the new Set.

Do you think it is fair to act this way or should I say that I'm cheating? :)

25Jan/080

Project Euler in F# – Problem 9

Today's exercise is Project Euler Problem 9, that says:

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,
a² + b² = c²

For example, 3² + 4² = 9 + 16 = 25 = 5².

There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.

Therefore this time we have to find a triplet (a, b, c), but a brute-force approach would require a billion combinations, since the three numbers can range from 1 to 1000.

However, we can reduce the number of tests exploiting a little algebra.

First of all, c = 1000 - a - b, so only two variables are in play, leading us to a million choices.

Then we go down to half a million, thanks to the constraint that a < b.

According to these premises, here is the F# code:

#light
let sq x = x * x

let ab =
    { for a in 1 .. 1000
      for b in a .. 1000 -> a,b } |> Seq.filter (fun (a,b) -> sq a + sq b = sq (1000 - a - b) ) |> Seq.hd

let answer =
    let a = fst ab
    let b = snd ab
    let c = 1000 - a - b
    a * b * c

At line 5 we enumerate all items of a collection created with list comprehension, i.e. the numbers between 1 and 1000.

Inside this loop we have another loop, but in this case we are interested in all numbers bigger than the current item of the outer collection, i.e. all numbers between a and 1000.

Then, we filter all couples (a, b) keeping only those for which we have: a² + b² = (1000 - a - b)².

According to the text of the exercise, there exists exactly one Pythagorean triplet that satisfies the equation a + b + c = 1000, so we can apply the Seq.hd (head) function to take the first (and only) element of the generated sequence.

At lines 9, 10 and 11 we evaluate a, b and c and finally we multiply them to get the answer.