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

Question

В Хаскеле, как я могу сгенерировать числа Фибоначчи, основываясь на том, что n-е число Фибоначчи равно (n-2) -ому числу Фибоначчи плюс (n-1) -ому числу Фибоначчи?

Я видел это:

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

Я не очень понимаю это, или как он создает бесконечный список вместо одного, содержащего 3 элемента.

Как бы я написал код на haskell, который работает, вычисляя фактическое определение, а не делая что-то действительно странное с функциями списка?

Answer 1

Вот другая и более простая функция, которая вычисляет 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

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

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

Answer 2

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

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

теперь просто возьмите n предметов из фибо, начиная с 0,1

take 10 (fibo 0 1)

Answer 3

Чтобы расширить ответ ДТБ:

Существует важное отличие между "простым" решением:

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) цифр.

Answer 4

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

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

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, ?

и так далее..

Answer 5

Здесь есть ряд различных алгоритмов Хаскеля для последовательности Фибоначчи. "Наивная" реализация выглядит так, как вам нужно.

Answer 6

Определение Фибоначчи (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

Answer 7

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

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]

Answer 8

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

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

Answer 9

Эта реализация вычисляет 100000-е число Фибоначчи почти мгновенно:

fib = fastFib 1 1

fastFib _ _ 0 = 0
fastFib _ _ 1 = 1
fastFib _ _ 2 = 1
fastFib a b 3 = a + b
fastFib a b c = fastFib (a + b) a (c - 1)

Answer 10

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

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

Answer 11

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

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)

Answer 12

Я попытался переопределить это в python3. Цель состояла в том, чтобы получить аналогичный алгоритм в Python, который, очевидно, тот же самый, но не имитировать все аспекты Haskell.

Я придумал следующий код.

fibs.py:

      # python version of Haskell's code
#    fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

from operator import add

fibsList = [1, 1]  # growing

def fibs(n):
  if n >= len(fibsList):                # lazy evaluation
    x=zipWith(n-2,add,fibs,tail(fibs))  # or: ...,fibs,tailfibs)
    fibsList.append(x)
  return fibsList[n]

def zipWith(n,op,list1,list2):
  return op(list1(n),list2(n))

def tail(list):                         # or: def tailfibs(n):
  return lambda n : list(n + 1)         #       return fibs(n+1)

# test
print (fibs(10))
print (*fibsList)

Запуск выведет

      $ python fibs.py
89
1 1 2 3 5 8 13 21 34 55 89

Это будет делать то же самое, что и код Haskell, но это пошаговая версия, в которую вы можете добавить ведение журнала.

Answer 13

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]

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

Изменить 15/03/2018

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

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 секунд.