F# фибоначчи!

Я писал про .NET для Линукс - продолжаю забавляться с ним. В его составе, кроме C#, идёт также компилятор F#. Несмотря на хулиганское название, это весьма серьёзный функциональный язык программирования. Давайте попробуем сваять на нём функцию вычисления чисел Фибоначчи.

В языке F# есть поддержка целых чисел неограниченного размера, чем мы и воспользуемся. Для литералов типа bigint надо указывать суффикс I.

Для вычислений задействуем хвостовую рекурсию, как и положено в порядочном функциональном языке.

let fibonacci n =

    let rec fibrec n f0 f1 =
        match n with
        | 0 -> f0
        | 1 -> f1
        | _ -> fibrec (n - 1) f1 (f0 + f1)

    fibrec n 0I 1I

Запускаем (можно онлайн на https://repl.it/languages/fsharp).

printfn "%A" (fibonacci 10)

55

Неплохо для начала, двинем дальше.

printfn "%A" (fibonacci 100)

354224848179261915075

Таки оно работает! Поддадим жару.

( +2 )

Ну что тут поделаешь. Я проверял на миллионе - вычисляет за 25 секунд на моём лаптопе.