被困在州Monad

Question

我想使用节点和唯一键的IntMap创建图形结构.这里和这里已经很好地介绍了这个主题.我理解状态monad是如何工作的,基本上将状态函数 - >(val,state)包装在newtype中,这样我们就可以为它创建一个monad实例.我已经阅读了很多相关主题.我仍然无法理解如何在程序执行过程中获得唯一(或仅增量)值.获得一系列连续的ID很容易,但是一旦我"runState"退出monad,似乎我回到了我开始跟踪当前ID的位置.我觉得我被卡在了monad中.我考虑的另一个选择是保持整个IntMap和当前"下一个"ID作为状态,但这似乎非常"必要"和极端.这个问题非常相似,但没有得到很多答案(或者我可能只是错过了一些明显的答案).在程序执行过程中利用状态monad获取唯一ID的惯用方法是什么？谢谢.

Answer 1

让我们想象一下,我们是为了IO让Statemonad 成为现实.那会是什么样的？我们纯粹的Statemonad只是一个新类型:

s -> (a, s)

好吧,IO在返回最终值之前,版本可能会产生一些副作用,如下所示:

s -> IO (a, s)

这种模式很常见,它有一个名字,具体来说StateT:

newtype StateT s m a = StateT { runStateT :: s -> m (a, s) }

这个名字T最后是因为它是monad T变形金刚.我们称之为m"基地monad"和StateT s m"变形"monad.

StateT s m只是一个Monadif m是一个Monad:

instance (Monad m) => Monad (StateT s m) where {- great exercise -}

但是,除此之外,所有monad变换器都实现了MonadTrans类,定义如下:

class MonadTrans t where
    lift :: (Monad m) => m a -> t m a

instance MonadTrans (StateT s) where {- great exercise -}

如果t是StateT s,则该lift类型专门用于:

lift :: m a -> StateT s m a

换句话说,它让我们"提升"基础monad中的一个动作,成为变形monad中的一个动作.

因此,对于您的特定问题,你想要的StateT (IntMap k v) IO单子,延伸IO与附加State.然后你可以在这个monad中编写你的整个程序:

main = flip runStateT (initialState :: IntMap k v) $ do
    m <- get        -- retrieve the map
    lift $ print m  -- lift an IO action
    (k, v) <- lift readLn
    put (insert k v m)

请注意,我仍然使用get和put.这是因为transformers包实现我所描述的所有概念,它概括的签名get,并put为:

get :: (Monad m) => StateT s m s
put :: (Monad m) => s -> StateT s m ()

这意味着他们自动在其中工作StateT. transformers然后定义State为:

type State s = StateT s Identity

这意味着,你可以使用get和put两个State和StateT.

要了解有关monad变压器的更多信息,我强烈推荐Monad变压器 - 一步一步.