8

我想使用节点和唯一键的 IntMap 创建图形结构。这个话题在这里和这里已经很好地涵盖了. 我通过基本上将 state -> (val,state) 的函数包装在一个新类型中来理解 state monad 的工作原理，这样我们就可以为它创建一个 monad 实例。我已经阅读了很多关于这个主题的内容。我似乎仍然无法理解如何在整个程序执行过程中获得唯一（或只是增量）值。获得一系列连续的 ID 很容易，但是一旦我“runState”退出 monad，我似乎又回到了开始跟踪当前 ID 的地方。我觉得我被困在单子里了。我考虑的另一个选择是将整个 IntMap 和当前的“下一个”ID 保留为状态，但这似乎非常“必要”和极端。这问题非常相似，但没有得到很多答案（或者我只是遗漏了一些明显的东西）。在整个程序执行过程中，利用 state monad 获取唯一 ID 的惯用方法是什么？谢谢。

4

1 回答 1

11

假设我们要IO-ify Statemonad。那会是什么样子？我们的纯Statemonad 只是一个新类型：

s -> (a, s)

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

s -> IO (a, s)

这种模式很常见，它有一个名字，特别是StateT：

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

这个名字T的末尾有一个，因为它是一个单子变形器T。我们称其m为“基本单子”和StateT s m“转换后的”单子。

StateT s mis only a Monadif mis a 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 -}

如果tis StateT s，则lift's 类型专门用于：

lift :: m a -> StateT s m a

换句话说，它让我们“提升”基本单子中的一个动作，使其成为转换后的单子中的一个动作。

因此，对于您的特定问题，您需要StateT (IntMap k v) IOmonad，它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)

请注意，我仍然使用getand 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

这意味着您可以同时使用getand和。putStateStateT

要了解有关 monad 转换器的更多信息，我强烈推荐Monad Transformers - Step by Step。

于 2013-01-25T16:11:28.000 回答