5

私には機能があります

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

これは何らかの入力を受け取り、出力を生成する IO 計算を返します。fこれらの計算を入力ごとに 1 回だけ実行するように、「メモ化」したいと考えています。たとえば、

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

memoize次に、そのような関数が必要です

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

は 1 回だけ出力"hello world"して を返します("world", "world")。私が書いているプログラムはマルチスレッドであるため、異なるスレッドがすべて呼び出している場合でも、このプロパティは保持されるはずmfです。

以下は、私がこれまでに思いついた（ひどい）解決策です。私の質問は、それを改善できるかどうか、そしてどのように改善できるかです。

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

ここでいくつかのことが起こっています：

1)cacheタイプ を持っていTVar (Map a (TMVar (Maybe b)))ます。TMVar入力を、計算された値またはNothing(値がまだ計算されていないことを示す)を含むにマップします。この関数lookupInsertは を検査し、まだ存在しない場合は に初期化されcacheた新しい を挿入します。TMVarNothing

2) 返されたアクションは、最初にv :: TMVar (Maybe b)関連付けられた to を取得しa、次にそれを受け取り、計算f aを実行して結果を取得するか、利用可能な場合は に格納されている値を返しMaybeます。これtakeとパターンは、まだ実行されていないことを確認した後put、2 つの異なるスレッドが両方とも計算を実行しないようにするためのものです。f a

4

1 に答える 1

1

あなたが望んでいることは不可能だと思っていましたが、そうであることがわかりました。

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

なぜそれが機能するのか、私はまだ理解できません！

于 2013-04-11T00:16:15.180 に答える