Генерация ряда Fibonacci в F#
Я только начинаю узнавать, что F# с помощью VS2010 и ниже является моей первой попыткой генерации ряда 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#, это, кажется, не чувствует, чтобы быть правильным способом сделать программу. Я корректен в этом чувстве?
5 ответов
Прежде всего, вы используете 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)
Да, изменяемые переменные и циклы 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]*)
В других сообщениях рассказывается, как написать цикл while с использованием рекурсивных функций. Это еще один способ использования библиотеки Seq в 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
для объяснения, пожалуйста, обратитесь к решение 2 в F # для задач проекта Эйлера , где первый Решено 50 задач Эйлера. Думаю, вам будут интересны эти решения.
Вот решение с бесконечной хвостовой рекурсией, использующее выражения последовательности. Это довольно эффективно, производя 100000-й член всего за несколько секунд. Оператор yield подобен оператору yield return в C # и оператору yield! Оператор может быть прочитан как «yield all», тогда как в C # вам нужно будет выполнить «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
Этот подход аналогичен следующему в C # (который использует цикл while (true) вместо рекурсии ):
Нахождение последовательности Фибоначчи в C #. [Упражнение по проекту Эйлера]
Вот хорошая статья гуру .Net Скотта Хансельмана о создании рядов Фибоначчи в F #
let rec fib n = if n < 2 then 1 else fib (n-2) + fib(n-1)
http://www.hanselman.com/blog/TheWeeklySourceCode13FibonacciEdition .aspx
Он также сравнивается с другими языками как ссылка