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

Question

Je ne peux pas comprendre pourquoi est apparemment memoized m1 alors que m2 est pas dans les domaines suivants:

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

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

prend environ 10.000.000 m1 1,5 secondes sur le premier appel, et une fraction de celle sur les appels suivants (on peut supposer qu'il met en cache la liste), tandis que m2 10000000 prend toujours le même laps de temps (reconstruire la liste avec chaque appel). Une idée de ce qui se passe? Existe-t-il des règles générales 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 plus une fois par fois que son expression lambda environnante est entrée, ou tout au plus une fois si elle est au niveau supérieur. Déterminer où les expressions lambda-sont peut être un peu délicat lorsque vous utilisez du sucre syntaxique comme dans votre exemple, si nous allons convertir en syntaxe Dessucré équivalente:

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

(Note: Le rapport Haskell 98 décrit en fait un opérateur gauche section comme (a %) comme équivalent à \b -> (%) a b, mais GHC desugars à (%) a. ce sont techniquement différents parce qu'ils peuvent être distingués par seq. Je pense que je pourrais avoir soumis un billet GHC Trac à ce sujet.)

Donné ce, vous pouvez voir que dans m1', l'expression filter odd [1..] n'est pas contenue n toute 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 ce que la description ci-dessus 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 y ne dépend pas de x et récrire la fonction à

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

Dans ce cas, la nouvelle version est beaucoup moins efficace parce qu'il aura lire environ 1 Go de la mémoire où y est stocké, tandis que la version d'origine s'exécuterait dans un espace constant et entrer dans le cache du processeur. En fait, sous GHC 6.12.1, la fonction f est presque deux fois plus rapide lorsqu'elle est compilée sans optimisations qu'elle n'est compilée avec -O2.

Answer 2

m1 est calculé 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 GHC sur CAFs: http://www.haskell.org/haskellwiki/Constant_applicative_form

Answer 3

Il y a une différence essentielle entre les deux formes: la restriction de monomorphisme applique à m1, mais pas m2, parce que m2 a explicitement donné des arguments. Le type de m2 est donc général mais celui de m1 est spécifique.Les types auxquels ils sont affectés sont:

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

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

Answer 4

Je ne suis pas sûr, parce que je suis assez nouveau pour Haskell moi-même, 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 en particulier du paradigme fonctionnel, cela dépend UNIQUEMENT de l'entrée. L'implication évidente est qu'une fonction sans paramètre retourne toujours la même valeur encore et encore, quoi qu'il arrive. Il existe clairement 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'exécution du programme entier. Il le fait paresseusement, pour être sûr, mais le fait néanmoins. Je l'ai remarqué moi-même, quand je l'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 de le tester, je suis entré dans GHCi et écrit: primes !! 1000. Il a fallu quelques secondes, mais finalement j'ai eu la réponse: 7927. Puis j'ai appelé primes !! 1001 et j'ai obtenu la réponse instantanément. De même dans un instant, j'ai obtenu le résultat pour take 1000 primes, parce que Haskell a dû calculer toute la liste des milliers d'éléments pour retourner 1001st élément avant. Ainsi, si vous pouvez écrire votre fonction de telle sorte qu'elle ne prenne aucun paramètre, vous en aurez probablement besoin.