Come funzionano i dati.Memocombinatori?

https://stackoverflow.com/questions/4980102

12-11-2019
|

Domanda

Ho esaminato la fonte per Data.Memocombinator Ma non posso davvero vedere dove è il cuore.

Si prega di spiegare a me quale sia la logica dietro tutti questi combinatori e la meccanica di come effettivamente funzionano per accelerare il tuo programma nella programmazione del mondo reale.

Sto cercando specifiche per questa implementazione , e facoltativamente confronto / contrasto con altri approcci Haskell alla memoizzazione.Capisco quale memoizzazione è e sono non Alla ricerca di una descrizione di come funziona in generale.

Soluzione

Questa biblioteca è una combinatorizzazione semplice della ben nota tecnica della memoizzazione. Iniziamo con l'esempio canonico:

fib = (map fib' [0..] !!)
    where
    fib' 0 = 0
    fib' 1 = 1
    fib' n = fib (n-1) + fib (n-2)

Interpreto ciò che hai detto per significare che sai come e perché funziona. Quindi mi concentrerò sulla combinatorizzazione.

Stiamo essenzialmente cercando di catturare e generalizzare l'idea di (map f [0..] !!). Il tipo di questa funzione è (Int -> r) -> (Int -> r), che ha senso: prende una funzione da Int -> r e restituisce una versione memoizzata della stessa funzione. Qualsiasi funzione che è semanticamente l'identità e questo tipo è chiamato "Memoizer per Int" (anche id, che non è memorizzare). Generalizzate a questa astrazione:

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

Quindi un Memo a, un memoizer per a, prende una funzione da a a qualsiasi cosa e restituisce una funzione semanticamente identica che è stata memorizzata (o meno).

L'idea delle diverse memorizzatori è trovare un modo per enumerare il dominio con una struttura dati, mappare la funzione su di esse, quindi indicizzare la struttura dei dati. bool è un buon esempio:

bool :: Memo Bool
bool f = table (f True, f False)
    where
    table (t,f) True = t
    table (t,f) False = f

Le funzioni da Bool sono equivalenti a coppie, ad eccezione di una coppia valuteremo solo ciascun componente (come nel caso di ogni valore che si verifica al di fuori di un lambda). Quindi mappelliamo su una coppia e ritorno. Il punto essenziale è che stiamo sollevando la valutazione della funzione sopra la Lambda per l'argomento (qui l'ultima argomentazione di table) enumerando il dominio.

Memorizzazione Maybe a è una storia simile, ad eccezione di ora dobbiamo sapere come memorizzare la memorizzazione di a per il caso Just. Quindi il memoizer per Maybe prende un memorizzatore per a come argomento:

maybe :: Memo a -> Memo (Maybe a)
maybe ma f = table (f Nothing, ma (f . Just))
    where
    table (n,j) Nothing = n
    table (n,j) (Just x) = j x

Il resto della biblioteca è solo variazioni su questo tema.

Il modo in cui memorizza i tipi di integrali utilizza una struttura più appropriata rispetto a [0..]. È un po 'coinvolto, ma fondamentalmente crea un albero infinito (che rappresenta i numeri in binari a chiarire la struttura):

Così che la ricerca di un numero nell'albero abbia tempo di esecuzione proporzionale al numero di bit nella sua rappresentazione.

