I have a function
f :: MonadIO m => a -> m b
which takes some input and returns an input-output calculation that will give an output. I want to "memoize" fso that I only ever do this calculation once for each input. For example, if
f :: String -> IO String
f s = putStrLn ("hello " ++ s) >> return s
I need a function memoizesuch that
do
mf <- memoize f
s <- mf "world"
t <- mf "world"
return (s,t)
prints "hello world"exactly once and returns ("world", "world"). The program I am writing is multi-threaded, so this property should be executed even if different threads call it mf.
Below is a (terrible) solution that I have come up with so far. My question is whether and how to improve it.
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
There are a few things here:
1) cache TVar (Map a (TMVar (Maybe b))). TMVar, , Nothing ( , ). lookupInsert cache TMVar, Nothing, .
2) v :: TMVar (Maybe b), a, f a , Maybe, . take put , f a, , .