Générer des nombres de Fibonacci en Haskell?

Question

En Haskell, comment puis-je générer des nombres de Fibonacci basé sur la propriété que le n-ième nombre de Fibonacci est égal à (n-2)ème nombre de Fibonacci en plus de la (n-1)ième nombre de Fibonacci?

J'ai vu ceci:

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

Je ne sais vraiment pas qui, ni comment, il se produit une liste infinie au lieu d'un seul contenant 3 éléments.

Comment pourrais-je écrire du code haskell qui fonctionne par le calcul de la définition réelle et non pas par faire quelque chose de vraiment bizarre avec les fonctions de liste?

Merci.

Answer 1

Voici une simple fonction qui calcule le n-ième nombre de Fibonacci:

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

La fonction dans votre question fonctionne comme ceci:

Supposons que vous avez déjà eu une liste infinie des nombres de Fibonacci:

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

L' tail de cette liste est

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

zipWith combine deux listes de l'élément par élément à l'aide de l'opérateur:

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

Si la liste infinie des nombres de Fibonacci peut être calculé en ajoutant les éléments 1 et 1 à la suite de la compression de la liste infinie des nombres de Fibonacci avec la queue de la liste infinie des nombres de Fibonacci à l'aide de l' + de l'opérateur.

Maintenant, pour obtenir le n-ième nombre de Fibonacci, juste obtenir le n-ième élément de la liste infinie des nombres de Fibonacci:

fib n = fibs !! n

La beauté de Haskell, c'est qu'il ne parvient pas à calculer n'importe quel élément de la liste de nombres de Fibonacci jusqu'à son besoin.

J'ai fait votre tête exploser? :)

Answer 2

Selon la définition, chaque élément de la série fibonacci est la somme des deux termes précédents. mettre cette définition dans haskell paresseux vous donne ça!

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

maintenant, il suffit de prendre n éléments de fibo à partir de 0,1

 take 10 (fibo 0 1)
 

Answer 3

Pour développer sur dtb réponse:

Il existe une différence importante entre la "simple" solution:

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

Et celui que vous avez spécifié:

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

La solution la plus simple prend O(1.618^NN) le temps de calculer le n-ième élément, tandis que celui que vous avez spécifié prend O(N²). C'est parce que celui que vous avez spécifié ne prend en compte que le calcul de fib n et fib (n-1) (ce qui est nécessaire pour le calculer) partager la dépendance de l' fib (n-2), et qu'il peut être calculé une fois pour les deux pour gagner du temps. O(N²) pour N additions de nombres de O(N) chiffres.

Answer 4

Il existe un certain nombre d'algorithmes Haskell différents pour la séquence de Fibonacci ici . L'implémentation "naïve" ressemble à ce que vous recherchez.

Answer 5

en utilisant itérer

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

en utilisant

 take 10 fibonaci

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