Fibonacci Fun with F#

As you probably know, the Fibonacci sequence is the infinite sequence of integers where each element is the sum of the previous two (the first two elements being 0 and 1). Recently, I was inspired by a blog post, Ruby vs. Haskell – project Euler #25 deathmatch. In particular, I enjoyed the Haskell solution for its simplicity and declarativeness.

I decided to try and solve the same problem, but using F#, the functional programming language being introduced as a first class .NET citizen for the first time with Visual Studio 2010. If you have never seen F# code before, the snippets included in this post may be difficult to comprehend, especially if you are used to reading code written in imperative languages like C# or Java.

To declaratively create infinite sequences in F#, the Seq module provides the unfold function. This function takes two parameters, a generator function and an initial state. The generator function must take a state parameter and produce an option tuple with a sequence element and a new state. In F# notation, the unfold function has the signature Seq.unfold : ('State -> 'T * 'State option) -> 'State -> seq<'T>. Note that if the generator function always returns Some(_) and never None, the resulting sequence will be infinite.

An example of Seq.unfold in action is shown in the following one-liner, producing an infinite sequence of all positive integers.

let positiveIntegers = Seq.unfold (fun x -> Some(x, x + 1)) 1

In this example, the generator function takes an integer state as input. The sequence element produced by this function is the current state, while the next state is calculated by incrementing the current state. Thus, each time the generator function is called, the input integer state is one higher than the previous time. The initial state, 1, is passed as the final parameter to Seq.unfold. The result is the sequence “1, 2, 3, …, ∞” (or, strictly speaking, as far as 32 bit integers go).

So, how do we go from this sequence to the Fibonacci sequence? First of all, since each element of the Fibonacci sequence is the sum of the previous two, the state cannot consist only of a single integer. Rather, the state has to be a tuple of two integers. By choosing (0, 1) as the initial state, the generator function can use the first tuple element as sequence output and construct the next state as ([next], [current] + [next]), where [current] and [next] are the first and second element, respectively, from the current state tuple.

Translated into F# code, this yields the following definition of the Fibonacci sequence.

let fibonacci =
    Seq.unfold
        (fun (current, next) -> Some(current, (next, current + next)))
        (0, 1)

When enumerating this sequence, however, one problem becomes apparent. Element number 48 is a negative number. This is definitely erroneous behavior, as the Fibonacci sequence consists solely of positive integers. The error is due to the limited value space of 32 bit integers, causing an overflow. To circumvent this problem, we can use the BigInteger type, capable of representing integers of arbitrary size. The only change we need to make to our original Fibonacci definition is to change the initial state tuple to contain BigInteger values. The F# type inference system handles the rest.

open System.Numerics

let fibonacci =
    Seq.unfold
        (fun (current, next) -> Some(current, (next, current + next)))
        (BigInteger 0, BigInteger 1)

Now to the actual solution to Project Euler #25. Modelled after the previously mentioned Haskell solution, my solution also counts the number of elements in the Fibonacci sequence having a value less than 10999.

Again, translating this into F# results in the following code.

open System.Numerics

let limit = BigInteger.Pow(BigInteger 10, 999)

let fibonacci =
    Seq.unfold
        (fun (current, next) -> Some(current, (next, current + next)))
        (BigInteger 0, BigInteger 1)

let term =
    fibonacci
    |> Seq.takeWhile (fun n -> n < limit)
    |> Seq.length

printfn "%d" term

I am intrigued by how this functional solution focuses on what the Fibonacci sequence is, rather than how it is calculated. Constructing an infinite Fibonacci sequence in C# would typically require an iterator consisting of an infinite loop, representing state with two local variables. Counting elements having a value less than 10999, however, could easily have been accomplished in a functional manner using LINQ.

Advertisements

4 thoughts on “Fibonacci Fun with F#

  1. How does the Seq implementation perform? It would be interesting to know what kind of optimizations are available to what is essentially a lazy list type (from what I gather).

  2. The performance of Seq.unfold is closely corellated to the performance of the generator function used. For each element requested when enumerating the sequence, the generator function is called, producing the next value of the sequence.

    Technically, the lazy sequence produced by Seq.unfold is simply an IEnumerable object.

  3. Yep, I understand unfold — I’ve written several of the Haskell libraries for optimizing sequenes, and getting unfold to optimize well is key to performance of generators.

    Did you try measuring anything? What’s the cost of sequences over iteration?

  4. No, I did not perform any measures comparing the performance of sequences over iteration. I’m learning F# these days, and for me, this was simply a fun thing to do along the way. However, comparing the cost of sequences over iteration is a good idea for a follow-up post. Any pointers on how to best perform such measures are much welcome.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s