记住有效的功能

Question

我开始研究一个将元胞自动机定义为局部转换函数的项目:

newtype Cellular g a = Cellular { delta :: (g -> a) -> a }

无论何时g是a Monoid,都可以通过在应用本地转换之前移动焦点来定义全局转换.这给了我们以下step功能:

step :: Monoid g => Cellular g a -> (g -> a) -> (g -> a)
step cell init g = delta cell $ init . (g <>)

现在,我们可以通过使用简单地运行自动机iterate.通过memo模仿每个步骤,我们可以节省很多(而且我确实意味着很多:它可以节省数小时)重新计算:

run :: (Monoid g, Memoizable g) => Cellular g a -> (g -> a) -> [g -> a]
run cell = iterate (memo . step cell)

我的问题是我推广Cellular到了CelluarT能够在本地规则中使用副作用(例如复制随机邻居):

newtype CellularT m g a = Cellular { delta :: (g -> m a) -> m a }

但是,我只想让效果运行一次,这样如果你多次询问一个单元格的值是多少,那么答案都是一致的.memo我们在这里失败了,因为它节省了有效的计算而不是结果.

如果不使用不安全的功能,我不希望这是可以实现的.我试图使用unsafePerformIOa IORef和a Map g a来存储已计算的值:

memoM :: (Ord k, Monad m) => (k -> m v) -> (k -> m v)
memoM =
  let ref = unsafePerformIO (newIORef empty) in
  ref `seq` loopM ref

loopM :: (Monad m, Ord k) => IORef (Map k v) -> (k -> m v) -> (k -> m v)
loopM ref f k =
  let m = unsafePerformIO (readIORef ref) in
  case Map.lookup k m of
    Just v  -> return v
    Nothing -> do
      v <- f k
      let upd = unsafePerformIO (writeIORef ref $ insert k v m)
      upd `seq` return v

但它以不可预测的方式运行:memoM putStrLn正确记忆,同时memoM (\ str -> getLine)尽管传递相同的参数,仍保持获取行.