Como você faz uma função memoize genérica em Haskell?

Question

Eu vi outro post sobre este , mas há uma maneira limpa de fazer isso em Haskell?

Como uma segunda parte, pode também ser feito sem fazer a função monádico?

Answer 1

Isto segue em grande parte http://www.haskell.org/haskellwiki/Memoization .

Você quer uma função do tipo (a -> b). Se não se chamar, em seguida, você pode simplesmente escrever um wrapper simples que armazena os valores de retorno. o melhor maneira de armazenar esse mapeamento depende do que propriedades de um possível explorar. A ordenação é praticamente um mínimo. com números inteiros você pode construir uma lista preguiçoso infinita ou árvore segurando os valores.

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

Assim, suponho que é recursiva. Então você precisa para chamar não em si, mas a versão memoized, então você passar isso em vez disso:

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

A versão memoized é, naturalmente, o que estamos tentando definir.

Mas podemos começar por criar uma função que armazena suas entradas:

Podemos construir um nível, passando de uma função que cria um estrutura que valores caches. Exceto precisamos criar a versão de f que já tem a função em cache passado.

Graças à preguiça, isso não é problema:

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

então tudo necessidade que é usá-lo:

exposed_f = memoize cacher_for_f f

O artigo dá dicas de como usar uma seleção de classe tipo no entrada para a função de fazer o acima, em vez de escolher uma explícita cache função. Isso pode ser muito bom - em vez de explicitamente construção de um cache para cada combinação de tipos de entrada, podemos implicitamente combinar caches para os tipos A e B em um cache para uma função de tomar a e b.

Uma advertência final: usando esta técnica preguiçoso significa que o cache nunca diminui, ele só cresce. Se você, em vez usar a mônada IO, você pode gerenciar isso, mas fazê-lo com sabedoria depende de padrões de uso.

Answer 2

O pacote de dados-memocombinators sobre hackage fornece muitas rotinas memoização reutilizáveis. A idéia básica é:

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

i. ele pode memoize qualquer função a partir de um. O módulo, em seguida, fornece algumas primitivas (como unit :: Memo () e integral :: Memo Int) e combinadores para a construção de tabelas de notas mais complexas (como pair :: Memo a -> Memo b -> Memo (a,b) e list :: Memo a -> Memo [a]).

Answer 3

Você pode modificar solução Jonathan's com unsafePerformIO para criar uma versão "pura" memoizing de sua função.

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

Este irá trabalhar com funções 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 exemplo é uma função com um parâmetro inteiro, o tipo de memoize nos diz que ele pode ser usado com qualquer função que leva um tipo comparável. Se você tem uma função com mais de um parâmetro apenas agrupá-los em uma tupla antes de aplicar memoize. F.i:.

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

f_memo = curry (memoize (uncurry f))

Answer 4

Fazendo uma tradução direta das línguas mais imperativas, eu vim com isso.

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

Mas isso é de alguma forma insatisfatória. Além disso, Data.Map constrangimentos o parâmetro a ser uma instância de Ord .

Answer 5

Se os seus argumentos vão ser números naturais, você pode fazer simplesmente:

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

No entanto, isso não é realmente ajudá-lo com a pilha transbordando, e ele não funciona com chamadas recursivas. Você pode ver algumas soluções mais extravagantes em http://www.haskell.org/haskellwiki/Memoization .