折返緩存調用

Question

假設我們有一個IO動作如

lookupStuff :: InputType -> IO OutputType 

這可能是簡單的東西，如DNS查找，或對不隨時間變化數據的一些Web服務調用。

讓我們假設：

1. 操作不會拋出任何異常和/或從未發散

2. 如果不是爲IO單子，該功能將是純的，即結果對於相同的輸入參數總是相同的

3. 該操作是可重入的，即它可以安全地從多個線程同時調用。

4. lookupStuff操作相當（時間）昂貴。

我面臨的問題是如何正確（和W/O使用任何unsafe*IO*作弊）實現重入緩存中，可以從多個線程調用，組合多個查詢，對於相同的輸入參數整合成一個請求。

我想我是在類似於GHC的黑洞概念純粹的計算，但在IO「計算」的上下文。

什麼是指定問題的慣用Haskell/GHC解決方案？

Answer 1

是的，基本上是重新實現邏輯。雖然它與GHC已經做的很相似，但這是GHC的選擇。 Haskell可以在工作方式非常不同的虛擬機上實現，因此從這個意義上說，它尚未爲您完成。

但是，只需使用MVar (Map InputType OutputType)甚至IORef (Map InputType OutputType)（請確保使用atomicModifyIORef修改），並將緩存存儲在那裏。如果這個必要的解決方案看起來不對，那就是「如果不是爲了IO，這個函數就是純粹的」約束。如果它只是一個任意的動作，那麼你必須保持狀態才能知道執行或不執行的想法是非常自然的。問題是Haskell沒有「純IO」的類型（如果它依賴於數據庫，它在某些條件下表現得純粹，這與純粹的遺傳是不一樣的）。

import qualified Data.Map as Map 
import Control.Concurrent.MVar 

-- takes an IO function and returns a cached version 
cache :: (Ord a) => (a -> IO b) -> IO (a -> IO b) 
cache f = do 
    r <- newMVar Map.empty 
    return $ \x -> do 
     cacheMap <- takeMVar r 
     case Map.lookup x cacheMap of 
      Just y -> do 
       putMVar r cacheMap 
       return y 
      Nothing -> do 
       y <- f x 
       putMVar (Map.insert x y cacheMap) 
       return y 

是的它在裏面很醜。但在外面，看看！它就像純粹的記憶功能的類型，除了它有IO染上了它。

Answer 2

下面是一些代碼實現或多或少什麼，我在我原來的問題後：

import   Control.Concurrent 
import   Control.Exception 
import   Data.Either 
import   Data.Map   (Map) 
import qualified Data.Map   as Map 
import   Prelude   hiding (catch) 

-- |Memoizing wrapper for 'IO' actions 
memoizeIO :: Ord a => (a -> IO b) -> IO (a -> IO b) 
memoizeIO action = do 
    cache <- newMVar Map.empty 
    return $ memolup cache action 

    where 
    -- Lookup helper 
    memolup :: Ord a => MVar (Map a (Async b)) -> (a -> IO b) -> a -> IO b 
    memolup cache action' args = wait' =<< modifyMVar cache lup 
     where 
     lup tab = case Map.lookup args tab of 
      Just ares' -> 
      return (tab, ares') 
      Nothing -> do 
      ares' <- async $ action' args 
      return (Map.insert args ares' tab, ares') 

上面的代碼建立在西蒙·馬洛的Async抽象爲Tutorial: Parallel and Concurrent Programming in Haskell描述：

-- |Opaque type representing asynchronous results. 
data Async a = Async ThreadId (MVar (Either SomeException a)) 

-- |Construct 'Async' result. Can be waited on with 'wait'. 
async :: IO a -> IO (Async a) 
async io = do 
    var <- newEmptyMVar 
    tid <- forkIO ((do r <- io; putMVar var (Right r)) 
       `catch` \e -> putMVar var (Left e)) 
    return $ Async tid var 

-- |Extract value from asynchronous result. May block if result is not 
-- available yet. Exceptions are returned as 'Left' values. 
wait :: Async a -> IO (Either SomeException a) 
wait (Async _ m) = readMVar m 

-- |Version of 'wait' that raises exception. 
wait' :: Async a -> IO a 
wait' a = either throw return =<< wait a 

-- |Cancels asynchronous computation if not yet completed (non-blocking). 
cancel :: Async a -> IO() 
cancel (Async t _) = throwTo t ThreadKilled