Фибоначчи на Haskell, во имя бобра!

Последнее время меня дико прет от функциональных языков программирования. Началось с Visual Prolog, который как известно поддерживает несколько парадигм программирования - функциональную, логическую и процедурную. Он очень удобен для декларативного описания задач и решения их "в лоб" за счет встроенного в язык перебора с возвратами (backtracking). Но сегодня не о нем, итак Haskell.

Haskell - кристально чистый функциональный язык программирования. Лямбда-функции (lambda), сопоставление с образцом (pattern matching), ленивые вычисления (lazy evaluation), каррирование (currying), длинная арифметика (arbitrary-precision integers), строгая, статическая типизация с автоматическим выводом типов - вот лишь несколько самых броских фишек языка.

Лаконичность синтаксиса программ на Haskell просто потрясающая!

К примеру данный код производит вычисление N-го числа последовательности Фибоначчи:

fib 0 = 1
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

Шикарно, не правда ли?

Время работы простого рекурсивного алгоритма (согласно SICP)

Потребление памяти простого рекурсивного алгоритма

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

Простая итеративная версия данного алгоритма: 

fib_iter n = f n 0 1 0
    where f n k a b 
        | n == k    = a
        | otherwise = f n (k + 1) (a + b) a

Время работы итеративной версии

Потребление памяти итеративной версии алгоритма

Выглядит она конечно менее очевидно, но если заметить, что в a и b на каждом шаге хранится текущее и следующее число последовательности, а завершается хвостовая рекурсия когда счетчик k дойдет до искомого n, то все становится понятно.

Ну и на закуску, хитрая итеративная версия вычисления чисел Фибоначчи (подробнее в упражнении 1.19 из SICP):

fib_fast_iter n = f 1 0 0 1 n
    where f a b p q n
        | n == 0         = b
        | n `mod` 2 == 0 = f a b (q^2 + p^2) (q^2 + 2 * p * q) (n `div` 2)
        | otherwise      = f (b * q + a * q + a * p) (b * p + a * q) p q (n - 1)

Время работы быстрой итеративной версии

Потребление памяти быстрой итеративной версии алгоритма 

В следующий раз расскажу, как просто тестировать код на Haskell.