Créer une liste infinie avec les nombres de Fibonacci

Question

Je fais mon prochain devoir =) Ma tâche est de créer une liste infinie avec des nombres de fibonacci [0,1,1,2,3,5,8 ]. Je peux utiliser n'importe quelle fonction de Prelude.

J'ai essayé :

fibs2 :: [Integer]
fibs2 = reverse $ foldr f [1,0] [0..]
  where 
        f _ (x:y:xs) = (x+y):x:y:xs

Cette fonction ne fonctionne qu'avec des listes finies comme [0..100]. avec une liste infinie cela donne :

*** Exception: stack overflow

Qu'est-ce que j'ai fait de mal ? Comment faire fonctionner la fonction "paresseux" ?

UPDATE mon deuxième essai :

fibs4 = 0:[ b | (a, b) <- scanl (\(x,y) _ -> (y,x + y)) (0,1) [0..] ]

ça marche bien. :) c'est normal ou étrange ?

Answer 1

foldr (avec une fonction de combinaison stricte) déconstruit une liste d'arguments jusqu'à sa fin, puis la recombine à l'aide de la fonction de combinaison fournie par l'utilisateur. f :

foldr f z [a,b,c,...,y] = f a (f b (f c (.....(f y z).....)))

dans votre cas,

fibs2 = reverse $ foldr (\_ (x:y:xs) -> (x+y):x:y:xs) [1,0] [0..]

foldr ici ne produit jamais aucun résultat. Mais ce n'est pas faute d'avoir essayé : il travaille très dur en récurant la liste infinie à la recherche de sa fin, car sa fonction de combinaison est la suivante strict (il correspond au reste de foldr avec (x:y:xs) avant de construire son propre résultat).

Foldr avec une fonction de combinaison stricte exprime la récursion, et la récursion doit avoir son cas de base, pour s'arrêter. Ce que vous aviez en tête est le suivant :

fibs2 = reverse $ snd $ until (null.fst) 
         (\(_t:ts, x:y:xs) -> (ts, (x+y):x:y:xs)) ([0..],[1,0])

qui est manifestement non terminale. ts exprime simplement les moments de passage du temps. Nous pouvons essayer de voir toute l'histoire de son exécution, en la réécrivant en tant que

fibs2 = reverse $ snd $ last $ iterate
         (\(_t:ts, x:y:xs) -> (ts, (x+y):x:y:xs)) ([0..],[1,0])

Bien sûr, il n'y a pas de dernier élément dans la liste infinie. Mais nous pouvons au moins voir tous les résultats intermédiaires maintenant :

> mapM_ (print.reverse.snd) $ take 11 $ iterate 
          (\(_:ts, x:y:xs) -> (ts, (x+y):x:y:xs)) ([0..],[1,0])
[0,1]
[0,1,1]
[0,1,1,2]
[0,1,1,2,3]
[0,1,1,2,3,5]
[0,1,1,2,3,5,8]
[0,1,1,2,3,5,8,13]
[0,1,1,2,3,5,8,13,21]
[0,1,1,2,3,5,8,13,21,34]
[0,1,1,2,3,5,8,13,21,34,55]
[0,1,1,2,3,5,8,13,21,34,55,89]

Ainsi, au lieu d'attendre que la toute dernière liste soit construite (ce qui sera jamais ) et puis en l'inversant, pourquoi ne pas produire ses éléments au fur et à mesure ? Tout est déjà là, de toute façon. Et le dernier élément de chaque résultat intermédiaire, inversé - n'est-il pas simplement son premier élément ?

> take 11 $ map (head.snd) $ iterate 
          (\(_:ts, x:y:xs) -> (ts, (x+y):x:y:xs)) ([0..],[1,0])
[1,1,2,3,5,8,13,21,34,55,89]

Neat, huh. Alors, avons-nous vraiment besoin de notre compteur de temps explicite ? Devons-nous faire glisser toute la queue du résultat intermédiaire précédent, ou avons-nous seulement besoin de ses deux premiers éléments ?

fibs = map (head.tail) $ iterate (\[x,y] -> [x+y,x]) [1,0]

L'utilisation de tuples pour les listes de longueur constante sera un peu plus propre. Vous voyez donc que nous sommes arrivés ici à l'une des définitions canoniques,

fibs = g (1,0)  where  g (a,b) = b : g (a+b,a)

(voir aussi Quelle est la différence entre la récursion et la corecursion ? ).

---

votre "deuxième essai",

fibs4 = 0:[ b | (a, b) <- scanl (\(x,y) _ -> (y,x + y)) (0,1) [0..] ]

est en fait très proche de ce qui précède, comme vous pouvez le voir. scanl sur la liste de comptage du temps est juste équivalent à iterate . C'est donc équivalent à

fibs4a = [a | (a,b) <- iterate (\(a,b) -> (b, a+b)) (0,1)]

que nous avons vu dans la dérivation ci-dessus comme une map variante, avec des tuples au lieu de listes.

Answer 2

Yep, tu ne peux pas inverser un tableau infini.

Jetez un coup d'oeil à ça :

0,1,1,2,3,5,8,13,21,...
  0,1,1,2,3,5,8, 13...   +
----------------------
0,1,2,3,5,8,13,21,...

Comme vous pouvez le voir dans ma tentative de montrer la relation comment la séquence de Fibonacci peut être générée en s'utilisant elle-même, c'est assez facile ! Vous devez zipWith fibonacci avec ses queues en utilisant la fonction d'addition !

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

Pour un peu plus de détails, voici une extension de ce qui précède.

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
fibs = 0 : 1 : zipWith (+) 0:1:? 1:?
fibs = 0 : 1 : (0+1) : zipWith (+) 1:? ?
fibs = 0 : 1 : 1 : zipWith (+) 1:1:? 1:?
fibs = 0 : 1 : 1 : 2 : zipWith (+) 1:2:? 2:?
fibs = 0 : 1 : 1 : 2 : 3 : zipWith (+) 2:3:? 3:?

ad infinitum... Le site ? représente un thunk un morceau de calcul en Haskell qui n'a pas encore été évalué.