AS SCLV sottolinea, la Biblioteca Memotrie di Conal utilizza la stessa tecnica sottostante, ma utilizza una presentazione di typeclass anziché una presentazione di combinatori. Abbiamo rilasciato le nostre biblioteche in modo indipendente allo stesso tempo (anzi, entro un paio d'ore!). Conal's è più facile da usare in casi semplici (esiste una sola funzione, memo e determinerà la struttura del memo da utilizzare in base al tipo), mentre il mio è più flessibile, come puoi fare cose come questa:

boundedMemo :: Integer -> Memo Integer
boundedMemo bound f = \z -> if z < bound then memof z else f z
   where
   memof = integral f

che memorizza solo i valori meno di un dato limite, necessario per l'implementazione di uno dei problemi di Project Euler.

Ci sono altri approcci, ad esempio esporre una funzione Apri Fixpoint su una monaca:

memo :: MonadState ... m => ((Integer -> m r) -> (Integer -> m r)) -> m (Integer -> m r)

che consente ancora più flessibilità, ad esempio. Purging cache, LRU, ecc. Ma è un dolore nel culo da usare, e inoltre mette in atto vincoli di rigore sulla funzione da memorizzare (ad esempio una ricorsione a sinistra infinita). Non credo che ci siano librerie che implementano questa tecnica.

ha risposto di ciò che sei stato curioso? In caso contrario, forse rendono esplicito i punti di cui sei confuso?

Altri suggerimenti

Il cuore è la funzione bits:

-- | Memoize an ordered type with a bits instance.
bits :: (Ord a, Bits a) => Memo a
bits f = IntTrie.apply (fmap f IntTrie.identity)

È l'unica funzione (eccetto il banale unit :: Memo ()) che può darti un valore Memo a. Usa la stessa idea come in questo pagina sulla memoizzazione haskell. La sezione 2 mostra la più semplice strategia di memorizzazione utilizzando un elenco e la sezione 3 fa lo stesso usando un albero binario di naturali simile al IntTree utilizzato nei memostoni.

L'idea di base è quella di utilizzare una costruzione come (map fib [0 ..] !!) o nel caso di MemoCombinars - IntTrie.apply (fmap f IntTrie.identity). La cosa da notare qui è la corrispondenza tra IntTie.apply e !! e anche tra IntTrie.identity e [0..].

Il passo successivo è la memorizzazione delle funzioni con altri tipi di argomenti. Questo viene fatto con la funzione wrap che utilizza un isomorfismo tra tipi a e b per costruire un Memo b da un Memo a. Ad esempio:

Memo.integral f
=>
wrap fromInteger toInteger bits f
=>
bits (f . fromInteger) . toInteger
=>
IntTrie.apply (fmap (f . fromInteger) IntTrie.identity) . toInteger
~> (semantically equivalent)
(map (f . fromInteger) [0..] !!) . toInteger

Il resto del codice sorgente riguarda i tipi come l'elenco, forse, sia memorizzando più argomenti.

Alcuni lavori sono fatti da inttrie: http://hackage.haskell .org / package / data-inttrie-0.0.4

La biblioteca di Luke è una variazione della Biblioteca Memotrie di Cona, che ha descritto qui: http://conal.net/blog/posts/elegant-memoization-with-functional-memo-tries/

Un'ulteriore espansione: la nozione generale dietro la memorizzazione funzionale è quella di prendere una funzione da a -> b e mapparla su una tappa di dati indicizzata da tutti i valori possibili dei valori a e contenenti valori di b. Tale datastruttura dovrebbe essere pigra in due modi - prima dovrebbe essere pigro nei valori che detiene. In secondo luogo, dovrebbe essere prodotto pigramente. Il primo è per impostazione predefinita in una lingua fondamentale. Quest'ultimo è compiuto utilizzando tentativi generalizzati.

I vari approcci di Memonombinatori, Memotrie, ecc. Sono tutti solo modi per creare composizioni di pezzi di tentativi sui singoli tipi di tastieri per consentire la semplice costruzione di tentativi per strutture sempre più complesse.

@Luqui Una cosa che non è chiara per me: ha lo stesso comportamento operativo come quanto segue:

fib :: [Int]
fib = map fib' [0..]
    where fib' 0 = 0
             fib' 1 = 1
             fib' n = fib!!(n-1) + fib!!(n-2)

Quanto sopra dovrebbe memorizzare FIB al livello superiore, e quindi se si definisce due funzioni:

f n = fib!!n + fib!!(n+1)

Se poi calcolamo f 5 , otteniamo che fib 5 non è ricomput durante il calcolo fib 6 .Non mi è chiaro se i combinatori di memorizzazione hanno lo stesso comportamento (cioè la memorizzazione di alto livello invece di proibire solo la ricomputazione "all'interno" il calcolo del fib) e, in caso affermativo, perché esattamente?

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow