需要MonadPlus（ST a）實例

我正在閱讀紙張Typed Logical Variables in Haskell，但我無法理解最終實現的細節。特別是，回溯狀態變壓器第4節介紹了由於某些原因，不認得我，GHC認爲我需要一個(ST a)例如MonadPlus在功能unify，如下：需要MonadPlus（ST a）實例

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)實例，或者我沒有使用正確的函數，並且誤解了某些內容。

來源

2011-10-06 danportin

unify'的'返回類型爲'LP S（）'或'BackT（ST一）（）'。顯然，MonadPlus的'BackT m'實例需要'MonadPlus m'。你能在這裏包括那個實例嗎？ –

mzero是typeclass MonadPlus的成員。特別是

mzero :: MonadPlus m => m a

是用於你的函數unify的單子是LP，這實際上BackT是ST實例化。此外，您還可以爲BackT定義一個MonadPlus的實例，該實例依賴於此基礎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)

在普通的英語：這是針對BackT m的MonadPlus一個實例，只要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-06 23:08:21 fuz

你是對的;我已更新我的帖子以包含定義。這可能是我誤解了monad並定義了綁定，返回，mzero或者加了不正確的。 – danportin

這工作完美。感謝您解釋問題和解決方案。 – danportin

小心！這個MonadPlus定義可能不是你所期望的。中級寫入'STRef's在最終失敗的分支將*不*回滾。 – luqui

的BackTMonadPlus實例或許應該使用的[]的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-06 23:19:44

需要MonadPlus（ST a）實例

回答

相關問題