Comment fonctionnent Data.Memocombinators?

Question

J'ai regardé la source depuis Data.memocombinateurs Mais je ne peux pas vraiment voir où est le cœur.

Veuillez m'expliquer quelle est la logique derrière tous ces combinateurs et la mécanique de la façon dont ils travaillent réellement pour accélérer votre programme dans la programmation du monde réel.

Je recherche des détails pour cette Mise en œuvre, et éventuellement comparaison / contraste avec les autres approches de Haskell pour la mémorisation. Je comprends ce qu'est la mémorisation et je suis ne pas à la recherche d'une description de son fonctionnement en général.

Answer 1

Cette bibliothèque est une combinatisation simple 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 que vous savez comment et pourquoi cela fonctionne. Je vais donc me concentrer sur la combination.

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 a du sens: 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 "Memoizer pour Int" (même id, qui ne fait pas la mémoire). Nous généralisons à cette abstraction:

type Memo a = forall r. (a -> r) -> (a -> r)

Donc un Memo a, un souvenir pour a, prend une fonction de a à n'importe quoi, et renvoie une fonction sémantiquement identique qui a été mémorisée (ou non).

L'idée des différents mémoriseurs est de trouver un moyen d'énumérer le domaine avec une structure de données, de cartographier la fonction sur eux, puis d'indexer la structure des 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 équivalents aux paires, sauf qu'une paire n'évaluera chaque composant qu'une seule fois (comme c'est le cas pour chaque valeur qui se produit en dehors d'un lambda). Nous gardons donc simplement une paire et dos. Le point essentiel est que nous soulevons l'évaluation de la fonction au-dessus de la lambda pour l'argument (ici le dernier argument de table) en énumérant le domaine.

Mémoire Maybe a est une histoire similaire, sauf que maintenant nous devons savoir comment mémoriser a pour le Just Cas. Donc le mémoit pour Maybe prend un mémoriseur 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 des variations sur ce thème.

La façon dont il mémorise les types intégraux utilise une structure plus appropriée que [0..]. C'est un peu impliqué, mais crée simplement un arbre infini (représentant les nombres en binaire pour élucider la structure):

1
  10
    100
      1000
      1001
    101
      1010
      1011
  11
    110
      1100
      1101
    111
      1110
      1111

De sorte que 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 TypeClass au lieu d'une présentation Combinator. Nous avons libéré nos bibliothèques indépendamment en même temps (en effet, en quelques heures!). Conal's est plus facile à utiliser dans des cas simples (il n'y a qu'une seule fonction, memo, et il déterminera la structure de la note à utiliser en fonction du type), tandis 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émorisait que des valeurs inférieures à une limite donnée, nécessaire pour la mise en œuvre de l'un des problèmes du projet Euler.

Il existe d'autres approches, par exemple, exposant une fonction de point de fix 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. Purger les caches, LRU, etc. Mais c'est une douleur dans le cul à utiliser, et il met également des contraintes de stricte sur la fonction à noter (par exemple, aucune récursion infinie gauche). Je ne crois pas qu'il y ait des bibliothèques qui implémentent cette technique.

Cela a-t-il répondu à quoi vous étiez curieux? Sinon, faites peut-être expliciter les points dont vous êtes confus?

Answer 2

Le cœur est le bits fonction:

-- | Memoize an ordered type with a bits instance.
bits :: (Ord a, Bits a) => Memo a
bits f = IntTrie.apply (fmap f IntTrie.identity)

C'est la seule fonction (sauf le trivial unit :: Memo ()) qui peut vous donner un Memo a évaluer. Il utilise la même idée que dans ce page À propos de la mémorisation de Haskell. La section 2 montre que la stratégie de mémorisation la plus simple à l'aide d'une liste et la section 3 fait de même en utilisant un arbre binaire de naturels similaire à IntTree Utilisé dans les méocombinateurs.

L'idée de base est d'utiliser une construction comme (map fib [0 ..] !!) ou dans le cas des méocombinateurs - IntTrie.apply (fmap f IntTrie.identity). La chose à remarquer ici est la correspondance entre IntTie.apply et !! et aussi entre IntTrie.identity et [0..].

L'étape suivante consiste à mémoriser les fonctions avec d'autres types d'arguments. Cela se fait avec le wrap fonction qui utilise un isomorphisme entre les types a et b Pour construire un Memo b de Memo a. Par exemple:

Memo.integral f
=>
wrap fromInteger toInteger bits f
=>
bits (f . fromInteger) . toInteger
=>
IntTrie.apply (fmap (f . fromInteger) IntTrie.identity) . toInteger
~> (semantically equivalent)
(map (f . fromInteger) [0..] !!) . toInteger

Le reste du code source traite des types comme la liste peut-être, peut-être et de la mémorisation de plusieurs arguments.

Answer 3

Une partie du travail est effectuée par Inttrie: http://hackage.haskell.org/package/data-intrie-0.0.4

La bibliothèque de Luke est une variation de la bibliothèque Memotrie de Conal, qu'il a décrite ici: http://conal.net/blog/posts/elegant-memoization-with-finctional-memo-trries/

Une nouvelle expansion - la notion générale derrière la mémorisation fonctionnelle est de prendre une fonction a -> b et le cartographier sur une datastructure indexée par tout est possible des valeurs a et contenant des valeurs de b. Une telle données doit être paresseuse de deux manières - elle doit d'abord être paresseuse dans les valeurs qu'elle détient. Deuxièmement, il devrait être produit paresseusement. Le premier est par défaut dans une langue non distribuée. Ce dernier est accompli en utilisant des essais généralisés.

Les diverses approches des méocombinateurs, de la mémoire, etc. ne sont que des moyens de créer des compositions d'essais sur des types individuels de données pour permettre la construction simple d'essais pour des structures de plus en plus complexes.

Answer 4

@Luqui une chose qui n'est pas claire pour moi: cela a-t-il le même comportement opérationnel que le suivant:

fib :: [Int]
fib = map fib' [0..]
    where fib' 0 = 0
             fib' 1 = 1
             fib' n = fib!!(n-1) + fib!!(n-2)

Ce qui précède doit mémoriser FIB au niveau supérieur, et donc si vous définissez deux fonctions:

f n = fib!!n + fib!!(n+1)

Si nous calculons alors f 5, nous obtenons ça fib 5 n'est pas recomputé lors du calcul fib 6. Il n'est pas clair pour moi si les combinateurs de mémorisation ont le même comportement (c'est-à-dire la mémorisation de niveau supérieur au lieu d'interdire uniquement la recomputation "à l'intérieur" du calcul FIB), et si oui, pourquoi exactement?