Генерация чисел Фибоначчи в Haskell?

Вот другая и более простая функция, которая вычисляет n-е число Фибоначчи:

fib :: Integer -> Integer
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

Реализация, о которой вы говорите, передает некоторые наблюдения о том, как значения в Фибоначчи соотносятся друг с другом (и как Haskell может определять структуры данных в терминах самих себя, фактически создавая бесконечные структуры данных)

Функция в вашем вопросе работает так:

Предположим, у вас уже есть бесконечный список чисел Фибоначчи:

   [ 1, 1, 2, 3, 5,  8, 13, .... ]

tail в этом списке

   [ 1, 2, 3, 5, 8, 13, 21, .... ]

zipWith объединяет два списка поэлементно с использованием данного оператора:

   [ 1, 1, 2, 3,  5,  8, 13, .... ]
+  [ 1, 2, 3, 5,  8, 13, 21, .... ]
=  [ 2, 3, 5, 8, 13, 21, 34, .... ]

Таким образом, бесконечный список чисел Фибоначчи может быть вычислен путем добавления элементов 1 и 1 к результату сжатия бесконечного списка чисел Фибоначчи с хвостом бесконечного списка чисел Фибоначчи с использованием оператора +.

Теперь, чтобы получить n-е число Фибоначчи, достаточно получить n-й элемент бесконечного списка чисел Фибоначчи:

fib n = fibs !! n

Прелесть Haskell в том, что он не вычисляет ни один элемент списка чисел Фибоначчи до тех пор, пока он не понадобится.

Я заставил твою голову взорваться? :)

согласно определению, каждый элемент ряда Фибоначчи является суммой двух предыдущих членов. вставив это определение в ленивый haskell, вы получите это!

fibo a b = a:fibo b (a+b)

теперь просто возьмите n элементов из fibo, начиная с 0,1

take 10 (fibo 0 1)

Чтобы расширить ответ dtb:

Между «простым» решением есть важное отличие:

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

И тот, который вы указали:

fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

Простое решение занимает O (1.618 ^N N) времени. для вычисления N-го элемента, в то время как тот, который вы указали, принимает O (N ²). Это потому, что указанное вами значение принимает во внимание, что вычисления fib n и fib (n-1) (которые необходимы для его вычисления) разделяют зависимость fib (n-2), и что его можно вычислить один раз для обоих, чтобы сэкономить время. O (N ²) - для N сложений чисел по O (N) цифр.

здесь существует ряд различных алгоритмов Haskell для последовательности Фибоначчи. «Наивная» реализация похожа на то, что вам нужно.

fibs :: [Integer]
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

сначала с fibs и tail fibs мы можем получить 3-й элемент:

