Generazione serie di Fibonacci in F #

Question

Sto solo iniziando a imparare F # utilizzando VS2010 e sotto è il mio primo tentativo di generare la serie di Fibonacci. Quello che sto cercando di fare è quello di costruire una lista di tutti i numeri meno di 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 

Il mio primo problema è che l'ultima affermazione, sto ricevendo un messaggio di errore "costrutto incompleta strutturato al momento o prima questo punto nell'espressione "sull'ultima riga. Non capisco cosa sto facendo male qui.

Mentre questo sembra essere un modo ovvio per costruire l'elenco in modo abbastanza efficiente (da un programmatore C++/C#), da quel poco che so di f #, questo non sembra essere il modo giusto fare il programma. Sono corretto in questo sentimento?

Answer 1

Prima di tutto, si sta utilizzando let come se fosse una dichiarazione di mutare una variabile, ma non è questo il caso. In F #, let viene utilizzato per dichiarare un nuovo valore (che potrebbe nascondere qualsiasi valore precedente con lo stesso nome). Se si desidera scrivere codice usando mutazione, allora avete bisogno di usare qualcosa come:

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

Il secondo problema con il codice è che si sta cercando di mutare F # lista con l'aggiunta di elementi ad esso - F # liste sono immutabili quindi, una volta creati, non è possibile modificarli (in particolare, non esiste un membro Add!). Se si voleva scrivere questo utilizzando mutazione, si potrebbe scrivere:

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 

Ma, come altri già notato, scrivere il codice in questo modo non è la soluzione # idiomatica F. In F #, si utilizzano elenchi e ricorsioni immutabili anziché cicli (ad esempio while). Ad esempio:

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

Ecco un buon articolo di .Net guru Scott Hanselman sulla generazione di serie di Fibonacci 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

Esso mette a confronto anche con altri linguaggi come riferimento

Answer 3

Sì, variabili mutabili e mentre i loop sono di solito un buon segno che il tuo codice non è molto funzionale. Anche la serie di fibonacci, non inizia con 1,2 - inizia con 0,1 o 1,1 a seconda di chi chiedi.

Ecco come lo farei:

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

Answer 4

Altri post indicano come scrivere il ciclo while utilizzando le funzioni ricorsive. Questo è un altro modo utilizzando la libreria Seq 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 

per la spiegazione, si prega di ref solution 2 in F# for Project Euler Problems, in cui vengono risolti i primi 50 problemi di Eulero. Penso che ti interesseranno queste soluzioni.

Answer 5

Ecco una soluzione coda-ricorsiva infinita che usa le espressioni di sequenza. È abbastanza efficiente, produce il 100.000 ° termine in pochi secondi. L'operatore "yield" è come "yield return" di C# e "yield!" l'operatore può essere letto come "yield all", dove in C# si dovrebbe fare "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 

Questo approccio è simile al seguente in C# (che utilizza un po '(vero anello) al posto di ricorsione):

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

Answer 6

La grande soluzione di Scott Hanselman non riporta lo 0 con cui inizia la sequenza di Fibonacci.

Quindi ecco una piccola modifica alla sua soluzione per segnalare anche lo 0. Ho usato una piccola lista da 0 a 10 per visualizzare i primi 11 elementi della sequenza.

let nums=[0..10] 
let rec fib n = if n < 1 then 0 else if n < 2 then 1 else fib (n-2) + fib(n-1) 
let finres = List.map fib nums 
printfn "%A" finres 

Sono nuovo e incompetente in relazione a F # e ancora non del tutto comprendere appieno la necessità di esso. Ma ho trovato questo un test interessante.

Solo per divertimento: se trovato una formula di Binet che calcola il n-esimo numero di Fibonacci. Purtroppo sono necessarie alcune funzioni virgola mobile per ottenere il risultato intero indietro alla fine: [formula Fibonacci di Binet] [1]

http://i.stack.imgur.com/nMkxf.png

let fib2 n = (1.0/sqrt(5.0)) * ((((1.0 + sqrt(5.0)) /2.0)**n) - (((1.0 - sqrt(5.0)) /2.0)**n)) 
let fib2res = fib2 10.0 
System.Console.WriteLine(fib2res) 
let strLine = System.Console.ReadLine() 

Una traduzione rapido e sporco di f # sarebbe come mostrato sopra. Sono sicuro che altri possono migliorare in materia di stile ed efficienza. L'esempio calcola il decimo numero. Il risultato sarà più 55.

Answer 7

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

Answer 8

Un modo codata'ish:

let rec fib = seq { 
    yield! seq {0..1} 
    yield! Seq.map (fun(a,b)->a+b) <| Seq.zip fib (Seq.skip 1 fib) 
} 
let a = fib |> Seq.take 10 |> Seq.toList 

Answer 9

Uno con una matrice:

let fibonacci n = [|1..n|] |> Array.fold (fun (a,b) _ -> b, a + b) (0,1) |> fst 

Answer 10

Questa funzione "fib" restituirà un elenco di Fibonacci numeri non superiori a 500

let rec fib a b = 
    let current = a + b 
    match current with 
    | _ when current >= 500 -> [] 
    | _ -> current :: fib b current 

let testFib = fib 1 2;;