在F#中生成斐波那契数列

Question

我刚刚开始使用VS2010学习F#,下面是我第一次尝试生成Fibonacci系列.我要做的是建立一个小于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

我的第一个问题是,在最后一个语句中,我在最后一行收到错误消息"表达式中此点或之前的不完整结构化构造".我不明白我在这里做错了什么.

虽然这似乎是以相当有效的方式(从c ++/C#程序员)构建列表的明显方式,但从我对f#的了解很少,这似乎不是正确的方法来执行程序.这种感觉我是否正确？

Answer 1

其他帖子告诉你如何使用递归函数编写while循环.这是在F#中使用Seq库的另一种方法:

// 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

为了解释,请在F#中为项目欧拉问题解决方案2,其中解决了前50个欧拉问题.我想你会对这些解决方案感兴趣.

Answer 2

首先,你使用的let好像是一个声明变异的声明,但事实并非如此.在F#中,let用于声明一个新值(可能隐藏任何以前的同名值).如果你想使用变异编写代码,那么你需要使用类似的东西:

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

你的代码的第二个问题是你试图通过向它添加元素来改变F#列表--F#列表是不可变的,所以一旦你创建它们,你就无法修改它们(特别是没有Add成员!).如果你想用变异写这个,你可以写:

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

但是,正如其他人已经指出的那样,以这种方式编写代码并不是惯用的F#解决方案.在F#中,您将使用不可变列表和递归而不是循环(例如while).例如这样:

// 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)

Answer 3

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

Answer 4

这是使用序列表达式的无限尾递归解决方案.它非常高效,只需几秒钟即可产生第100,000个术语."yield"运算符就像C#的"收益率"和"收益率"一样.运算符可以被读作"全部收益",在C#中你必须做"foreach item ... yield return item".

/sf/ask/160766511/#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

这种方法类似于C#中的以下方法(使用while(true)循环而不是递归):

在C#中查找Fibonacci序列.[项目欧拉演习]

Answer 5

是的，可变变量和 while 循环通常是一个好兆头，表明您的代码功能不是很好。另外，斐波那契数列不是以 1,2 开头，而是以 0,1 或 1,1 开头，具体取决于您问的是谁。

我是这样做的：

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]*)