5

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

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在这里失败了，因为它保存了有效的计算而不是它的结果。

如果不使用不安全的功能，我不希望这是可以实现的。我尝试使用unsafePerformIO、 anIORef和 aMap 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)继续获取行，尽管传递给它的参数相同。

4

2 回答 2

2

如果你给自己一个机会来分配引用来保存地图，这可以安全地实现。

import Control.Monad.IO.Class

memoM :: (Ord k, MonadIO m) => (k -> m v) -> m (k -> m v)
                 |                           |
                 |        opportunity to allocate the map
                 get to IO correctly

我将使用 anMVar而不是 anIORef来获得正确的大部分并发性。这是为了正确性，以防它同时使用，而不是为了性能。对于性能，我们可能会比这更好，并使用双重检查锁或具有更精细锁粒度的并发映射。

import Control.Concurrent    
import Control.Monad.IO.Class    
import qualified Data.Map as Map

memoM :: (Ord k, Monad m, MonadIO m) => (k -> m v) -> m (k -> m v)
memoM once = do 
    mapVar <- liftIO $ newMVar Map.empty    
    return (\k -> inMVar mapVar (lookupInsertM once k))

-- like withMVar, but isn't exception safe   
inMVar :: (MonadIO m) => MVar a -> (a -> m (a, b)) -> m b
inMVar mvar step = do
    (a, b) <- liftIO (takeMVar mvar) >>= step
    liftIO $ putMVar mvar a
    return b

lookupInsertM :: (Ord k, Monad m) => (k -> m v) -> k -> Map.Map k v -> m (Map.Map k v, v)
lookupInsertM once k map = 
    case Map.lookup k map of
        Just v -> return (map, v)
        Nothing -> do
            v <- once k
            return (Map.insert k v map, v)

我们并没有真正使用IO，我们只是在传递状态。任何 monad 都应该能够通过对其应用变压器来做到这一点，那么我们为什么要在IO. 这是因为我们希望能够分配这些映射，以便memoM可以用于多个不同的功能。如果我们只关心单个记忆的有效函数，我们可以只使用状态转换器。

{-# LANGUAGE GeneralizedNewtypeDeriving #-}

import Control.Applicative
import Control.Monad.Trans.Class
import Control.Monad.Trans.State

newtype MemoT k v m a = MemoT {getMemoT :: StateT (k -> m v, Map.Map k v) m a}
    deriving (Functor, Applicative, Monad, MonadIO)

instance MonadTrans (MemoT k v) where
    lift = MemoT . lift

这个转换器增加了从记忆的有效函数中查找值的能力

lookupMemoT :: (Ord k, Monad m) => k -> MemoT k v m v
lookupMemoT k = MemoT . StateT $ \(once, map) -> do
                                                    (map', v) <- lookupInsertM once k map
                                                    return (v, (once, map'))

为了运行它并获得底层的 monad，我们需要提供我们想要记忆的有效函数。

runMemoT :: (Monad m) => MemoT k v m a -> (k -> m v) -> m a
runMemoT memo once = evalStateT (getMemoT memo) (once, Map.empty)

我们对每个函数都MemoT使用 a Map。某些功能可能会以其他方式记忆。monad-memo包有一个mtl风格的monad 类，它为特定函数提供 memoization，以及一个更精细的机制来构建它们，不一定使用Maps。

于 2015-09-11T15:52:22.360 回答
0

首先，停止尝试使用 unsafePerformIO。它有这个名字是有原因的。

你试图做的不是记忆，它实际上控制对内部单子的调用。部分线索是 Cellular 不是单子，因此 CellularT 不是单子转换器。

我认为您需要做的是有一个纯函数来计算每个单元格所需的效果，然后遍历单元格以对效果进行排序。这将您的细胞自动机机制（您已经拥有，并且看起来不错）与您的有效机制分开。目前，您似乎正在尝试在计算效果的同时执行效果，这导致了您的问题。

可能是您的效果需要拆分为输入阶段和输出阶段，或类似的东西。或者，您的效果实际上更像是一个状态机，其中每个单元的每次迭代都会产生一个结果并期望一个新的输入。在这种情况下，请参阅我的问题，了解有关如何执行此操作的一些想法。

于 2015-09-11T15:44:40.130 回答