fibs                        : [1, 1, ?
tail fibs                   : [1, ?
zipWith (+) fibs (tail fibs): [2, ?

теперь, когда мы знаем, что 3-е равно 2, мы можем получить 4-е:

fibs                        : [1, 1, 2, ?
tail fibs                   : [1, 2, ?
zipWith (+) fibs (tail fibs): [2, 3, ?

теперь 5-е:

fibs                        : [1, 1, 2, 3, ?
tail fibs                   : [1, 2, 3, ?
zipWith (+) fibs (tail fibs): [2, 3, 5, ?

и так далее ..

Определение fibonaci (n):

fibonacci (n) = fibonacci (n-1) + fibonacci (n-2)

Наивная реализация на Haskell

fibonacci :: Integer -> Integer
fibonacci 0 = 1
fibonacci 1 = 1
fibonacci x = fibonacci (x-1) + fibonacci (x-2)

Все формулы можно проследить до этого определения, некоторые из которых работают очень быстро, а некоторые очень медленно. В приведенной выше реализации O (n) = 2 ^ n

В духе вашего вопроса, позвольте мне убрать использование списков и дать вам то, что работает в O (n) Т.е. давайте не будем держать все фибоначчи от 0 до n в списке.

Если у нас есть тройка (кортеж из трех членов), который выглядит так:

(n, fibonacci[n-1], fibonacci[n])

Помня первоначальное определение, мы можем вычислить следующую тройку из последней тройки:

(n+1, fibonacci[n], fibonacci[n-1] + fibonacci[n]) = (n+1, fibonacci[n], fibonacci[n+1])

И следующая тройка из последней тройки: (n+2, fibonacci[n+1], fibonacci[n] + fibonacci[n+1]) = (n+1, fibonacci[n+1], fibonacci[n+2])

И так далее ...

n = 0 => (0,0,1) 
n = 1 => (1,1,1) - calculated from the previous triple
n = 2 => (2,1,2) - calculated from the previous triple
n = 3 => (3,2,3) - calculated from the previous triple
n = 4 => (4,3,5) - calculated from the previous triple
n = 5 => (5,5,8) - calculated from the previous triple

Давайте реализуем это в Haskell и будем использовать понятные имена переменных:

nextTripleIfCurrentNIsLessThanN :: (Int, Integer, Integer) -> Int -> (Int, Integer, Integer)
nextTripleIfCurrentNIsLessThanN (currentN, x, y) n = if currentN < n
then nextTripleIfCurrentNIsLessThanN (currentN + 1, y, x + y) n
else (currentN, x, y)

thirdElementOfTriple :: (x,y,z) -> z
thirdElementOfTriple (x,y,z) = z

fibonacci :: Int -> Integer
fibonacci n = thirdElementOfTriple (nextTripleIfCurrentNIsLessThanN (0,0,1) n)

Это будет работать в O (n) [Это умеренно квадратично, что проявляется в больших количествах. Причина в том, что добавление больших чисел обходится дороже, чем добавление маленьких. Но это отдельное обсуждение модели вычислений.]

fibonacci 0
1
fibonacci 1
1
fibonacci 2
2
fibonacci 3
3
fibonacci 4
5
fibonacci 5
8
fibonacci 5000
6276302800488957086035253108349684055478528702736457439025824448927937256811663264475883711527806250329984690249846819800648580083040107584710332687596562185073640422286799239932615797105974710857095487342820351307477141875012176874307156016229965832589137779724973854362777629878229505500260477136108363709090010421536915488632339240756987974122598603591920306874926755600361865354330444681915154695741851960071089944015319300128574107662757054790648152751366475529121877212785489665101733755898580317984402963873738187000120737824193162011399200547424034440836239726275765901190914513013217132050988064832024783370583789324109052449717186857327239783000020791777804503930439875068662687670678802914269784817022567088069496231111407908953313902398529655056082228598715882365779469902465675715699187225655878240668599547496218159297881601061923195562143932693324644219266564617042934227893371179832389642895285401263875342640468017378925921483580111278055044254198382265567395946431803304304326865077742925818757370691726168228648841319231470626

используя итерацию

fibonaci = map fst (iterate f (0,1)) where f (x,y) = (y,x+y)

с использованием

take 10 fibonaci

[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377]

Ленивый способ создания бесконечных рядов Фибоначчи может быть легко достигнут unfoldr следующим образом;

fibs :: [Integer]
fibs = unfoldr (\(f,s) -> Just (f,(s,f+s))) (0,1)

LOL, я люблю сопоставление с образцом в Haskell, но оно бесполезно в стандартных функциях Фибоначчи. Стандартный список строится справа. Чтобы использовать сопоставление с образцом и минусы, список должен быть построен слева. Что ж, одно утешение, по крайней мере, в том, что это действительно быстро. ~ O (n), так и должно быть. Вспомогательная функция необходима для переворота бесконечного списка (вещи, которые вы можете делать только в Haskell, радость), и эта функция выводит каждый последующий список выполнения, поэтому «последний» также используется в конвейере вспомогательных функций.

f (x:y:xs) = (x+y):(x:(y:xs))

Помощник

fib n = reverse . last . take n $ iterate f [1,0]

Это версия со списком, и, я думаю, она объясняет, как создается список, что и является целью. Я хочу сделать кортежную версию.

Изменить 15.03.2018

Во-первых, Уилл Несс просветил меня, зная, что весь список, генерируемый на каждой итерации, не нужен, и что нужны только два последних значения, а значения для списка результатов являются первыми значениями каждого сгенерированного списка или пары. Это было так смешно. После того, как Уилл сказал мне, что значения для списка были первыми значениями списков, я запустил его и увидел значения 0,1,1,2,3,5,8,13 в качестве каждого заголовка каждого списка, я сказал WTF, Изменил ли мой код на моем ПК? Ценности были, но как !? Через некоторое время я понял, что они были там все время, но просто не видел их. фу. Версия функции и вспомогательной функции Уилла:

f = (\(x:y:xs) -> (x+y):x:xs) -- notice, no y: put back only x+y & x

и его вспомогательная функция перезаписывает

fib n = map head . take n $iterate f [0,1]

Я тоже думаю, что теперь их можно комбинировать:

fib n = take n . map head $ iterate (\(x:y:xs) -> (x+y):x:xs) [0,1]

Кроме того, функция может быть и с кортежами.

fib n = take n . map fst $ iterate (\(a,b) -> (b,a+b)) (0,1)

Другая форма, форма понимания списка, также может быть написана для всех:

fib n = take n [ fst t | t <- iterate (\(a,b) -> (b,a+b)) (0,1)]

Все они итеративны и надежны. Самая быстрая - карта со списками за 12,23 секунды для fib 5000. На втором месте по скорости распознавания кортежей - 13,58 секунды для fib 5000.

Вставьте код, ваше определение

fib :: Int -> Integer
fib 0 = 1
fib 1 = 1
fib n = fib (n-1) + fib (n-2)
  -- i.e.
  -- fib (n+2) = fib (n+1) + fib n

Int -> a ~= [a] потому что

from f = map f [0..]     -- from :: (Int -> a) -> [a]
to = (!!)                -- to :: [a] -> (Int -> a)

Таким образом

fibs :: [Integer]
fibs = from fib 

fibs !! 0 = 1
fibs !! 1 = 1
fibs !! (n+2)    = fibs !! (n+1)     +  fibs !! n
-- or,
drop 2 fibs !! n = drop 1 fibs !! n  +  fibs !! n
                 = zipWith (+) (tail fibs) fibs !! n
-- i.e.
take 2 fibs = [1,1]
drop 2 fibs = zipWith (+) (tail fibs) fibs
-- hence, 
fibs = take 2 fibs ++ drop 2 fibs
     = 1 : 1 : zipWith (+) (tail fibs) fibs

Или как a, b = (0,1) : (b, a+b):

fibs :: [Integer]
fibs = a
  where
  (a,b) = unzip $ (0,1) : zip b (zipWith (+) a b)

Я делал домашнее задание6 по CIS194 и обнаружил, что вы можете писать так. Для вычисления первых n элементов требуется всего O (n) операций сложения.

fibs2 :: [Integer]
fibs2 = [0, 1] ++ [fibs2 !! (n-1) + fibs2 !! (n-2) | n <- [2..]]