Come si crea una funzione di memoize generica in Haskell?

Question

Ho visto l'altro post su questo , ma esiste un modo chiaro per farlo in Haskell?

Come seconda parte, può essere fatto anche senza rendere monadica la funzione?

Answer 1

Ciò segue in gran parte http://www.haskell.org/haskellwiki/Memoization .

Vuoi una funzione di tipo (a - > b). Se non si chiama se stesso, allora puoi semplicemente scrivere un semplice wrapper che memorizza nella cache i valori restituiti. Il il modo migliore per archiviare questa mappatura dipende da quali proprietà puoi sfruttare. Ordinare è praticamente un minimo. Con numeri interi puoi costruire un infinito elenco o albero pigro contenente i valori.

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

Quindi, supponiamo che sia ricorsivo. Quindi ti serve non chiamare se stesso, ma la versione memorizzata, quindi passala invece:

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

La versione memorizzata è, ovviamente, ciò che stiamo cercando di definire.

Ma possiamo iniziare creando una funzione che memorizza nella cache i suoi input:

Potremmo costruire un livello passando una funzione che crea un struttura che memorizza nella cache i valori. Tranne che dobbiamo creare la versione di f che ha già passato la funzione cache.

Grazie alla pigrizia, questo non è un problema:

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

allora tutto ciò che serve è usarlo:

exposed_f = memoize cacher_for_f f

L'articolo fornisce suggerimenti su come utilizzare una classe di tipi selezionando su input per la funzione per fare quanto sopra, piuttosto che scegliere un esplicito funzione di memorizzazione nella cache. Questo può essere davvero bello, piuttosto che esplicitamente costruendo una cache per ogni combinazione di tipi di input, possiamo implicitamente combina le cache per i tipi aeb in una cache per una funzione che prende a e b.

Un'ultima avvertenza: l'uso di questa tecnica pigra significa che la cache non si restringe mai, cresce solo. Se invece usi la monade IO, puoi gestirla, ma farlo saggiamente dipende dai modelli di utilizzo.

Answer 2

Il pacchetto di dati-memocombinator su hackage fornisce molte routine di memoization riutilizzabili. L'idea di base è:

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

vale a dire. può memorizzare qualsiasi funzione da a. Il modulo fornisce quindi alcune primitive (come unit :: Memo () e integral :: Memo Int ) e combinatori per la creazione di tabelle memo più complesse (come la coppia :: Memo a - > Memo b - > Memo (a, b) e list :: Memo a - > Memo [a] ).

Answer 3

Puoi modificare la soluzione di Jonathan con unsafePerformIO per creare un "puro" memorizzazione della versione della tua funzione.

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

Funzionerà con le funzioni ricorsive:

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

Anche se questo esempio è una funzione con un parametro intero, il tipo di memoize ci dice che può essere usato con qualsiasi funzione che assume un tipo comparabile. Se hai una funzione con più di un parametro, raggruppali in una tupla prima di applicare memoize. F.i:.

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

f_memo = curry (memoize (uncurry f))

Answer 4

Facendo una traduzione diretta dalle lingue più imperative, ho pensato a questo.

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

Ma questo è in qualche modo insoddisfacente. Inoltre, Data.Map vincola il parametro deve essere un'istanza di Ord .

Answer 5

Se i tuoi argomenti saranno numeri naturali, puoi semplicemente fare:

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

Tuttavia, ciò non ti aiuta davvero con lo stack traboccante e non funziona con le chiamate ricorsive. Puoi trovare alcune soluzioni più elaborate su http://www.haskell.org/haskellwiki/Memoization .