In the past few weeks, as I've written on this here weblog, I've been trying my darndest to learn F#. So far, I've been reading Expert F# by Don Syme, Adam Granicz, and Antonio Cisternino; THE book on F# written by the inventor of F# (If you're at all interested, grab it). While I'm definitely not an expert on the matter yet, hopefully this will help someone, somewhere along the line. 

 On my quest for complete and thorough erudition of F# through experiencing it first hand, I discovered Project Euler. This is exactly what I was looking for, a platform to think of new ways to implement what I already know about F#, and more importantly what I don't, to solve complex math problems. Sure, this isn't isn't too complex, but this is just number 2 of 180 problems (some of the higher ones are very complicated, but I'll touch on that another day). I definitely recommend the site to anyone who is learning F# (or anybody, really).

Euler Question #2:

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.

 
... And my implementation. 
 

#light

open System.Collections.Generic

let fibList = new Dictionary<int, int>()
let rec fib n = if fibList.ContainsKey(n) then fibList.[n]
                elif n < 2 then fibList.[n] <- 1; fibList.[n]                      
                else fibList.[n] <- (fib (n-2) + fib(n-1)); fibList.[n]
                
let probAns =
        [1 .. 30]
        |> Seq.map (fun a -> fib(a))
        |> Seq.filter (fun x -> x % 2 = 0 && x <1000000)
        |> Seq.fold (+) 0
        |> printfn "Answer: %d"

 

 Modeling the actual solution (probAns) after Robert Pickering's beautiful implementation of Euler #1:

let problem1 =

       [1 .. 999]

       |> Seq.filter (fun x -> x % 3 = 0 || x % 5 = 0)

       |> Seq.fold (+) 0      

printfn "Problem 1 = %d" problem1

 (Taken from the comments on Chris Smith's blog) 

 For me, Euler #2 had been the most absolutely frustrating thing I've run into with F# so far. Alas, I crushed my obstruction (I read the question wrong :[ ) and came out the undisputed victor.

First, I went ahead and popped in my implementation of the fibonacci sequence. I had read Scott Hanselman's and Dustin Cambell's posts about fibonacci sequences awhile back and had a super-fast fibonacci sequence saved on file that I made as soon as I learned how to implement Dictionaries in F#. It's set up to limit the rediculous amount of recursion by having a dictionary already that has every number that has already passed through. You say it's not in the dictionary? No problem! It'll compute the value for n and toss it in the dictionary for super-fast look-up the next time around. There may be better ways of implementing the Fibonacci sequence out there that I just don't know of yet. If anyone has suggestions feel free to post in the comments. Alright, that's out of the way.

[1 .. 30]
|> Seq.map (fun a -> fib(a))

 Now the actual solution. I went ahead and set up a sequence of 1 to 30 ([1 .. 30]) in probAns. (The number 30 itself doesn't matter very much. I just went for overkill to make sure that the sequence would eventually go over 1,000,000 when applied to my Fibonacci function) I took this sequence and passed it to the Seq.map aggregate operator using the forward pipe operator.

this guy:  |>

The forward pipe operator kind-of applyis the function order backwards; pushing the values in before the aggregate operator rather than behind the function. I could've implemented it as "Seq.map (fun x -> fib(x)) probAns", but for that to work I would have to toss the mapped value into a completely different sequence. That's NOT what we want. The forward pipe operator makes life much easier. 

        |> Seq.filter (fun x -> x % 2 = 0 && x <1000000)

 
Back on topic, this returned a new sequence with the values of [1 .. 30] run through the Fibonacci function. I now have a sequence full of EVERY Fibonacci value from 1 to 30. It looks like we need to find just the even-valued terms, so I ran the Fibonacci-filled sequence through the Seq.filter aggregate operator. To filter, a boolean function is tossed in (in this case, fun x -> x % 2 = 0 && x <1000000) and filtered based on which values inside the sequence are true. Now we have everything we need, now it's time to put it all together.

        |> Seq.fold (+) 0
        |> printfn "Answer: %d"

Seq.fold passes a function through the whole sequence along with an accumulator and accumulates(go figure) to return a single, nice, beautiful int (in this case). All that's left is to output the answer, which is done by using the forward pipe operator along with printfn. One of the nice things about printfn is that the format strings are type-safe, which is why %d is in my printfn statement. If you want to learn a bit more about this, check out Dustin's blog (linked below). That's it! +1% 

 If you're at all interested in hearing about some of the other amazing stuff in F#, check out Dustin Campbell's series on why he loves F# too. 

Posted on: 2/5/2008 at 8:23 AM
Categories: Development | F#
Actions: E-mail | Kick it! | DZone it! | del.icio.us
Post Information: Permalink | Comments (2) | Post RSS