Cette bibliothèque est une combinatoire directe de la technique bien connue de la mémorisation. Commençons par l'exemple canonique :
fib = (map fib' [0..] !!)
where
fib' 0 = 0
fib' 1 = 1
fib' n = fib (n-1) + fib (n-2)
J'interprète ce que vous avez dit comme signifiant que vous savez comment et pourquoi cela fonctionne. Je vais donc me concentrer sur la combinatoire.
Nous essayons essentiellement de capturer et de généraliser l'idée de (map f [0..] !!) . Le type de cette fonction est (Int -> r) -> (Int -> r) ce qui est logique : il prend une fonction de Int -> r et renvoie une version mémorisée de la même fonction. Toute fonction qui est sémantiquement l'identité et qui a ce type est appelée un "memoizer for Int "(même id qui ne mémorise pas). Nous généralisons à cette abstraction :
type Memo a = forall r. (a -> r) -> (a -> r)
Donc un Memo a un mémorisateur pour a prend une fonction de a à n'importe quoi, et retourne une fonction sémantiquement identique qui a été mémorisée (ou non).
L'idée des différents memoizers est de trouver un moyen d'énumérer le domaine avec une structure de données, de mapper la fonction sur eux, puis d'indexer la structure de données. bool est un bon exemple :
bool :: Memo Bool
bool f = table (f True, f False)
where
table (t,f) True = t
table (t,f) False = f
Fonctions de Bool sont équivalentes aux paires, sauf qu'une paire n'évaluera chaque composant qu'une seule fois (comme c'est le cas pour chaque valeur qui apparaît en dehors d'une lambda). Nous nous contentons donc de faire un mapping vers une paire et inversement. Le point essentiel est que nous élevons l'évaluation de la fonction au-dessus de la lambda de l'argument (ici le dernier argument de table ) en énumérant le domaine.
Memoizing Maybe a est une histoire similaire, sauf que maintenant nous devons savoir comment mémoriser a pour le Just cas. Donc le mémorisateur pour Maybe prend un mémorisateur pour a comme argument :
maybe :: Memo a -> Memo (Maybe a)
maybe ma f = table (f Nothing, ma (f . Just))
where
table (n,j) Nothing = n
table (n,j) (Just x) = j x
Le reste de la bibliothèque n'est que variations sur ce thème.
La façon dont il mémorise les types intégraux utilise une structure plus appropriée que celle de [0..] . C'est un peu compliqué, mais il s'agit en fait de créer un arbre infini (en représentant les nombres en binaire pour clarifier la structure) :
1
10
100
1000
1001
101
1010
1011
11
110
1100
1101
111
1110
1111
Ainsi, la recherche d'un nombre dans l'arbre a un temps d'exécution proportionnel au nombre de bits dans sa représentation.
Comme le souligne sclv, la bibliothèque MemoTrie de Conal utilise la même technique sous-jacente, mais utilise une présentation par classes de types au lieu d'une présentation par combinateurs. Nous avons publié nos bibliothèques indépendamment au même moment (en fait, en quelques heures !). La bibliothèque de Conal est plus facile à utiliser dans des cas simples (il n'y a qu'une seule fonction, memo et il déterminera la structure de mémo à utiliser en fonction du type), alors que le mien est plus flexible, car vous pouvez faire des choses comme ceci :
boundedMemo :: Integer -> Memo Integer
boundedMemo bound f = \z -> if z < bound then memof z else f z
where
memof = integral f
Qui ne mémorise que les valeurs inférieures à une limite donnée, nécessaire pour l'implémentation d'un des problèmes d'euler du projet.
Il existe d'autres approches, par exemple l'exposition d'une fonction de point fixe ouverte sur une monade :
memo :: MonadState ... m => ((Integer -> m r) -> (Integer -> m r)) -> m (Integer -> m r)
Ce qui permet encore plus de flexibilité, par exemple la purge des caches, LRU, etc. Mais c'est une douleur dans le cul à utiliser, et aussi il met des contraintes de rigueur sur la fonction à mémoriser (par exemple pas de récursion infinie à gauche). Je ne crois pas qu'il y ait de bibliothèques qui implémentent cette technique.
Cela a-t-il répondu à votre question ? Si ce n'est pas le cas, peut-être pouvez-vous expliciter les points qui vous laissent perplexe ?
