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

Question

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

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

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

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

Answer 1

GHC ne mémorise pas les fonctions.

Cependant, il calcule une expression donnée dans le code au maximum une fois à chaque fois que l'expression lambda qui l'entoure est saisie, ou au maximum une fois à chaque fois si elle se trouve au niveau supérieur. Déterminer où se trouvent les expressions lambda peut être un peu délicat lorsque vous utilisez un sucre syntaxique comme dans votre exemple, alors convertissons-les en syntaxe désucrée équivalente :

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

(Note : Le rapport Haskell 98 décrit en fait une section d'opérateur gauche comme (a %) comme équivalent à \b -> (%) a b mais GHC le désucre en (%) a . Ils sont techniquement différents car ils peuvent être distingués par seq . Je pense que j'ai peut-être soumis un ticket Trac GHC à ce sujet).

Compte tenu de cela, vous pouvez voir que dans m1' l'expression filter odd [1..] n'est pas contenue dans une expression lambda, elle ne sera donc calculée qu'une seule fois par exécution de votre programme, alors que dans l'expression m2' , filter odd [1..] sera calculée à chaque fois que l'expression lambda est saisie, c'est-à-dire à chaque appel de la fonction 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 pourrait remarquer que y ne dépend pas de x et réécrire la fonction en

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 mémoire où y est stockée, alors que la version originale s'exécuterait en espace constant et tiendrait dans le cache du processeur. En fait, sous GHC 6.12.1, la fonction f est presque deux fois plus rapide lorsqu'il est compilé sans qu'il est compilé avec -O2 .

Answer 2

M1 n'est calculé qu'une seule fois car il s'agit d'une Forme Applicative Constante, alors que m2 n'est pas un CAF, et est donc calculé pour chaque évaluation.

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

Answer 3

Il y a une différence cruciale entre les deux formes : la restriction du monomorphisme s'applique à m1 mais pas à m2, car m2 a des arguments explicitement donnés. 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 ceux 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, alors que celle de m1 ne l'est pas.

Answer 4

Je ne suis pas sûr, parce que je suis moi-même assez nouveau en Haskell, mais il semble que c'est parce que la deuxième fonction est paramétrée et 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 ne dépend QUE de l'entrée. L'implication évidente est qu'une fonction sans paramètres renvoie toujours la même valeur, quoi qu'il arrive.

Apparemment, il existe un mécanisme d'optimisation dans le compilateur GHC qui exploite ce fait pour calculer la valeur d'une telle fonction une seule fois pendant toute la durée d'exécution du programme. Il le fait paresseusement, certes, mais il le fait quand même. 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

Puis, pour le tester, je suis entré dans GHCI et j'ai écrit : primes !! 1000 . Cela a pris quelques secondes, mais j'ai finalement obtenu la réponse : 7927 . Puis j'ai appelé primes !! 1001 et 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 a dû calculer toute la liste de mille éléments pour retourner le 1001e élément auparavant.

Ainsi, si vous pouvez écrire votre fonction de manière à ce qu'elle ne prenne aucun paramètre, c'est probablement ce que vous voulez. ;)