Le mécanisme d'évaluation en Haskell est par nécessité: quand une valeur est nécessaire, il est calculé, et mis à disposition dans le cas où il est demandé à nouveau. Si nous définissons quelques liste, xs=[0..] et, plus tard, de demander pour son 100e élément, xs!!99, le 100e fente dans la liste devient "chair", en maintenant le nombre 99 maintenant, prêt pour le prochain accès.
C'est quoi ce truc, "going-par-une-liste", est en train d'exploiter. Normal doublement recursve Fibonacci définition, fib n = fib (n-1) + fib (n-2), la fonction elle-même est appelée, deux fois par le haut, à l'origine de la hausse exponentielle. Mais avec cette astuce, nous avons établi une liste de résultats intermédiaires, et d'aller "dans la liste":
fib n = (xs!!(n-1)) + (xs!!(n-2)) where xs = 0:1:map fib [2..]
Le truc, c'est à cause de cette liste pour obtenir créé, et faire en sorte que la liste ne pas aller loin (par le biais de la collecte des ordures) entre les appels à l' fib. La façon la plus simple de faire cela est de nom de cette liste. "Si vous avez un nom, il va rester."
Votre première version définit un monomorphe constante, et la deuxième définit une fonction polymorphe. Une fonction polymorphe ne pouvez pas utiliser la même liste interne pour les différents types dont elle a besoin pour servir, donc pas de partage, c'est à dire pas de memoization.
Avec la première version, le compilateur est généreux avec nous, en prenant la constante sous-expression (map fib' [0..]) et en faire un distinct partageable entité, mais il n'est pas soumis à aucune obligation de le faire. et il y a effectivement des cas où on ne souhaitez faire que pour nous automatiquement.
(edit:) tenir compte de ces ré-écrit:
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)
Donc la vraie histoire semble être sur le sous-champ d'application définitions. Il est dénuée de portée avec le 1er et le 3ème est prudent de ne pas appeler de l'extérieur-champ fib3, mais le même niveau f.
Chaque nouvelle invocation d' fib2 semble créer son imbriqués les définitions de nouveau parce que l'un d'eux peut (en théorie) être défini différemment en fonction de la valeur de n (merci à Guy et Tikhon pour le pointage). Avec la première définition il n'y a pas d' n dépendent, et à la troisième il y a une dépendance, mais chaque appel à l' fib3 d'appels en f qui est prudent de n'appeler que les définitions de même au niveau de la portée, à l'intérieur de cette invocation de l' fib3, de sorte que le même xs obtient réutilisés (c'est à dire partagée) pour que l'invocation de l' 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épendants de l'extérieur, n obligatoire, à effectuer le lambda de levage après tout, résultant en plein memoization (sauf pour le polymorphe définitions). En fait, c'est exactement ce qui se passe avec les trois versions déclaré avec monomorphe types et compilé avec-O2 drapeau. Avec polymorphes déclarations de type, fib3 expositions locales, le partage et l' fib2 sans partage à tous.
En fin de compte, selon un compilateur, et les optimisations du compilateur utilisé, et comment vous le tester (le chargement de fichiers dans GHCI, compilé ou non, avec -O2 ou pas, ou autonome), et si elle obtient un monomorphe ou polymorphe type de comportement pourrait changer complètement de savoir si c'expositions locales (par appel), le partage (c'est à dire le temps linéaire sur chaque appel), memoization (c'est à dire le temps linéaire sur première convocation, et 0 dans le temps sur les appels suivants avec la même ou plus petit argument), ou pas de partage à tous (temps exponentiel).
Bref, c'est un compilateur chose. :)
