В Haskell, как я могу генерировать числа Фибоначчи на основе свойства, что n-е число Фибоначчи равно числу (n-2) -го числа Фибоначчи плюс (n-1) -й номер Фибоначчи?
Я видел это:
fibs :: [Integer]
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
Я действительно не понимаю этого или как он создает бесконечный список вместо одного, содержащего 3 элемента.
Как я могу написать код хекеля, который работает, вычисляя фактическое определение, а не делая что-то действительно странное с функциями списка?
Здесь другая и более простая функция, которая вычисляет 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, дает это!
fibo a b = a:fibo b (a+b)
теперь просто возьмите n элементов из фибо, начиная с 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 2). Это потому, что тот, который вы указали, учитывает, что вычисления fib n и fib (n-1) (которые необходимы для его вычисления) разделяют зависимость fib (n-2) и что он может быть вычислен один раз для того, чтобы сэкономить время. O (N 2) для N дополнений чисел O (N) цифр.
Существует несколько различных алгоритмов Haskell для последовательности Фибоначчи здесь. "Наивная" реализация выглядит так, как вы.
fibs :: [Integer]
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
сначала, с помощью fibs и tail fibs, мы можем получить третий элемент:
fibs : [1, 1, ?
tail fibs : [1, ?
zipWith (+) fibs (tail fibs): [2, ?
Теперь мы знаем, что третье - это 2, мы можем получить четвертое:
fibs : [1, 1, 2, ?
tail fibs : [1, 2, ?
zipWith (+) fibs (tail fibs): [2, 3, ?
теперь пятый:
fibs : [1, 1, 2, 3, ?
tail fibs : [1, 2, 3, ?
zipWith (+) fibs (tail fibs): [2, 3, 5, ?
и так далее..
Леничный способ генерации бесконечных рядов Фибоначчи легко достигается посредством unfoldr следующим образом:
fibs :: [Integer]
fibs = unfoldr (\(f,s) -> Just (f,(s,f+s))) (0,1)
Определение 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) I.e. пусть не удерживает всю фибоначчи от 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]
LOL, мне нравится совпадение шаблонов Haskell, но оно бесполезно в стандартных функциях Фибоначчи. Стандартный список построен справа. Чтобы использовать сопоставление образцов и минус, список должен быть построен слева. Ну, одно утешение, по крайней мере, это очень быстро. ~ O (n), должно быть. Вспомогательная функция необходима для обращения к бесконечному списку (вещи, которые вы можете делать только в Haskell, радость), и эта функция выводит каждый последующий список прогона, поэтому "last" также используется в конвейере вспомогательной функции.
f (x:y:xs) = (x+y):(x:(y:xs))
Помощник
fib n = reverse . last . take n $ iterate f [1,0]
Это версия списка, и, я думаю, она объясняет, как создается список, который является целью. Я хочу сделать кортеж версии.
Редактировать 3/15/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. Понимание кортежа было вторым самым быстрым для fib 5000 в 13.58 секунд.