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

Question

He visto la otra publicación sobre esto , pero ¿hay una manera limpia de hacer esto en Haskell?

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

Answer 1

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

Desea una función de tipo (a - > b). Si no se llama a sí mismo, entonces simplemente puede escribir un contenedor simple que almacene en caché los valores de retorno. los La mejor manera de almacenar este mapeo depende de las propiedades que puedas explotar. Ordenar es prácticamente un mínimo. Con enteros puede construir una lista perezosa infinita o un árbol 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

Entonces, supongamos que es recursivo. Entonces lo necesitas para llamarte no a ti mismo, pero la versión memorizada, por lo que pasa eso 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 memorizada es, por supuesto, lo que estamos tratando de definir.

Pero podemos comenzar creando una función que almacene sus entradas en caché:

Podríamos construir un nivel pasando una función que crea un Estructura que almacena valores en caché. Excepto que necesitamos crear la versión de f que ya tiene la función en caché pasada.

Gracias a la pereza, esto no es un problema:

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

entonces todo lo que necesitamos es usarlo:

exposed_f = memoize cacher_for_f f

El artículo proporciona sugerencias sobre cómo usar una clase de tipo seleccionando en la entrada a la función para hacer lo anterior, en lugar de elegir un explícito función de almacenamiento en caché. Esto puede ser realmente bueno, en lugar de explícitamente construyendo un caché para cada combinación de tipos de entrada, podemos implícitamente combine los cachés para los tipos ayb en un caché para una función que toma a y b.

Una advertencia final: el uso de esta técnica perezosa significa que el caché nunca se reduce, sólo crece. Si, en cambio, utiliza la mónada IO, puede gestionar esto, pero hacerlo sabiamente depende de los patrones de uso.

Answer 2

El paquete de datos-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 un archivo. El módulo luego proporciona algunas primitivas (como unit :: Memo () y integral :: Memo Int ), y combinadores para crear tablas de memo más complejas (como el par :: Memo a - > Memo b - > Memo (a, b) y list :: Memo a - > Memo [a] ).

Answer 3

Puedes modificar la solución de Jonathan con unsafePerformIO para crear un " puro " memoizing versió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 funcionará 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

Aunque este ejemplo es una función con un parámetro entero, el tipo de memoize nos dice que se puede usar con cualquier función que tome un tipo comparable. Si tiene una función con más de un parámetro, simplemente agrúpelas en una tupla antes de aplicar memoize. F.i .:

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

f_memo = curry (memoize (uncurry f))

Answer 4

Haciendo una traducción directa de 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 restricciones el parámetro será una instancia de Ord .

Answer 5

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, eso realmente no te ayuda con el desbordamiento de pila, y no funciona con llamadas recursivas. Puede ver algunas soluciones más sofisticadas en http://www.haskell.org/haskellwiki/Memoization .