A first post

Lately I've been experimenting with F# from Microsoft Research and this is more or less just a post to get my blog going and to try out some code highlighting and the blog design. After some looking around I've decided to choose the oCaml highlighting from tohtml.com. Iris seems like a nice alternative too, but I disliked it putting the code in a centered "box".

Fibonacci bonanza
So, as an introductionary post here are some Fibonacci numbers implemented in F#. Fibonacci is a sequence of numbers where each number is the sum of the two preceding numbers. Like this:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765...etc.

The Fibonacci numbers are probably most known to programming students as a way to introduce recursion. All F# code I post is with the #light syntax and with that a classic recursive implementation in F# would look something like this:

let rec fib x =
    if x <= 2 then 1
    else fib (x-2) + fib (x-1)

Another recursive implementation is using the match syntax. At a first look match looks like a normal switch statement in C#, however it is much more powerful and I'm sure I will return to it later in my exploration of F#.

let rec fib x =
    match x with
    | 1 | 2 -> 1 
    | x -> fib (x - 1) + fib (x -2)

Note that in F# you need to write out that it is a recursive function with the rec keyword. Both these implementations are beautiful but lacking when it comes to performance. A simple fib 40 takes 1.5 seconds to calculate on my computer. Compare this to a non recursive version like this one:

let fib x =
    let temp = ref 1
    let f1 = ref 1
    let f0 = ref 0
    for i = 2 to x do
        temp := !f1
        f1 := !f0 + !f1
        f0 := !temp + !f1
    !f1

This implementation takes only around 0.02 seconds to run fib 40. This one is quite ugly however, but it is possible to write a efficient and beautiful Fibonacci in F# style using cashing. I might return to that in a later blog post.

To measure time I used the #time;; switch in the F# interactive console in Visual Studio 2005. Results look like this:

Real: 00:00:00.01, CPU: 00:00:00.00, GC gen0: 0, gen1: 0, gen2: 0.