Project Euler in F# - Problem 2

It’s been a few days, so here is Project Euler’s problem 2 in F#.

 

Problem 2 is defined as follows:

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

Find the sum of all the even-valued terms in the sequence which do not exceed one million.

 

Sounds simple enough, here’s my Solution in F#

#light

let problem2 =

    let fibs =

        (1,1) |> Seq.unfold

            (fun (n0,n1) ->

                if n0 <= 1000000 then

                    Some (n0, (n1, n0 + n1))

                else

                    None)

    fibs |> Seq.fold

        (fun acc x ->

            if x % 2 = 0 then

                acc + x

            else

    acc) 0

printfn "Problem 2 = %d" problem2

The first thing I do is define a function called ‘fibs’, which will return the list of all Fibonacci numbers less than one million. To do this, I use the ‘Seq.unfold’ function which is valuable but somewhat tricky. I’ll go into more detail of how it works later in this post. Next, I take the sequence of Fibonacci numbers I generated and sum the even terms. So other than the ‘Seq.unfold’ jazz everything is pretty straight forward.

 

Before I explain what Seq.unfold does, let me explain the syntax. An interesting language concept in F# is the tuple, or group of values. The syntax “(1,1)” refers to a single object/element/thingey that has two parts; but a tuple can have any number of thingies inside of it. The second thing I’ll draw your attention to are the ‘Some’ and ‘None’ methods. Notice that if n0 <= one million, ‘None’ is called – intuitively ending our sequence of Fibonacci numbers under a million. Also, note that the ‘Some’ method is taking a tuple as a parameter, with one part of that tuple being another tuple. (At first glance it is easy to look at this syntax as a function’s parameters, but please resist this temptation.)

 

So now we sort of know the language constructs in place, let’s go into what Seq.unfold does. Seq.unfold produces a sequence of values from continually calling a function. That function passes the result of the previous computation along with an optional, intermediary value on ward. ‘Some’ indicates that there is something left in the sequence, and the process continues. ‘None’ indicates that the sequence should end. To better explain this, consider the following example:

#light

open System

let powersOf x = (x, 0.0) |> Seq.unfold (function (base, power) -> Some(Math.Pow(base, power), (base, power + 1.0)))

let powers2 = powersOf 2.0

let powers3 = powersOf 3.0

printfn "Powers of 2 = %A" (Seq.take 5 powers2)

printfn "Powers of 3 = %A" (Seq.take 5 powers3)

Which produces the following:

Powers of 2 = [1.0; 2.0; 4.0; 8.0; 16.0]

Powers of 3 = [1.0; 3.0; 9.0; 27.0; 81.0]

To explain how the ‘powersOf’ function works, we start with (x, 0.0) and pass that to Seq.unfold. We indicate that there the next value in the sequence is System.Math.Pow(x, 0.0) and then repeat the process with the same base but increment the power by one. So the next value in the sequence is Pow(x, 1.0) and so on. The net result is producing a sequence of powers of a number. Notice the fact that in our function we never call ‘None’; we have just produced an infinite sequence which literally goes on forever – or until we get an overflow exception. (You can do this sort of thing in C# using 'yield return'.)

 

Anyways, if you can think of a more elegant way to solve the problem please post a comment. One of the great things about F# is just how elegantly you can solve problems like these. Also, the original problem is copyright the folks at Project Euler.

Comments

• Anonymous
  October 26, 2007
  PingBack from http://msdnrss.thecoderblogs.com/2007/10/26/project-euler-in-f-problem-2/

• Anonymous
  October 26, 2007
  PingBack from http://msdnrss.thecoderblogs.com/2007/10/26/project-euler-in-f-problem-2/

• Anonymous
  November 14, 2007
  I've played with this problem http://khigia.wordpress.com/2007/11/14/euler-problem-2/ and I'm not happy with my solution! ;)

• Anonymous
  November 20, 2007
  I'm please to announce that starting Monday I'll be joining the F# team as (currently) the only full-time tester. I'm super-excited about this for many reasons, but the biggest is knowing what an impact I'll have. Without a doubt F# will change the .Net

• Anonymous
  December 30, 2008
  I'm just getting started with F#, and I was wondering - is there an advantage to using Seq.fold over chaining a Seq.filter with a Seq.sum? fibs |> Seq.filter (fun x -> x % 2 = 0) |> Seq.sum

• Anonymous
  December 30, 2008
  I don't think so. There might pick one over the other to do micro optimization, but they should behave the same.