¿Cómo se hace una función de memoria genérica en Haskell?

Question

He visto the other post about this, pero ¿hay una forma clara de hacerlo en Haskell?

Como segunda parte, ¿también se puede hacer sin hacer la función monádica?

Answer 1

Esto sigue en gran medida a http://www.haskell.org/haskellwiki/Memoization.

Desea una función de tipo (a -> b). Si no se llama a sí mismo, entonces puede simplemente escribir un contenedor simple que almacena en caché los valores devueltos. La mejor forma de almacenar esta asignación en depende de las propiedades de un exploit . Ordenar es prácticamente un mínimo. Con los números enteros puedes construir una lista o árbol perezoso infinito que contenga los valores.

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

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

o

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 

Por lo tanto, supongo que es recursivo. Luego hay que llamar a sí mismo no, pero la versión memoized, por lo que se pasa en su lugar:

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

La versión memoized es, por supuesto, lo que estamos tratando de definir.

Pero podemos empezar por crear una función que almacena sus entradas:

Nos podría construir una planta mediante introducción de una función que crea una estructura que almacena valores. . Salvo que necesitamos para crear la versión de f que ya tiene la función de caché aprobada en

Gracias a la pereza, esto no es problema:

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

entonces todo lo que necesitamos es para usarlo:

exposed_f = memoize cacher_for_f f 

el artículo da consejos sobre cómo utilizar una clase de selección de tipo de la entrada a la función de hacer lo anterior, en lugar de elegir unexplícitafunción de almacenamiento en caché. Esto puede ser muy bueno, en lugar de explícitamente construir un caché para cada combinación de tipos de entrada, podemos implícitamente combinar cachés para los tipos ay b en un caché para una función que tome a y b.

Una advertencia final: el uso de esta técnica perezosa significa que la memoria caché nunca se encoge, solo crece. Si en su lugar usa la mónada IO, puede administrar esto, pero hacerlo sabiamente depende de los patrones de uso.

Answer 2

Si sus argumentos van a ser números naturales, puede hacerlo simplemente:

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

Sin embargo, que en realidad no le ayude con la pila de desbordamiento, y no se ha solucionado con llamadas recursivas. Puede ver algunas soluciones más sofisticadas en http://www.haskell.org/haskellwiki/Memoization.

Answer 3

Al hacer una traducción directa desde los idiomas más imperativos, se me ocurrió esto.

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 

Pero esto es de alguna manera insatisfactorio. Además, Data.Map restringe el parámetro para que sea una instancia de Ord.

Answer 4

El paquete data-memocombinators en hackage proporciona muchas rutinas de memorización reutilizables. La idea básica es:

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

I.e. puede memorizar cualquier función de a. El módulo proporciona algunas primitivas (como unit :: Memo() y integral :: Memo Int) y combinadores para crear tablas de notas más complejas (como pair :: Memo a -> Memo b -> Memo (a,b) y list :: Memo a -> Memo [a]).

Answer 5

Puede modificar la solución de Jonathan con inseguroPerformIO para crear una versión "pura" de la función de memorización de su función.

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 

Esto funciona con funciones recursivas:

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 este ejemplo es una función con un parámetro de número entero, el tipo de memoize nos dice que se puede utilizar con cualquier función que toma una comparable tipo. Si tiene una función con más de un parámetro, simplemente agrúpelos en una tupla antes de aplicar memoize. F.i .:

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

f_memo = curry (memoize (uncurry f))