Comment créez-vous une fonction memoize générique dans Haskell?

Question

J'ai lu l'autre message à ce sujet . , mais y at-il un moyen propre de le faire à Haskell?

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

Answer 1

Cela découle en grande partie de http://www.haskell.org/haskellwiki/Memoization . / p>

Vous voulez une fonction de type (a - > b). Si ça ne s'appelle pas, alors vous pouvez simplement écrire un simple wrapper qui met en cache les valeurs de retour. le Le meilleur moyen de stocker ce mappage dépend des propriétés de ce que vous pouvez exploit. La commande est à peu près un minimum. Avec des entiers vous pouvez construire une liste infinie de paresseux ou un arbre 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

Alors, supposons que ce soit récursif. Ensuite, vous en avez besoin pour ne pas appeler elle-même, mais la version mémoisée, vous la transmettez donc à 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 mémo est, bien sûr, ce que nous essayons de définir.

Mais nous pouvons commencer par créer une fonction qui cache ses entrées:

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

Grâce à la paresse, ce n'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 explique comment utiliser une classe de type en sélectionnant sur le entrée à la fonction pour faire ce qui précède, plutôt que de choisir un explicite fonction de mise en cache. Cela peut être vraiment sympa - plutôt que explicitement construire un cache pour chaque combinaison de types d'entrée, on peut implicitement combinez les caches des types a et b dans un cache pour une fonction prenant a et b.

Un dernier avertissement: en utilisant cette technique paresseuse, le cache ne se réduit jamais, ça ne fait que grandir. Si vous utilisez plutôt la monade IO, vous pouvez gérer cela, mais le faire sagement dépend des habitudes d’utilisation.

Answer 2

Le paquet de mémocombinateurs de données sur le piratage fournit de nombreuses routines de mémorisation réutilisables. L'idée de base est la suivante:

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 (telles que unit :: Memo () et integrales :: Memo Int ), ainsi que des combinateurs permettant de créer des tables de mémo plus complexes (telles que la paire :: Mémo a - > Mémo b - > Mémo (a, b) et liste :: Mémo a - > Mémo [a] ).

Answer 3

Vous pouvez modifier la solution de Jonathan avec unsafePerformIO pour créer un "pur" & pur; mémoriser la version 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

Ceci fonctionnera 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

Bien que cet exemple soit une fonction avec un paramètre entier, le type de memoize nous indique qu'il peut être utilisé avec toute fonction prenant un type comparable. 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))

Answer 4

Réalisant une traduction directe à partir des langues les plus impératives, je l’ai imaginé.

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 ceci est en quelque sorte insatisfaisant. Data.Map contraint le paramètre doit être une instance de Ord .

Answer 5

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

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

Cependant, cela ne vous aide pas vraiment avec le débordement de pile, et cela ne fonctionne pas avec les appels récursifs. Vous pouvez découvrir des solutions plus sophistiquées à l'adresse http://www.haskell.org/haskellwiki/Memoization . .