Comment faites-vous une fonction mémoize générique dans Haskell?

Question

J'ai vu the other post about this, mais y a-t-il une manière propre de le faire dans Haskell?

En 2ème partie, peut-on le faire sans rendre la fonction monadique?

Answer 1

Ceci suit en grande partie http://www.haskell.org/haskellwiki/Memoization.

Vous voulez une fonction de type (a -> b). S'il ne s'appelle pas lui-même, alors vous pouvez simplement écrire un wrapper simple qui met en cache les valeurs de retour. Le meilleur moyen de stocker ce mappage dépend des propriétés d'un exploit . La commande est à peu près un minimum. Avec les entiers , vous pouvez construire une liste paresseuse infinie ou une arborescence contenant les valeurs.

type Cacher a b = (a -> b) -> a -> b 

positive_list_cacher :: Cacher Int b 
positive_list_cacher f n = (map f [0..]) !! n 

ou

integer_list_cacher :: Cacher Int b 
integer_list_cacher f n = (map f (interleave [0..] [-1, -2, ..]) !! 
    index n where 
     index n | n < 0 = 2*abs(n) - 1 
     index n | n >= 0 = 2 * n 

Ainsi, supposons qu'il est récursive. Ensuite, vous avez besoin d'appeler lui-même pas, mais la version memoized, vous repasserez à la place:

f_with_memo :: (a -> b) -> a -> b 
f_with_memo memoed base = base_answer 
f_with_memo memoed arg = calc (memoed (simpler arg)) 

La version memoized est, bien sûr, ce que nous essayons de définir.

Mais nous pouvons commencer par la création d'une fonction qui met en cache ses entrées:

Nous pourrions construire un niveau en passant dans une fonction qui crée une structure que les valeurs en cache. . Sauf que nous devons créer la version de f que a déjà la fonction cache passé dans

Merci à la paresse, c'est pas un problème:

memoize cacher f = cached where 
     cached = cacher (f cached) 

alors tout ce dont nous avons besoin est de l'utiliser:

exposed_f = memoize cacher_for_f f 

l'article donne des conseils quant à la façon d'utiliser une sélection de classe de type sur l'entrée à la fonction de faire ce qui précède, plutôt que de choisir unexplicitefonction de mise en cache. Cela peut être vraiment agréable - plutôt que de construire explicitement un cache pour chaque combinaison de types d'entrée, nous pouvons implicitement combiner des caches pour les types a et b dans un cache pour une fonction en prenant a et b.Une dernière mise en garde: l'utilisation de cette technique paresseuse signifie que le cache ne rétrécit jamais, il ne fait que croître. Si vous utilisez à la place la monade IO, vous pouvez gérer cela, mais le fait sagement dépend des habitudes d'utilisation.

Answer 2

Si vos arguments vont être des nombres naturels, vous pouvez le faire simplement:

memo f = let values = map f [0..] 
    in \n -> values !! n 

Cependant, cela ne vous aide pas vraiment avec la pile déborde, et il ne fonctionne pas avec les appels récursifs. Vous pouvez voir des solutions plus fantaisistes au http://www.haskell.org/haskellwiki/Memoization.

Answer 3

En faisant une traduction directe des langues les plus impératives, je suis venu avec cela.

memoize :: Ord a => (a -> IO b) -> IO (a -> IO b) 
memoize f = 
    do r <- newIORef Map.empty 
    return $ \x -> do m <- readIORef r 
         case Map.lookup x m of 
          Just y -> return y 
          Nothing -> do y <- f x 
              writeIORef r (Map.insert x y m) 
              return y 

Mais cela n'est pas satisfaisant. En outre, Data.Map contraint le paramètre à être une instance de Ord.

Answer 4

Les memocombinateurs de données de paquets sur le hackage fournissent beaucoup de routines de mémoisation réutilisables. L'idée de base est:

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

I.e. il peut mémoriser n'importe quelle fonction d'un. Le module fournit ensuite des primitives (comme unit :: Memo() et integral :: Memo Int) et des combinateurs pour construire des tables de mémos plus complexes (comme pair :: Memo a -> Memo b -> Memo (a,b) et list :: Memo a -> Memo [a]).

Answer 5

Vous pouvez modifier la solution de Jonathan avec safePerformIO pour créer une version mémoizing "pure" de votre fonction.

import qualified Data.Map as Map 
import Data.IORef 
import System.IO.Unsafe 

memoize :: Ord a => (a -> b) -> (a -> b) 
memoize f = unsafePerformIO $ do 
    r <- newIORef Map.empty 
    return $ \ x -> unsafePerformIO $ do 
     m <- readIORef r 
     case Map.lookup x m of 
      Just y -> return y 
      Nothing -> do 
        let y = f x 
        writeIORef r (Map.insert x y m) 
        return y 

Cela fonctionne avec les fonctions récursives:

fib :: Int -> Integer 
fib 0 = 1 
fib 1 = 1 
fib n = fib_memo (n-1) + fib_memo (n-2) 

fib_memo :: Int -> Integer 
fib_memo = memoize fib 

Altough cet exemple est une fonction avec un paramètre entier, le type de memoize nous dit qu'il peut être utilisé avec une fonction qui prend un comparable type. Si vous avez une fonction avec plus d'un paramètre, il suffit de les regrouper dans un tuple avant d'appliquer memoize. F.i .:

f :: String -> [Int] -> Float 
f ... 

f_memo = curry (memoize (uncurry f))