Comment cette fonction fibonacci est-elle mémorisée?

114

Par quel mécanisme cette fonction fibonacci est-elle mémorisée?

fib = (map fib' [0..] !!)                 
     where fib' 1 = 1                                                        
           fib' 2 = 1                                                        
           fib' n = fib (n-2) + fib (n-1)                    

Et sur une note connexe, pourquoi cette version n'est-elle pas?

fib n = (map fib' [0..] !! n)                                               
     where fib' 1 = 1                                                        
           fib' 2 = 1                                                        
           fib' n = fib (n-2) + fib (n-1)                    
bjornars
la source
13
Légèrement sans rapport, fib 0ne se termine pas: vous voulez probablement que les cas de base fib'soient fib' 0 = 0et fib' 1 = 1.
huon
1
Notez que la première version pourrait être plus concise: fibs = 1:1:zipWith (+) fibs (tail fibs)et fib = (fibs !!).
Bastian

Réponses:

95

Le mécanisme d'évaluation dans Haskell est par besoin : lorsqu'une valeur est nécessaire, elle est calculée et maintenue prête au cas où elle serait à nouveau demandée. Si nous définissons une liste, xs=[0..]et demandons plus tard son 100e élément, xs!!99le 100e emplacement de la liste est "étoffé", tenant le numéro 99maintenant, prêt pour le prochain accès.

C'est ce que cette astuce, "passant par une liste", exploite. Dans la définition normale de Fibonacci à double récurrence,, fib n = fib (n-1) + fib (n-2)la fonction elle-même est appelée deux fois par le haut, provoquant l'explosion exponentielle. Mais avec cette astuce, nous établissons une liste pour les résultats intermédiaires, et passons "par la liste":

fib n = (xs!!(n-1)) + (xs!!(n-2)) where xs = 0:1:map fib [2..]

L'astuce consiste à créer cette liste et à empêcher cette liste de disparaître (par le biais d'un garbage collection) entre les appels à fib. Le moyen le plus simple d'y parvenir est de nommer cette liste. "Si vous le nommez, il restera."


Votre première version définit une constante monomorphe et la seconde définit une fonction polymorphe. Une fonction polymorphe ne peut pas utiliser la même liste interne pour différents types qu'elle pourrait avoir besoin de servir, donc pas de partage , c'est-à-dire pas de mémorisation.

Avec la première version, le compilateur est généreux avec nous, en supprimant cette sous-expression constante ( map fib' [0..]) et en en faisant une entité partageable distincte, mais il n'est pas obligé de le faire. et il y a en fait des cas où nous ne voulons pas qu'il le fasse pour nous automatiquement.

( modifier:) Considérez ces réécritures:

fib1 = f                     fib2 n = f n                 fib3 n = f n          
 where                        where                        where                
  f i = xs !! i                f i = xs !! i                f i = xs !! i       
  xs = map fib' [0..]          xs = map fib' [0..]          xs = map fib' [0..] 
  fib' 1 = 1                   fib' 1 = 1                   fib' 1 = 1          
  fib' 2 = 1                   fib' 2 = 1                   fib' 2 = 1          
  fib' i=fib1(i-2)+fib1(i-1)   fib' i=fib2(i-2)+fib2(i-1)   fib' i=f(i-2)+f(i-1)

La vraie histoire semble donc concerner les définitions de portée imbriquées. Il n'y a pas de portée externe avec la 1ère définition, et la 3ème prend soin de ne pas appeler la portée externe fib3, mais du même niveau f.

Chaque nouvelle invocation de fib2semble créer à nouveau ses définitions imbriquées parce que n'importe laquelle d'entre elles pourrait (en théorie) être définie différemment en fonction de la valeur de n(merci à Vitus et Tikhon pour l'avoir souligné). Avec la première définition, il n'y a pas de quoi ndépendre, et avec la troisième il y a une dépendance, mais chaque appel séparé à des fib3appels dans flequel fait attention à n'appeler que des définitions de portée de même niveau, interne à cet appel spécifique de fib3, donc la même chose xsobtient réutilisé (c'est-à-dire partagé) pour cet appel de fib3.

Mais rien n'empêche le compilateur de reconnaître que les définitions internes dans l'une des versions ci-dessus sont en fait indépendantes de la nliaison externe , pour effectuer le levage lambda après tout, ce qui entraîne une mémorisation complète (sauf pour les définitions polymorphes). En fait, c'est exactement ce qui se passe avec les trois versions lorsqu'elles sont déclarées avec des types monomorphes et compilées avec l'option -O2. Avec les déclarations de type polymorphe, fib3présente un partage local et fib2aucun partage.

En fin de compte, en fonction du compilateur et des optimisations du compilateur utilisées, et de la façon dont vous le testez (chargement de fichiers dans GHCI, compilés ou non, avec -O2 ou non, ou autonome), et s'il obtient un type monomorphe ou polymorphe, le comportement pourrait changer complètement - s'il présente un partage local (par appel) (c'est-à-dire un temps linéaire sur chaque appel), une mémorisation (c'est-à-dire un temps linéaire au premier appel, et 0 heure sur les appels suivants avec le même argument ou un argument plus petit), ou pas de partage du tout ( temps exponentiel).

La réponse courte est, c'est une chose de compilateur. :)

Will Ness
la source
4
Juste pour corriger un petit détail: la deuxième version ne reçoit aucun partage principalement parce que la fonction locale fib'est redéfinie pour tout net donc fib'dans fib 1fib'in fib 2, ce qui implique également que les listes sont différentes. Même si vous corrigez le type pour qu'il soit monomorphe, il présente toujours ce comportement.
Vitus
1
whereles clauses introduisent le partage comme des letexpressions, mais elles ont tendance à cacher des problèmes comme celui-ci. En le réécrivant un peu plus explicitement, vous obtenez ceci: hpaste.org/71406
Vitus
1
Un autre point intéressant à propos de votre réécriture: si vous leur donnez un type monomorphe (ie Int -> Integer), alors fib2s'exécute en temps exponentiel, fib1et les fib3deux s'exécutent en temps linéaire mais fib1est également mémorisé - encore une fois parce que fib3les définitions locales sont redéfinies pour chaque n.
Vitus
1
@misterbee Mais en effet, ce serait bien d'avoir une sorte d'assurance du compilateur; une sorte de contrôle sur la résidence en mémoire d'une entité spécifique. Parfois, nous voulons le partage, parfois nous voulons l'empêcher. J'imagine / j'espère que cela devrait être possible ...
Will Ness
1
@ElizaBrandt ce que je voulais dire, c'est que parfois nous voulons recalculer quelque chose de lourd pour qu'il ne soit pas conservé pour nous en mémoire - c'est-à-dire que le coût du recalcul est inférieur au coût d'une énorme rétention de mémoire. un exemple est la création de PowerSet: dans pwr (x:xs) = pwr xs ++ map (x:) pwr xs ; pwr [] = [[]]nous voulons pwr xsêtre calculés indépendamment, deux fois, afin qu'ils puissent être ramassés à la volée au fur et à mesure qu'ils sont produits et consommés.
Will Ness
23

Je ne suis pas tout à fait certain, mais voici une supposition éclairée:

Le compilateur suppose que cela fib npourrait être différent sur un autre net aurait donc besoin de recalculer la liste à chaque fois. Les bits à l'intérieur de l' whereinstruction pourraient dépendre n, après tout. Autrement dit, dans ce cas, toute la liste des nombres est essentiellement une fonction de n.

La version sans n peut créer la liste une fois et l'envelopper dans une fonction. La liste ne peut pas dépendre de la valeur de npassée et cela est facile à vérifier. La liste est une constante qui est ensuite indexée dans. C'est, bien sûr, une constante qui est évaluée paresseusement, donc votre programme n'essaye pas d'obtenir la liste entière (infinie) immédiatement. Puisqu'il s'agit d'une constante, elle peut être partagée entre les appels de fonction.

Il est mémorisé du tout parce que l'appel récursif doit simplement rechercher une valeur dans une liste. Puisque la fibversion crée la liste une fois paresseusement, elle calcule juste assez pour obtenir la réponse sans faire de calcul redondant. Ici, «paresseux» signifie que chaque entrée de la liste est un thunk (une expression non évaluée). Lorsque vous n'évaluez thunk, il devient une valeur, donc l' accès à la prochaine fois ne se répète pas le calcul. Puisque la liste peut être partagée entre les appels, toutes les entrées précédentes sont déjà calculées au moment où vous avez besoin de la suivante.

C'est essentiellement une forme de programmation dynamique intelligente et peu coûteuse basée sur la sémantique paresseuse de GHC. Je pense que la norme spécifie seulement qu'elle doit être non stricte , donc un compilateur conforme pourrait potentiellement compiler ce code pour ne pas mémoriser. Cependant, dans la pratique, chaque compilateur raisonnable va être paresseux.

Pour plus d'informations sur les raisons pour lesquelles le deuxième cas fonctionne, lisez Comprendre une liste définie de manière récursive (fibs en termes de zipWith) .

Tikhon Jelvis
la source
vouliez-vous dire " fib' npourrait être différent sur un différent n" peut-être?
Will Ness
Je pense que je n'ai pas été très clair: ce que je voulais dire, c'est que tout à l'intérieur fib, y compris fib', pouvait être différent sur chaque différent n. Je pense que l'exemple original est un peu déroutant car cela fib'dépend aussi de lui-même de l' nombre à l'autre n.
Tikhon Jelvis
20

Premièrement, avec ghc-7.4.2, compilé avec -O2, la version non mémorisée n'est pas si mauvaise, la liste interne des numéros de Fibonacci est toujours mémorisée pour chaque appel de haut niveau à la fonction. Mais il n'est pas, et ne peut raisonnablement pas, être mémorisé entre différents appels de premier niveau. Cependant, pour l'autre version, la liste est partagée entre les appels.

Cela est dû à la restriction du monomorphisme.

Le premier est lié par une simple liaison de motif (seulement le nom, pas d'arguments), donc par la restriction de monomorphisme, il doit obtenir un type monomorphe. Le type inféré est

fib :: (Num n) => Int -> n

et une telle contrainte est définie par défaut (en l'absence de déclaration par défaut indiquant le contraire) à Integer, en fixant le type comme

fib :: Int -> Integer

Il n'y a donc qu'une seule liste (de type [Integer]) à mémoriser.

La seconde est définie avec un argument de fonction, elle reste donc polymorphe, et si les listes internes étaient mémorisées entre les appels, une liste devrait être mémorisée pour chaque type dans Num. Ce n'est pas pratique.

Compilez les deux versions avec la restriction de monomorphisme désactivée, ou avec des signatures de type identiques, et les deux présentent exactement le même comportement. (Ce n'était pas vrai pour les anciennes versions du compilateur, je ne sais pas quelle version l'a fait en premier.)

Daniel Fischer
la source
Pourquoi est-il impossible de mémoriser une liste pour chaque type? En principe, le GHC pourrait-il créer un dictionnaire (un peu comme pour appeler des fonctions contraintes de classe de type) pour contenir des listes partiellement calculées pour chaque type Num rencontré pendant l'exécution?
misterbee
1
@misterbee En principe, c'est possible, mais si le programme fait appel fib 1000000à beaucoup de types, cela consomme une tonne de mémoire. Pour éviter cela, il faudrait une heuristique qui répertorie à jeter hors du cache lorsqu'elle devient trop volumineuse. Et une telle stratégie de mémoisation s'appliquerait également à d'autres fonctions ou valeurs, vraisemblablement, de sorte que le compilateur devrait gérer un nombre potentiellement grand de choses à mémoriser pour potentiellement de nombreux types. Je pense qu'il serait possible d'implémenter une mémoisation polymorphe (partielle) avec une heuristique raisonnablement bonne, mais je doute que cela en vaille la peine.
Daniel Fischer
5

Vous n'avez pas besoin de la fonction de mémorisation pour Haskell. Seul le langage de programmation empirique a besoin de ces fonctions. Cependant, Haskel est lang et fonctionnel ...

Donc, voici un exemple d'algorithme de Fibonacci très rapide:

fib = zipWith (+) (0:(1:fib)) (1:fib)

zipWith est une fonction de Prelude standard:

zipWith :: (a->b->c) -> [a]->[b]->[c]
zipWith op (n1:val1) (n2:val2) = (n1 + n2) : (zipWith op val1 val2)
zipWith _ _ _ = []

Tester:

print $ take 100 fib

Production:

[1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,433494437,701408733,1134903170,1836311903,2971215073,4807526976,7778742049,12586269025,20365011074,32951280099,53316291173,86267571272,139583862445,225851433717,365435296162,591286729879,956722026041,1548008755920,2504730781961,4052739537881,6557470319842,10610209857723,17167680177565,27777890035288,44945570212853,72723460248141,117669030460994,190392490709135,308061521170129,498454011879264,806515533049393,1304969544928657,2111485077978050,3416454622906707,5527939700884757,8944394323791464,14472334024676221,23416728348467685,37889062373143906,61305790721611591,99194853094755497,160500643816367088,259695496911122585,420196140727489673,679891637638612258,1100087778366101931,1779979416004714189,2880067194370816120,4660046610375530309,7540113804746346429,12200160415121876738,19740274219868223167,31940434634990099905,51680708854858323072,83621143489848422977,135301852344706746049,218922995834555169026,354224848179261915075,573147844013817084101]

Temps écoulé: 0,00018s

Валерий Кобзарь
la source
Cette solution est géniale!
Larry