Project Euler problems with F#

October 10, 2011

Since I’ve just – JUST – started learning F#, I thought I would post my solutions to the first couple problems on Project Euler:

Problem #1: Add all the natural numbers below 1000 which are multiples of 3 or 5.

   1:  let all = [1 .. 999]
   2:  let filtered = all |> List.filter (fun x -> x%3=0 || x%5=0)
   3:  let count = List.sum filtered

So, first we declare a list of all natural numbers (basically, positive integers, since it doesn’t matter here if 0 is included or not) less than 1000. Then, we take that list and filter it for everything that’s divisible by 3 or 5. And finally, sum the list. Pretty easy. Now that I’ve done it. :)

Problem #2: Find the sum of the even-valued terms of the Fibonacci sequence which are less than 4 million.

   1:  let fibSeq = Seq.unfold (fun (a,b) -> Some( a+b, (b, a+b) ) ) (0,1)
   2:  let fibList = fibSeq |> Seq.takeWhile (fun x -> x<4000000 ) |> Seq.toList
   3:  let filterList = List.filter (fun x -> x%2=0) fibList
   4:  let fibSum = List.sum filterList

By far the hardest part about this problem (for me) was figuring out how to create the Fibonacci sequence. This whole unfolding thing is *totally* new. Basically, you’re starting with (a=0,b=1) and applying (a+b, (b, a+b)) for each new element. Once we have the generating function defined, we send that to takeWhile to only grab values less than 4 million, and put those into a new list. Next, we filter the new list, for only even values. Finally, sum those up.

I would *love* feedback on the code. Or how have you done it? I only went back a couple pages, but I didn’t see a single other F# solution in the forum for those two questions!

Also, a (probably very basic) question: I’ve seen several examples where people use List.fold to sum things. Since List.sum exists, would you ever do that IRL? When *would* you use List.fold? I haven’t been able to quite wrap my head around it. Thanks!

tags: ,
posted in F# by rach

Follow comments via the RSS Feed | Leave a comment | Trackback URL

5 Comments to "Project Euler problems with F#"

  1. Chris Ammerman wrote:

    You can think of List.fold as being very similar to IEnumerable.Aggregate. You would us it any time you want to digest a collection to produce a single value. You could use it to take a list of strings and make it a single-string comma-separated list of the individual values, for instance. Or you could use it to calculate the total length of all of the strings added up, using just one method call instead of using loops, or chaining Select and Sum.

  2. Daniel Jackson wrote:

    Much like imperative languages provide a for loop, or a while loop. These loops are isomorphic to general patterns of GOTO. List.fold is a generalization of a pattern of recursion. In functional programming classes of recursive operations have been investigated and chosen for their generality.

    To simplify your understanding, forget about the higher order function you pass to fold as well as the value you use to initialize the accumulator. Then you see fold is simply something like this: ‘a Seq -> ‘b. You give it a list and you get back something else… that something else could even be an ‘a Seq. The dual of this operation would be unfold, where, again ignoring the cruft you have something that is essentially ‘b -> ‘a Seq. In F# there is also foldBack, and you will find that if you initialize it with an empty list and the id function you will get the original list. foldBack (id) [] [1..5], then, is the identity on lists. The dual fold (id) [] [1..5] is the same as reversing the list (the opposite of your list I guess). For more in depth information I suggest the paper by Erik Meijer entitled “Functional Programming with Bannanas, Lenses, Envelopes and Barbed Wire”

  3. rach wrote:

    Thanks Chris, that helps a ton.

    And thanks Daniel — a fantastic explanation, and I will totally check out that paper!

  4. JJoos wrote:

    This is my solution for problem two:
    let solutionA =
    let rec sumEvenFib a b =
    match b with
    | b when b b + sumEvenFib b ( b * 4 + a)
    | _ -> 0

    lazy
    (
    sumEvenFib 0 2
    )

    I did the first 20 problems in f#, but the fora are closed for some time….

  5. rach wrote:

    Nice JJoos — the match keyword is something I haven’t quite gotten a handle on yet. :) I’ll have to make a point of using it in one of the next couple solutions. And maybe they reopened them? I was able to post a couple days ago.

Leave Your Comment

 
Powered by Wordpress and MySQL. Theme by Shlomi Noach, openark.org