Project Euler in F#: Problem 2
Problem 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 evenvalued terms in the sequence which do not exceed four million.
The Thinking
The problem is similar to Problem 1, but this time instead of a natural number sequence, we're to use a fibbonacci sequence, evens only, less than 4 million. Then, we'll need to sum them up; that we did in Problem 1 with Seq.sum. How can we generate the sequence? I'll be taking a simple twostep approach. First, figure out a function to generate a fibbonacci sequence (up through 4,000,000), then take all the evens. We can Seq.sum that resulting sequence to find our answer.
Generating a Fibonacci Sequence
Generating a fibbonacci sequence in F# is a textboook case, and so much so that it's actually an example snippet for the builtin F# function we're going to use to generate it: Seq.unfold. Seq.unfold is a function that returns a sequence, based on a function we provide. It takes two parameters: a sequence element generator function, and the inital value to start with.
Seq.unfold generator state
The generator function must be defined with a single input parameter (the "state value"), and returning an "option tuple of the next element in the sequence and the next state value" (from documentation).
A fibbonacci algorithm requires two inputs (the previous two digits), but we can only pass one parameter. Luckily in F# we have Tuples. A tuple lets us package up several values into a single group, and is written with as a comma separated list inside parenthesis:
let sometuple = ("this", "is", "a", "single", "tuple")
The return value is also something new, using the builtin Option module. We'll be returning an Option, either Some or None. None is a signal to unfold that this is the end of sequence, and for all the rest of the return results, we need to return Something (the next element of the sequence as well as the next state value in tuple form) as we learned above, from the documentation for unfold.
This might seem like a lot to process all at once, but it ends up looking pretty simple when it's all put together. The generator function for fibbonacci numbers less than 4m looks like this:
let fibgen (x,y) = //define a function 'fibgen' and pass in a single parameter, a tuple that represents the most recent two digits of the fibbonacci sequence so far if(x < 4000000) then // define a cutoff threshold to keep the sequence from going on forever Some(x+y, (y, x+y)) // return an Option tuple; the next elemnet of the sequence: x+y (the two most recent elements added together), and the next state value a single tuple that will be used next time the funciton is run else None // we're up to 4m, so tell unfold we're done with the sequence
And now, we can plug that into Seq.unfold:
let fibseq = Seq.unfold fibgen (1,1) // (1,1) is a single tuple parameter with the initial values for the fibgen function
If we run this in the Interactive F# window in Visual Studio, we can confirm this produces the full fibbonacci sequence:
val it : seq = seq [2; 3; 5; 8; ...]
Getting Just The Evens
If you recall our solution to Problem 1, it should be easy to figure out how to make a new sequence with only the even values by using seq, modulo, and yield that we've already learned.
let fibevens = seq{for i in fibseq do if i % 2 = 0 then yield i}
My Solution
Putting it all together, with Seq.sum to add up the sequence:
let fibgen (x,y) = if(x < 4000000) then Some(x+y, (y, x+y)) else None let fibseq = Seq.unfold fibgen (1,1) let fibevens = seq{for i in fibseq do if i % 2 = 0 then yield i} let result = Seq.sum fibevens printfn "%A" result
Project Euler Problem 2: Answered
Further Reading
 Chapter 8 Functions & Functional Concepts, The F# Survival Guide
 Mark Pearl's post on Seq.Unfold, using tuple parameters and pipelines
 Seq.unfold
 Options module
 Tuples
A Post Script
Each part of the above solution is named for clarity. We could easily compose these functions for a more compact solution:
printfn "%A" (Seq.sum(seq{for i in ((1,1) > Seq.unfold(fun (x,y) > if(x < 4000000) then Some(x+y, (y, x+y)) else None)) do if i % 2 = 0 then yield i}))
The only thing that gets weird in this compact version is the anonymous replacement for fibgen, which uses lambda syntax fun & >, and the pipeline operator, > to pass in the intial state. There are some goofy rules for when you can and cannot use piplineing; check out the Pipeline section of Chapter 8 of The F# Survival Guide for a good primer.

Poop On A Baby

Buttz