需要MonadPlus (ST a)实例

Question

我正在阅读报纸，但我无法理解最终实现的细节。特别是第4节中介绍的回溯状态转换器。出于某种原因，GHC认为我需要在函数MonadPlus中为(ST a)提供一个unify实例，如下所示：

newtype BackT m a = BT { run :: forall b . (a -> m [b]) -> m [b] }

instance (Monad m) => Monad (BackT m) where
 return a   = BT (\k -> k a)
 BT m >>= f = BT (\k -> m (\a -> run (f a) k))

instance (MonadPlus m) => MonadPlus (BackT m) where 
 mzero             = BT (\s -> mzero)
 f `mplus` g = BT (\s -> (run f) s `mplus` (run g) s)

type LP a = BackT (ST a)
type LR   = STRef

type Var s a = LR s (Maybe a)   
data Atom s = VarA (Var s (Atom s)) | Atom String

class Unify b a | a -> b where
 var   :: a -> Maybe (Var b a)
 unify :: a -> a -> LP s ()

instance Unify s (Atom s) where
 var (VarA a) = Just a
 var _        = Nothing

 unify (Atom a) (Atom b) | a == b = return () -- type checks
 unify _        _                 = mzero     -- requires MonadPlus (ST a) instance

我不知道是什么问题，以及如何解决它。在此之前，我一直以为我理解了前面的讨论和代码，但显然我弄错了。如果有人能指出出问题所在-我是否需要一个MonadPlus (ST a)实例？-这将是非常有帮助的。

编辑:澄清--我应该指出，作者似乎声称mzero (或mzero上的某些变体)是合适的函数。我只是不知道合适的功能是什么。我想知道的是，我是否应该创建一个MonadPlus (ST a)实例，还是没有使用正确的函数，并且误读了一些东西。

Answer 1

mzero是类型分类MonadPlus的成员之一。特别是

mzero :: MonadPlus m => m a

用于函数unify的monad是LP，它实际上是用ST实例化的BackT。您还为MonadPlus为BackT定义了一个实例，它依赖于底层monad的这样一个实例。因为ST没有这样的实例，所以GHC会嘲笑您。

这是重要的部分：

instance (MonadPlus m) => MonadPlus (BackT m) where 
  mzero             = BT (\s -> mzero)
  f `mplus` g = BT (\s -> (run f) s `mplus` (run g) s)

简单地说:这是MonadPlus for BackT m的一个实例，条件是m也是MonadPlus的一个实例。因为m是用ST实例化的，所以您需要ST的实例。我想知道如何在没有授权的情况下定义一个合理的MonadPlus实例。我有个主意：

instance MonadPlus (BackT m) where
  mzero = BT (const $ return [])
  mplus (BT f) (BT g) = BT $ \a -> do
    fs <- f a
    gs <- g a
    return $ fs ++ gs

这个实例基本上连接了两个输出列表。我希望它适合你的需要。

Answer 2

BackT MonadPlus实例可能应该使用[]的MonadPlus实例而不是m，如下所示：

instance (Monad m) => MonadPlus (BackT m) where 
  mzero       = BT (\_ -> return mzero)
  f `mplus` g = BT (\s -> liftM2 mplus (run f s) (run g s))