Generating Fibonacci series in F#

Question

I'm just starting to learn F# using VS2010 and below is my first attempt at generating the Fibonacci series. What I'm trying to do is to build a list of all numbers less than 400.

let fabList = 
    let l =  [1;2;]
    let mutable a = 1
    let mutable b = 2
    while l.Tail < 400 do
        let c = a + b
        l.Add(c)
        let a = b
        let b = c

My first problem is that on the last statement, I'm getting an error message "Incomplete structured construct at or before this point in expression" on the last line. I don't understand what I'm doing wrong here.

While this seems to be an obvious way to build the list in a fairly efficient way (from a c++/C# programmer), from what little I know of f#, this doesn't seem to feel to be the right way to do the program. Am I correct in this feeling?

Solution 1

First of all, you're using let as if it was a statement to mutate a variable, but that's not the case. In F#, let is used to declare a new value (which may hide any previous values of the same name). If you want to write code using mutation, then you need to use something like:

let c = a + b  // declare new local value
l.Add(c)  
a <- b   // mutate value marked as 'mutable'
b <- c   // .. mutate the second value

The second issue with your code is that you're trying to mutate F# list by adding elements to it - F# lists are immutable, so once you create them, you cannot modify them (in particular, there is no Add member!). If you wanted to write this using mutation, you could write:

let fabList = 
  // Create a mutable list, so that we can add elements 
  // (this corresponds to standard .NET 'List<T>' type)
  let l = new ResizeArray<_>([1;2])
  let mutable a = 1
  let mutable b = 2
  while l.[l.Count - 1] < 400 do
    let c = a + b
    l.Add(c) // Add element to the mutable list
    a <- b
    b <- c
  l |> List.ofSeq // Convert any collection type to standard F# list

But, as others already noted, writing the code in this way isn't the idiomatic F# solution. In F#, you would use immutable lists and recursion instead of loops (such as while). For example like this:

// Recursive function that implements the looping
// (it takes previous two elements, a and b)
let rec fibsRec a b =
  if a + b < 400 then
    // The current element
    let current = a + b
    // Calculate all remaining elements recursively 
    // using 'b' as 'a' and 'current' as 'b' (in the next iteration)
    let rest = fibsRec b current  
    // Return the remaining elements with 'current' appended to the 
    // front of the resulting list (this constructs new list, 
    // so there is no mutation here!)
    current :: rest
  else 
    [] // generated all elements - return empty list once we're done

// generate list with 1, 2 and all other larger fibonaccis
let fibs = 1::2::(fibsRec 1 2)

Solution 2

Other posts tell you how to write the while loop using recursive functions. This is another way by using the Seq library in F#:

// generate an infinite Fibonacci sequence
let fibSeq = Seq.unfold (fun (a,b) -> Some( a+b, (b, a+b) ) ) (0,1)
// take the first few numbers in the sequence and convert the sequence to a list
let fibList = fibSeq |> Seq.takeWhile (fun x -> x<=400 ) |> Seq.toList

for explanation, please ref solution 2 in F# for Project Euler Problems, where the first 50 Euler problems are solved. I think you will be interested in these solutions.

Solution 3

let rec fibSeq p0 p1 = seq {
    yield p0
    yield! fibSeq p1 (p0+p1)
}

Solution 4

Here's an infinite tail-recursive solution using sequence expressions. It's quite efficient, producing the 100,000th term in just a few seconds. The "yield" operator is just like C#'s "yield return", and the "yield!" operator may be read as "yield all", where in C# you would have to do "foreach item ... yield return item".

https://stackoverflow.com/questions/2296664/code-chess-fibonacci-sequence/2892670#2892670

let fibseq =    
    let rec fibseq n1 n2 = 
        seq { let n0 = n1 + n2 
              yield n0
              yield! fibseq n0 n1 }
    seq { yield 1I ; yield 1I ; yield! (fibseq 1I 1I) }

let fibTake n = fibseq |> Seq.take n //the first n Fibonacci numbers
let fib n = fibseq |> Seq.nth (n-1) //the nth Fibonacci number

This approach is similar to the following in C# (which uses a while(true) loop instead of recursion):

Finding Fibonacci sequence in C#. [Project Euler Exercise]

Solution 5

Yes, mutable variables and while loops are usually a good sign that your code is not very functional. Also the fibonacci series, doesn't start with 1,2 - it starts with 0,1 or 1,1 depending on who you ask.

Here's how I'd do it:

let rec fabListHelper (a:int,b:int,n:int) =
  if a+b < n then
    a+b :: fabListHelper (b, a+b, n)
  else
    [];;

let fabList (n:int) = 0 :: 1 :: fabListHelper (0,1, n);;

(*> fabList 400;;
val it : int list = [0; 1; 1; 2; 3; 5; 8; 13; 21; 34; 55; 89; 144; 233; 377]*)

View more solutions

Comments

[Matti Virkkunen]

Yes, you're doing it wrong. You're using a functional programming language like a procedural one. Try doing it without using while or any similar loop constructs at first.

[sepp2k]

a) This is a terribly inefficient way to calculate a fibonacci number and b) using this to create a list is even less efficient because you have to calculate the whole thing again for each item in the list.

[photo_tom]

Thanks for the detailed answer. Immutablity as a normal programming mode is something that I'm still trying to get use to and your explanation clarified concepts for me. Not to mention functional programming.

[Tomas Petricek]

@photo_tom: That's how all of us who have imperative background feel for the first time :-). Immutability is one of the essential concepts and the rest of functional ideas follow from that.

[Rune FS]

Very nice answer. One point worthwhile mentioning would be the fact that as a general approach when creating recursive functions the Call to the function it self should always be the last operation in that particular branch so that a tail Call optimization Can be performed. In this particular case with 400 as the limit a stackoverflow is of cause usually not an issue

[photo_tom]

Thanks for link - for F# for Project Euler Problems. I am working on some of those problems to help learn F#.

[Onorio Catenacci]

fabListHelper wouldn't be tail-call optimized would it? I mean the cons "a+b::fabListHelp(b,a+b,n)" prevents tail call optimization doesn't it?

[photo_tom]

C# use of yield is something I'm going to have to work on. A completely new way of thinking about yield. I'm just learning F#, so f# answer is cool, but makes my head hurt trying to understand it. Thanks!!!

[Stephen Swensen]

Indeed! I picked up the Expert F# book in 2008, read through it and absorbed as much as I could, but wasn't really ready for it at that time. However, it got me experimenting with yield/IEnumerable and delegates in C# at my day job (even pre-linq C# 2.0 has those features), and I've found now, two years later, I'm having a much easier time tacking F# in earnest.

[Be Brave Be Like Ukraine]

Your answer seems to be a duplicate of @DavidReihans'. Also, as noted in comments to other questions, this approach is neither effective nor tail-recursive.

[Mike]

I think the first line should actually be: let fibSeq = Seq.unfold (fun (a,b) -> Some( a+b, (a+b, a) ) ) (0,1)

[rmunn]

Downvoted because bare code, with no explanation, is not likely to help an OP who describes himself as "just starting to learn F#".

[Charly]

The F# for Project Euler Problems website has expired, here's an archive: web.archive.org/web/20120702222856/http://…

[Grozz]

np. I agree with the reason.

[Pontus Hultkrantz]

Nice, infinite sequence to be evaluated lazily. Just don't try to convert the infinite seq to an array or List, unless you have a lot of RAM ;).

[Srivathsa Harish Venkataramana]

It is worth noting to pipe fibSeq to Seq.Cache for better performance