Memoizing una funzione effectful

Question

ho iniziato a lavorare su un progetto che definisce un automa cellulare come una funzione di transizione locale:

newtype Cellular g a = Cellular { delta :: (g -> a) -> a } 

Ogni volta g è un Monoid, è possibile definire una transizione globale spostando l'attenzione prima di applicare la transizione locale. Questo ci dà la step seguente funzione:

step :: Monoid g => Cellular g a -> (g -> a) -> (g -> a) 
step cell init g = delta cell $ init . (g <>) 

Ora, possiamo semplicemente eseguire l'automa utilizzando iterate. E siamo in grado di risparmiare molto (e intendo molto: fa risparmiare letteralmente ore) di ri-calcoli da memo izing ognuno dei passaggi:

run :: (Monoid g, Memoizable g) => Cellular g a -> (g -> a) -> [g -> a] 
run cell = iterate (memo . step cell) 

mio problema è che ho generalizzato Cellular-CelluarT in modo che sarei in grado di utilizzare gli effetti collaterali nelle regole locali (ad esempio la copia di un vicino di casa casuale):

newtype CellularT m g a = Cellular { delta :: (g -> m a) -> m a } 

Tuttavia, voglio solo gli effetti per essere eseguito volta in modo che se si chiede una cella più volte quello che il suo valore è, le risposte sono tutte coerenti. memo ci fallisce qui perché salva il calcolo efficace piuttosto che il suo risultato.

Non mi aspetto che ciò sia possibile senza utilizzare funzioni non sicure. Ho cercato di avere un andare a esso utilizzando unsafePerformIO, un IORef e un Map g a per memorizzare i valori già calcolati:

memoM :: (Ord k, Monad m) => (k -> m v) -> (k -> m v) 
memoM = 
    let ref = unsafePerformIO (newIORef empty) in 
    ref `seq` loopM ref 

loopM :: (Monad m, Ord k) => IORef (Map k v) -> (k -> m v) -> (k -> m v) 
loopM ref f k = 
    let m = unsafePerformIO (readIORef ref) in 
    case Map.lookup k m of 
    Just v -> return v 
    Nothing -> do 
     v <- f k 
     let upd = unsafePerformIO (writeIORef ref $ insert k v m) 
     upd `seq` return v 

Ma si comporta in modo imprevedibile: memoM putStrLn sia correttamente memoized mentre memoM (\ str -> getLine) mantiene le linee che vanno a prendere, nonostante il lo stesso argomento è passato ad esso.

Answer 1

Per prima cosa, smettere di provare a utilizzare unsafePerformIO. Ha quel nome per una ragione.

Quello che stai cercando di fare non è la memo- razione, in realtà controlla le chiamate alla monade interiore. Parte del fatto è che Cellular non è una monade, quindi CellularT non è un trasformatore monade.

Quello che penso che devi fare è avere una funzione pura che calcoli l'effetto richiesto per cella, e quindi scorrere le celle per sequenziare gli effetti. Questo separa la meccanica del tuo autometo cellulare (che hai già, e che ha un bell'aspetto) dalla tua meccanica efficace. Al momento sembra che tu stia cercando di eseguire gli effetti nello stesso momento in cui li stai calcolando, il che sta portando ai tuoi problemi.

È possibile che i tuoi effetti debbano essere suddivisi in una fase di input e una fase di output, o qualcosa del genere. O forse i tuoi effetti sono in realtà più simili a una macchina a stati in cui ogni iterazione di ciascuna cella produce un risultato e si aspetta un nuovo input. In tal caso, vedere my question here per alcune idee su come eseguire questa operazione.

Answer 2

Questo può essere ottenuto in modo sicuro se ti dai l'opportunità di assegnare il riferimento per mantenere la mappa.

import Control.Monad.IO.Class 

memoM :: (Ord k, MonadIO m) => (k -> m v) -> m (k -> m v) 
       |       | 
       |  opportunity to allocate the map 
       get to IO correctly 

ho intenzione di utilizzare un MVar invece di un IORef per ottenere la maggior parte di concorrenza corretta.Questo è per la correttezza, nel caso sia usato contemporaneamente, non per le prestazioni. Per le prestazioni, potremmo essere più fanatici di questo e utilizzare i blocchi a doppio controllo o una mappa simultanea con granularità di blocco più fine.

import Control.Concurrent  
import Control.Monad.IO.Class  
import qualified Data.Map as Map 

memoM :: (Ord k, Monad m, MonadIO m) => (k -> m v) -> m (k -> m v) 
memoM once = do 
    mapVar <- liftIO $ newMVar Map.empty  
    return (\k -> inMVar mapVar (lookupInsertM once k)) 

-- like withMVar, but isn't exception safe 
inMVar :: (MonadIO m) => MVar a -> (a -> m (a, b)) -> m b 
inMVar mvar step = do 
    (a, b) <- liftIO (takeMVar mvar) >>= step 
    liftIO $ putMVar mvar a 
    return b 

lookupInsertM :: (Ord k, Monad m) => (k -> m v) -> k -> Map.Map k v -> m (Map.Map k v, v) 
lookupInsertM once k map = 
    case Map.lookup k map of 
     Just v -> return (map, v) 
     Nothing -> do 
      v <- once k 
      return (Map.insert k v map, v) 

Noi non siamo molto usare IO, stiamo solo passando intorno Stato. Qualsiasi monade dovrebbe essere in grado di farlo con un trasformatore ad esso applicato, quindi perché stiamo parlando di roba in IO? È perché vogliamo essere in grado di allocare tali mappe in modo che memoM possa essere utilizzato per più di una funzione diversa. Se ci interessa solo una singola funzione efficace memoizzata, possiamo semplicemente usare un trasformatore di stato.

{-# LANGUAGE GeneralizedNewtypeDeriving #-} 

import Control.Applicative 
import Control.Monad.Trans.Class 
import Control.Monad.Trans.State 

newtype MemoT k v m a = MemoT {getMemoT :: StateT (k -> m v, Map.Map k v) m a} 
    deriving (Functor, Applicative, Monad, MonadIO) 

instance MonadTrans (MemoT k v) where 
    lift = MemoT . lift 

Questo trasformatore aggiunge la possibilità di ricercare un valore dalla funzione effectful memoized

lookupMemoT :: (Ord k, Monad m) => k -> MemoT k v m v 
lookupMemoT k = MemoT . StateT $ \(once, map) -> do 
                (map', v) <- lookupInsertM once k map 
                return (v, (once, map')) 

per farlo funzionare e ottenere alla monade sottostante, abbiamo bisogno di fornire la funzione effectful vogliamo Memoize.

runMemoT :: (Monad m) => MemoT k v m a -> (k -> m v) -> m a 
runMemoT memo once = evalStateT (getMemoT memo) (once, Map.empty) 

nostra MemoT utilizza un Map per ogni funzione. Alcune funzioni potrebbero essere memorizzate in un altro modo. Il pacchetto monad-memo ha una classe in stile mtl per le monadi che forniscono la memoizzazione per una funzione specifica e un meccanismo più elaborato per la loro creazione che non utilizza necessariamente i valori Map s.