可重入缓存"引用透明"的IO调用

Question

假设我们有一个IO动作,如

lookupStuff :: InputType -> IO OutputType

这可能是简单的东西,如DNS查找,或一些针对时间不变数据的Web服务调用.

我们假设:

1. 该操作从不抛出任何异常和/或从不发散

2. 如果不是IOmonad,则函数将是纯函数,即对于相等的输入参数,结果总是相同的

3. 该操作是可重入的,即可以安全地同时从多个线程调用它.

4. 该lookupStuff操作非常(时间)昂贵.

我面临的问题是如何正确(并且不使用任何unsafe*IO*作弊)实现可以从多个线程调用的可重入缓存,并将针对相同输入参数的多个查询合并为单个请求.

我想我正在追求类似于GHC的黑洞概念,用于纯计算,但在IO"计算"环境中.

对于所述问题,什么是惯用的Haskell/GHC解决方案？

Answer 1

是的，基本上重新实现逻辑。虽然这看起来与 GHC 已经在做的事情相似，但这是 GHC 的选择。Haskell 可以在工作方式非常不同的虚拟机上实现，因此从这个意义上说，它还没有为您完成。

但是，是的，只需使用 anMVar (Map InputType OutputType)或什至 an IORef (Map InputType OutputType)（确保使用 进行修改atomicModifyIORef），然后将缓存存储在那里。如果这个命令式解决方案看起来是错误的，那就是“如果不是IO，这个函数将是纯函数”约束。如果这只是一个任意IO操作，那么您必须保持状态才能知道执行或不执行什么的想法似乎是非常自然的。问题是 Haskell 没有“纯 IO”类型（如果它依赖于数据库，那么它只是在某些条件下表现为纯 IO，这与遗传纯 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弄脏了。