Memoizing IO Obliczenia Haskell

Question

mam funkcji

f :: MonadIO m => a -> m b 

który trwa jakieś dane wejściowe i zwraca obliczenia IO, co da wynik. Chcę "zapamiętać" f, aby wykonać te obliczenia tylko raz dla każdego wejścia. Na przykład, jeśli

f :: String -> IO String 
f s = putStrLn ("hello " ++ s) >> return s 

potem chcę funkcję memoize takie, że

do 
    mf <- memoize f 
    s <- mf "world" 
    t <- mf "world" 
    return (s,t) 

wydruki "hello world" dokładnie raz i wraca ("world", "world"). Program, który piszę, jest wielowątkowy, więc ta właściwość powinna się utrzymywać, nawet jeśli różne wątki wywołują mf.

Poniżej znajduje się (straszne) rozwiązanie, które do tej pory wymyśliłem. Moje pytanie brzmi: czy i jak można to poprawić.

memoize :: (MonadIO m, Ord a) => (a -> m b) -> m (a -> m b) 
memoize f = do 
    cache <- liftIO $ newTVarIO Map.empty 
    return $ \a -> do 
       v <- liftIO $ atomically $ lookupInsert cache a 
       b <- maybe (f a) return =<< liftIO (atomically $ takeTMVar v) 
       liftIO $ atomically $ putTMVar v $ Just b 
       return b 
    where 
     lookupInsert :: Ord a => TVar (Map a (TMVar (Maybe b))) -> a -> STM (TMVar (Maybe b)) 
     lookupInsert cache a = do 
         mv <- Map.lookup a <$> readTVar cache 
         case mv of 
          Just v -> return v 
          Nothing -> do 
            v <- newTMVar Nothing 
            modifyTVar cache (Map.insert a v) 
            return v 

Istnieje kilka rzeczy dzieje się tutaj:

1) cache ma typ TVar (Map a (TMVar (Maybe b))). Mapuje dane wejściowe na wartości TMVar, które zawierają albo wartość obliczoną, albo Nothing (co wskazuje, że wartość nie została jeszcze obliczona). Funkcja lookupInsert sprawdza cache i wstawia nową TMVar zainicjowaną na Nothing, jeśli żadna z nich już nie istnieje.

2) zwrócone pierwsze działanie uzyskuje informacje v :: TMVar (Maybe b) powiązany a, a następnie wykonuje się i albo wykonuje obliczenia f a do uzyskania efektu lub zwraca wartość przechowywaną w Maybe, jeśli są dostępne. Wzorzec take i put jest taki, że dwa różne wątki nie uruchamiają obliczeń po stwierdzeniu, że nie zostały jeszcze uruchomione.

Answer 1

Myślałem, że to, co chciałeś, było niemożliwe, ale okazało się, że tak.

https://stackoverflow.com/a/9458721/1798971

Wciąż nie mogę zrozumieć, dlaczego to działa!