Числа Фиббоначи

Рассмотрим лобовое решение с бинарной рекурсией:

fib :: Int -> Int fib 1 = 1 fib 2 = 1 fib n = fib (n-1) + fib (n-2)

тогда сам список чисел Фиббоначи может быть задан следующим образом:

fibset = [ fib n | n <- [1..] ]

Однако данный способ вычисления является хоть и простым, но крайне затратным, так как вынужден делать бинарное дерево ветвлений вычислений при рекурсивном спуске. При этом хотя все вычисления одинаковые, но они делаются независимо и вынуждены занимать всю доступную память. Таким образом, на некоторых компьютерах вычислить даже 40-й элементы последовательности является проблематичным, а 45-й, тем более 50-й вычислить нереально практически на всех доступных персональных компьютерах.

Согласно сайту cubbi.com: fibonacci numbers in haskell возможно существенно улучшить даже бинарную рекурсию мемоизацией (кэшированием) промежуточных результатов:

import Data.MemoTrie -- Naive binary recursion: F(n) = F(n-1) + F(n-2) with -- using memotrie from http://haskell.org/haskellwiki/MemoTrie fib :: Int -> Integer fib 0 = 0 fib 1 = 1 fib n = mfib (n-2) + mfib (n-1) where mfib = memo fib

Более интересно превращение в линейную рекурсию с аккумулятором:

fib a b 0 = a fib a b (c+1) = fib (a+b) a c

запуск осуществляется так:

fib 0 1 n

Другой вариант из сайта The Fibonacci sequence с аккумулятором и хвостовой рекурсией (используя расширения языка):

{-# LANGUAGE BangPatterns #-} fib n = go n (0,1) where go !n (!a, !b) | n==0 = a | otherwise = go (n-1) (b, a+b)

Вот императивный вариант с монадой состояния (оттуда же):

import Control.Monad.State fib n = flip evalState (0,1) $ do forM [0..(n-1)] $ \_ -> do (a,b) <- get put (b,a+b) (a,b) <- get return a

А статья Мягкое введение в Haskell-1 предлагает решение в виде циклического бесконечного списка:

fib = 1 : 1 : [ a+b | (a,b) <- zip fib (tail fib) ]