4

我正在阅读Haskell 中的 Typed Logical Variables论文，但我无法理解最终实现的细节。特别是第 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)实例还是我没有使用正确的功能，并且误读了一些东西。

4

2 回答 2

4

mzero是 typeclass 的成员MonadPlus。尤其

mzero :: MonadPlus m => m a

用于您的函数的 monadunify是LP，它实际上是BackT用 实例化的ST。您还定义了一个MonadPlusfor的实例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)

用简单的英语：这是MonadPlusfor的一个实例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

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

于 2011-10-06T23:08:21.663 回答
3

该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))
于 2011-10-06T23:19:44.703 回答