Haskell: parzialmente rilasciato risultati pigro valutato

Question

Ho un albero decisionale molto grande. Viene utilizzato nel modo seguente:

-- once per application start 
t :: Tree 
t = buildDecisionTree 
-- done several times 
makeDecision :: Something -> Decision 
makeDecision something = search t something 

Questo albero delle decisioni è troppo grande per adattarsi alla memoria. Ma, grazie alla valutazione pigra, è solo parzialmente valutata.

Il problema è che ci sono scenari in cui tutte le decisioni possibili vengono provate causando la valutazione dell'intero albero. Questo non finirà, ma non dovrebbe causare un overflow di memoria. Inoltre, se questo processo viene interrotto, l'utilizzo della memoria non diminuisce, poiché un'enorme sottostruttura viene ancora valutata.

Una soluzione consiste nel rivalutare l'albero ogni volta che viene chiamato makeDecision, ma ciò perderebbe i vantaggi delle decisioni di memorizzazione nella cache e rallenterebbe significativamente makeDecision.

Mi piacerebbe fare un corso di mezzo. In particolare, è molto comune nella mia applicazione prendere decisioni successive con il prefisso del percorso comune nell'albero. Quindi vorrei memorizzare nell'ultimo percorso utilizzato, ma lasciare cadere gli altri, facendoli rivalutare la prossima volta che vengono utilizzati. Come posso farlo in Haskell?

Answer 1

Non è possibile in puro haskell, vedere domanda Can a thunk be duplicated to improve memory performance? (come indicato da @shang). Puoi, tuttavia, farlo con IO.

Iniziamo con il modulo heade ed elenciamo solo il tipo e le funzioni che dovrebbero rendere sicuro questo modulo (che userà unsafePerformIO). È anche possibile farlo senza unsafePerformIO, ma ciò significherebbe che l'utente deve conservare più del suo codice in IO.

{-# LANGUAGE ExistentialQuantification #-} 
module ReEval (ReEval, newReEval, readReEval, resetReEval) where 

import Data.IORef 
import System.IO.Unsafe 

Iniziamo definendo un tipo di dati che memorizza un valore in un modo che impedisce la condivisione tutto, mantenendo la funzione e l'argomento distanti, e si applicano solo la funzione quando vogliamo il valore. Si noti che il valore restituito da unsharedValuepuò essere condivisi, ma non con il valore di ritorno di altre invocazioni (assumendo che la funzione sta facendo qualcosa di non banale):

data Unshared a = forall b. Unshared (b -> a) b 

unsharedValue :: Unshared a -> a 
unsharedValue (Unshared f x) = f x 

Ora definiamo il nostro tipo di dati di calcoli ripristinabili . Abbiamo bisogno di memorizzare il calcolo e il valore corrente. Quest'ultimo è memorizzato in un IORef, in quanto vogliamo poterlo resettare.

data ReEval a = ReEval { 
    calculation :: Unshared a, 
    currentValue :: IORef a 
    } 

di avvolgere un valore in una casella ReEval, abbiamo bisogno di avere una funzione e un argomento. Perché non solo a -> ReEval a? Perché allora non ci sarebbe modo di impedire la condivisione del parametro.

newReEval :: (b -> a) -> b -> ReEval a 
newReEval f x = unsafePerformIO $ do 
    let c = Unshared f x 
    ref <- newIORef (unsharedValue c) 
    return $ ReEval c ref 

La lettura è semplice: basta ottenere il valore dal IORef. Questo uso di unsafePerformIO è sicuro perché otterremo sempre il valore di unsharedValue c, anche se una diversa "copia" di esso.

readReEval :: ReEval a -> a 
readReEval r = unsafePerformIO $ readIORef (currentValue r) 

E infine il ripristino. L'ho lasciato nella monade IO, non perché sarebbe meno sicuro rispetto all'altra funzione da incapsulare in unsafePerformIO, ma poiché questo è il modo più semplice per dare all'utente il controllo su quando avviene effettivamente il reset.Non si vuole rischiare che tutte le chiamate a resetReEval vengano ritardate pigramente finché la memoria non è esaurita o addirittura ottimizzata perché non vi è alcun valore di ritorno da utilizzare.

resetReEval :: ReEval a -> IO() 
resetReEval r = writeIORef (currentValue r) (unsharedValue (calculation r)) 

Questa è la fine del modulo. Ecco codice di esempio:

import Debug.Trace 
import ReEval 
main = do 
    let func a = trace ("func " ++ show a) negate a 
    let l = [ newReEval func n | n <- [1..5] ] 
    print (map readReEval l) 
    print (map readReEval l) 
    mapM_ resetReEval l 
    print (map readReEval l) 

E qui si può vedere che fa quello previsto:

$ runhaskell test.hs 
func 1 
func 2 
func 3 
func 4 
func 5 
[-1,-2,-3,-4,-5] 
[-1,-2,-3,-4,-5] 
func 1 
func 2 
func 3 
func 4 
func 5 
[-1,-2,-3,-4,-5]