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)
fib 0
ne se termine pas: vous voulez probablement que les cas de basefib'
soientfib' 0 = 0
etfib' 1 = 1
.fibs = 1:1:zipWith (+) fibs (tail fibs)
etfib = (fibs !!)
.Réponses:
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!!99
le 100e emplacement de la liste est "étoffé", tenant le numéro99
maintenant, 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":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:
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 niveauf
.Chaque nouvelle invocation de
fib2
semble 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 den
(merci à Vitus et Tikhon pour l'avoir souligné). Avec la première définition, il n'y a pas de quoin
dépendre, et avec la troisième il y a une dépendance, mais chaque appel séparé à desfib3
appels dansf
lequel fait attention à n'appeler que des définitions de portée de même niveau, interne à cet appel spécifique defib3
, donc la même chosexs
obtient réutilisé (c'est-à-dire partagé) pour cet appel defib3
.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
n
liaison 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,fib3
présente un partage local etfib2
aucun 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. :)
la source
fib'
est redéfinie pour toutn
et doncfib'
dansfib 1
≠fib'
infib 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.where
les clauses introduisent le partage comme deslet
expressions, mais elles ont tendance à cacher des problèmes comme celui-ci. En le réécrivant un peu plus explicitement, vous obtenez ceci: hpaste.org/71406Int -> Integer
), alorsfib2
s'exécute en temps exponentiel,fib1
et lesfib3
deux s'exécutent en temps linéaire maisfib1
est également mémorisé - encore une fois parce quefib3
les définitions locales sont redéfinies pour chaquen
.pwr (x:xs) = pwr xs ++ map (x:) pwr xs ; pwr [] = [[]]
nous voulonspwr 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.Je ne suis pas tout à fait certain, mais voici une supposition éclairée:
Le compilateur suppose que cela
fib n
pourrait être différent sur un autren
et aurait donc besoin de recalculer la liste à chaque fois. Les bits à l'intérieur de l'where
instruction pourraient dépendren
, après tout. Autrement dit, dans ce cas, toute la liste des nombres est essentiellement une fonction den
.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 den
passé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
fib
version 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) .
la source
fib' n
pourrait être différent sur un différentn
" peut-être?fib
, y comprisfib'
, pouvait être différent sur chaque différentn
. Je pense que l'exemple original est un peu déroutant car celafib'
dépend aussi de lui-même de l'n
ombre à l'autren
.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
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 commeIl 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.)
la source
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.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:
zipWith est une fonction de Prelude standard:
Tester:
Production:
Temps écoulé: 0,00018s
la source