tags:

views:

411

answers:

5

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?

A: 

Here's a good article by .Net guru Scott Hanselman on generating fibonacci series in F#

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

http://www.hanselman.com/blog/TheWeeklySourceCode13FibonacciEdition.aspx

It also compares with other languages as a reference

David Relihan
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.
sepp2k
+2  A: 

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]*)
sepp2k
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?
Onorio Catenacci
+9  A: 

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)
Tomas Petricek
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.
photo_tom
@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.
Tomas Petricek
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
Rune FS
+7  A: 

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.

Yin Zhu
+1 short, non recursive, and infinite!
Aviad P.
@Yin Zhu - Thanks for link - for F# for Project Euler Problems. I am working on some of those problems to help learn F#.
photo_tom
+1  A: 

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".

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

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

http://stackoverflow.com/questions/1580985/finding-fibonacci-sequence-in-c-project-euler-exercise/1581055#1581055

Stephen Swensen
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!!!
photo_tom
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.
Stephen Swensen