sobre - imprimir en haskell

¿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 forma clara de hacer esto en Haskell?

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

Answer 1

Al hacer 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 restringe el parámetro para que sea una instancia de Ord .

Answer 2

Si tus argumentos van a ser números naturales, puedes hacer simplemente:

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

Sin embargo, eso realmente no te ayuda con el desbordamiento de la pila, y no funciona con llamadas recursivas. Puede ver algunas soluciones más sofisticadas en http://www.haskell.org/haskellwiki/Memoization .

Answer 3

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

Desea una función de tipo (a -> b). Si no se llama a sí mismo, puede simplemente escribir un contenedor simple que almacena en caché los valores devueltos. La mejor forma de almacenar este mapeo depende de las propiedades que pueda explotar. Ordenar es prácticamente un mínimo. Con 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

Entonces, supongamos que es recursivo. Luego, necesita que no llame a sí mismo, sino a la versión modificada, por lo que la transfiere 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 memorable es, por supuesto, lo que estamos tratando de definir.

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

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

Gracias a la pereza, esto no es 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 da pistas sobre cómo usar una clase de tipo seleccionando en la entrada de la función para hacer lo anterior, en lugar de elegir una función de caché explícita. Esto puede ser realmente agradable: en lugar de construir explícitamente un caché para cada combinación de tipos de entrada, podemos combinar implícitamente 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 encoge, solo crece. Si en su lugar usa la mónada IO, puede gestionar esto, pero hacerlo de manera inteligente depende de los patrones de uso.

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)

Es decir, puede memorizar cualquier función de a. El módulo proporciona algunas primitivas (como unit :: Memo () e integral :: Memo Int ), y combinadores para construir tablas de memo 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 inseguraPerformIO 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 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 memoria nos dice que se puede usar con cualquier función que tenga un tipo comparable. Si tiene una función con más de un parámetro, simplemente agrúpelos en una tupla antes de aplicar memoize. Fi:

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

f_memo = curry (memoize (uncurry f))