5

セルオートマトンをローカル遷移関数として定義するプロジェクトに取り組み始めました。

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

gが であるときはいつでもMonoid、ローカル遷移を適用する前にフォーカスをシフトすることにより、グローバル遷移を定義できます。これにより、次のstep関数が得られます。

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

これで、 を使用してオートマトンを簡単に実行できますiterate。memoそして、各ステップを izing することで、再計算を大幅に節約できます (つまり、文字通り何時間も節約できます) 。

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 }

ただし、効果を 1 回だけ実行して、セルの値を複数回尋ねても、答えがすべて一致するようにしたいと考えています。結果ではなく有効な計算memoを保存するため、ここでは失敗します。

安全でない機能を使用しなければ、これが達成できるとは思えません。unsafePerformIO、 an 、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)

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

ほとんどの同時実行性を正しくするために、 an のMVar代わりに anを使用します。IORefこれは、パフォーマンスのためではなく、同時に使用される場合の正確さのためです。パフォーマンスについては、これよりも手の込んだものにすることができ、二重チェック ロックまたはより細かいロック粒度を持つ同時実行マップを使用します。

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。状態を渡しているだけです。どのモナドもトランスフォーマーを適用することでそれを行うことができるはずなのに、なぜ をいじる必要があるの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'))

それを実行して基礎となるモナドを取得するには、メモ化したい効果的な関数を提供する必要があります。

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

私たちMemoTはMapfor every 関数を使用しています。一部の関数は、別の方法でメモ化される場合があります。monad -memoパッケージには、特定の関数のメモ化を提供するモナド用のmtlスタイルのクラスと、必ずしもMaps を使用しないモナドを構築するためのより精巧なメカニズムがあります。

于 2015-09-11T15:52:22.360 に答える
0

まず、unsafePerformIO の使用をやめてください。その名前には理由があります。

あなたがやろうとしているのはメモ化ではなく、実際に内部モナドへの呼び出しを制御することです。手掛かりの一部は、Cellular はモナドではないため、CellularT はモナド変換子ではないということです。

あなたがする必要があると思うのは、セルごとに必要な効果を計算する純粋な関数を用意し、セルを反復処理して効果を順序付けることです。これにより、セルラー オートメトン メカニクス (既に持っていて見栄えの良いもの) が効果的なメカニクスから分離されます。現時点では、効果を計算すると同時に効果を実行しようとしているように見えますが、これが問題を引き起こしています。

エフェクトを入力フェーズと出力フェーズなどに分割する必要がある場合があります。あるいは、あなたの効果は実際には、各セルの各反復が結果を生成し、新しい入力を期待するステート マシンに似ているかもしれません。その場合、これを行う方法についてのいくつかのアイデアについては、私の質問 hereを参照してください。

于 2015-09-11T15:44:40.130 に答える