Comment savoir si Haskell mettra en cache un résultat ou le recalculera?

Question

J'ai remarqué que, parfois, Haskell fonctions pures sont en quelque sorte mis en cache: si j'appelle la fonction deux fois avec les mêmes paramètres, la deuxième fois, le résultat est calculé en un rien de temps.

1. Pourquoi est-ce arrivé? Est-il un GHCI fonction ou quoi?
2. Puis-je compter sur cela (c'est à dire: puis-je de façon déterministe savoir si une valeur de fonction sera mis en cache)?
3. Puis-je la force ou de désactiver cette fonctionnalité pour certains appels de fonction?

---

Tel que requis par les commentaires, voici un exemple que j'ai trouvé sur le web:

isPrime a = isPrimeHelper a primes
isPrimeHelper a (p:ps)
    | p*p > a = True
    | a `mod` p == 0 = False
    | otherwise = isPrimeHelper a ps
primes = 2 : filter isPrime [3,5..]

Je m'attendais, avant de l'exécuter, pour être un peu plus lent, car il conserve l'accès aux éléments d' primes sans explicitement la mise en cache d'eux (donc, à moins que ces valeurs sont mises en cache quelque part, ils doivent être recalculés à de nombreuses reprises). Mais j'avais tort.

Si j'ai mis en +s dans GHCI (pour imprimer calendrier/mémoire stats après chaque évaluation) et d'évaluer l'expression primes!!10000 deux fois, c'est ce que j'obtiens:

*Main> :set +s
*Main> primes!!10000
104743
(2.10 secs, 169800904 bytes)
*Main> primes!!10000
104743
(0.00 secs, 0 bytes)

Cela signifie qu'au moins primes !! 10000 "(ou mieux: l'ensemble de l' primes la liste, depuis aussi primes!!9999 prendra pas le temps) doit être mis en cache.

Answer 1

primes, dans votre code, n'est pas une fonction, mais une constante, dans haskellspeak connu comme un CAF. Si elle prend un paramètre (par exemple, ()), vous obtenez deux versions différentes de la même liste de retour si l'appelant deux fois, mais comme c'est une FAC, vous obtenez exactement la même liste de deux fois;

Comme un ghci de haut niveau de la définition, primes ne devient jamais inaccessible, donc la tête de la liste de points (et donc sa queue/le reste du calcul) n'est jamais nettoyée. Ajout d'un paramètre empêche de retenir que la référence, la liste sera ensuite nettoyée comme (!!) itère vers le bas pour trouver le bon élément, et votre deuxième appel à (!!) serait la force de la répétition de l'ensemble de calcul au lieu de simplement traverser le déjà-calculé de la liste.

Notez que dans les programmes compilés, il n'y a pas de haut-niveau comme dans ghci et les choses se ordures collectées lors de la dernière référence est allé, très probablement avant tout le programme des sorties, de la CAF ou pas, ce qui signifie que votre premier appel aurait fallu longtemps, la seconde un peu, et après cela, "l'avenir de votre programme" pas référence à la FAC plus, la mémoire de la CAF prend est recyclé.

Les nombres premiers paquet fournit une fonction qui prend un argument pour (principalement, j'avais demande) cette même raison, que la réalisation de près d'un demi-téraoctet de nombres premiers peut-être pas ce que l'on veut faire.

Si vous voulez vraiment obtenir vers le bas de cela, je vous recommande la lecture du STG papier. Il ne comprend pas de nouveaux développements dans le GHC, mais fait du bon travail en expliquant comment Haskell des cartes sur l'assemblée, et donc comment les thunks se faire dévorer par la rigueur, en général.