Quand la mémorisation est-elle automatique dans GHC Haskell?

Je ne comprends pas pourquoi m1 est apparemment mémorisé alors que m2 n'est pas dans ce qui suit:

m1      = ((filter odd [1..]) !!)

m2 n    = ((filter odd [1..]) !! n)

m1 10000000 prend environ 1,5 seconde sur le premier appel, et une fraction de cela sur les appels suivants (vraisemblablement il met en cache la liste), alors que m2 10000000 prend toujours le même temps (reconstruction de la liste à chaque appel). Une idée de ce qui se passe? Existe-t-il des règles empiriques pour savoir si et quand GHC mémorisera une fonction? Merci.

GHC ne mémorise pas les fonctions.

Cependant, il calcule une expression donnée dans le code au plus une fois par fois que son expression lambda environnante est entrée, ou au plus une fois si elle est au niveau supérieur. Déterminer où se trouvent les expressions lambda peut être un peu délicat lorsque vous utilisez du sucre syntaxique comme dans votre exemple, alors convertissons-les en syntaxe désuète équivalente:

m1' = (!!) (filter odd [1..])              -- NB: See below!
m2' = \n -> (!!) (filter odd [1..]) n

(Remarque: le rapport Haskell 98 décrit en fait une section d'opérateur de gauche (a %)comme équivalente à \b -> (%) a b, mais GHC la désuète (%) a. Celles-ci sont techniquement différentes car elles peuvent être distinguées par seq. Je pense que j'ai peut-être soumis un ticket GHC Trac à ce sujet.)

Compte tenu de cela, vous pouvez voir que dans m1', l'expression filter odd [1..]n'est contenue dans aucune expression lambda, donc elle ne sera calculée qu'une fois par exécution de votre programme, tandis que dans m2', filter odd [1..]sera calculée chaque fois que l'expression lambda est entrée, c'est-à-dire, à chaque appel de m2'. Cela explique la différence de timing que vous voyez.

En fait, certaines versions de GHC, avec certaines options d'optimisation, partageront plus de valeurs que la description ci-dessus ne l'indique. Cela peut être problématique dans certaines situations. Par exemple, considérons la fonction

f = \x -> let y = [1..30000000] in foldl' (+) 0 (y ++ [x])

GHC peut remarquer que ycela ne dépend pas de xet réécrire la fonction pour

f = let y = [1..30000000] in \x -> foldl' (+) 0 (y ++ [x])

Dans ce cas, la nouvelle version est beaucoup moins efficace car elle devra lire environ 1 Go de la mémoire où yest stockée, tandis que la version d'origine fonctionnerait dans un espace constant et rentrerait dans le cache du processeur. En fait, sous GHC 6.12.1, la fonction fest presque deux fois plus rapide lorsqu'elle est compilée sans optimisations qu'avec elle -O2.

m1 n'est calculé qu'une seule fois car il s'agit d'une forme applicative constante, tandis que m2 n'est pas un CAF, et est donc calculé pour chaque évaluation.

Voir le wiki du GHC sur les CAF: http://www.haskell.org/haskellwiki/Constant_applicative_form

Il existe une différence cruciale entre les deux formes: la restriction du monomorphisme s'applique à m1 mais pas à m2, car m2 a explicitement donné des arguments. Le type de m2 est donc général mais celui de m1 est spécifique. Les types qui leur sont attribués sont:

m1 :: Int -> Integer
m2 :: (Integral a) => Int -> a

La plupart des compilateurs et interprètes Haskell (tous que je connais en fait) ne mémorisent pas les structures polymorphes, donc la liste interne de m2 est recréée à chaque fois qu'elle est appelée, là où m1 ne l'est pas.

Je ne suis pas sûr, car je suis moi-même assez nouveau dans Haskell, mais il semble que cela soit dû au fait que la deuxième fonction est paramétrée et que la première ne l'est pas. La nature de la fonction est que son résultat dépend de la valeur d'entrée et dans le paradigme fonctionnel, il dépend UNIQUEMENT de l'entrée. L'implication évidente est qu'une fonction sans paramètre renvoie toujours la même valeur à plusieurs reprises, quoi qu'il arrive.

Apparemment, il y a un mécanisme d'optimisation dans le compilateur GHC qui exploite ce fait pour calculer la valeur d'une telle fonction une seule fois pour l'ensemble de l'exécution du programme. Il le fait paresseusement, certes, mais le fait néanmoins. Je l'ai remarqué moi-même, lorsque j'ai écrit la fonction suivante:

primes = filter isPrime [2..]
    where isPrime n = null [factor | factor <- [2..n-1], factor `divides` n]
        where f `divides` n = (n `mod` f) == 0

Ensuite , pour le tester, je suis entré dans GHCi et écrit: primes !! 1000. Il a fallu quelques secondes, mais finalement je me suis la réponse: 7927. Ensuite, j'ai appelé primes !! 1001et j'ai obtenu la réponse instantanément. De même, en un instant, j'ai obtenu le résultat pour take 1000 primes, car Haskell devait calculer la liste des mille éléments entière pour renvoyer le 1001e élément avant.

Ainsi, si vous pouvez écrire votre fonction de telle sorte qu'elle ne prenne aucun paramètre, vous en voudrez probablement. ;)