6

次のような IO アクションがあるとします。

lookupStuff :: InputType -> IO OutputType

これは、DNS ルックアップや、時不変データに対する Web サービス呼び出しなどの単純なものである可能性があります。

次のように仮定します。

  1. 操作は例外をスローしたり、発散したりしません。

  2. モナドがなければIO、関数は純粋になります。つまり、同じ入力パラメータに対して結果は常に同じになります。

  3. アクションは再入可能です。つまり、複数のスレッドから同時に安全に呼び出すことができます。

  4. このlookupStuff操作にはかなりの (時間) 費用がかかります。

私が直面している問題はunsafe*IO*、複数のスレッドから呼び出すことができる再入可能キャッシュを適切に (そしてチートを使用せずに) 実装し、同じ入力パラメーターに対する複数のクエリを単一の要求に結合する方法です。

私は、純粋な計算のための GHC のブラックホールの概念に似たものを求めていると思いますが、IO の「計算」のコンテキストにあります。

上記の問題に対する慣用的な Haskell/GHC ソリューションは何ですか?

4

2 に答える 2

4

ええ、基本的にロジックを再実装します。GHC がすでに行っていることと似ているように見えますが、それが GHC の選択です。Haskell は、まったく異なる動作をする VM に実装できるため、その意味では、まだ実装されていません。

しかし、ええ、MVar (Map InputType OutputType)またはを使用してIORef (Map InputType OutputType)（必ず で変更してくださいatomicModifyIORef）、そこにキャッシュを保存するだけです。この命令的な解決策が間違っていると思われる場合、それは「 がなければIO、この関数は純粋だろう」という制約です。それが恣意的な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全体が汚れていることを除けば、純粋なメモ化関数のタイプと同じです。

于 2011-03-30T15:44:45.243 に答える
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')

上記のコードは、 Tutorial: Parallel and Concurrent Programming in Haskell で説明されているSimon Marlow のAsync抽象化に基づいています。

-- |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
于 2011-06-21T11:01:58.200 に答える