MonadPlus (ST a) 인스턴스가 필요합니다.

Question

나는 Typed Logical Variables in Haskell이라는 글을 읽었으나 궁극적 인 구현 방법에 대해서는 자세히 이해하지 못했습니다. 내가 무슨 문제가 확실 해요

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 

: 특히, 나에게 알 수없는 몇 가지 이유를 들어 4 장에서 소개 되돌아 상태 변압기, GHC 내가 아래 기능 unify에 (ST a)에 대한 MonadPlus 인스턴스를 필요로 믿고 그리고 그것을 고치는 방법. 나는이 시점까지 선행 토론과 규범을 이해했다는 인상을 받았지만, 분명히 나는 ​​착각했다. 누군가가 무엇이 잘못되었는지 지적 할 수 있다면 MonadPlus (ST a) 인스턴스가 필요한가요? - 도움이 될 것입니다.

는 [편집 : 명확한 설명은] 나는 저자 그 mzero 항에 나타나는 지적한다, 또는 mzero에 약간의 변화는 적절한 기능입니다. 나는 단지 적절한 기능이 무엇인지 모른다. 내가 궁금한 것은 내가 MonadPlus (ST a) 인스턴스를 만들 것인지 아니면 올바른 함수를 사용하지 않고 뭔가 잘못 읽었는지 여부입니다.

Answer 1

mzero은 (는) MonadPlus의 typeclass 멤버입니다. 특히

mzero :: MonadPlus m => m a 

함수 unify에 사용되는 모나드는 실제로 BackTST 인스턴스화 인 LP이다. 또한 BackT에 대한 MonadPlus의 인스턴스를 정의합니다.이 인스턴스는 기본 모나드에 대한 인스턴스에 따라 다릅니다. 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 

이 인스턴스는 기본적으로 두 개의 출력 목록을 연결 : 나는 아이디어를 가지고있다. 나는 그것이 당신의 필요에 어울리기를 바랍니다.

Answer 2

BackTMonadPlus 인스턴스는 아마 다음과 같이 m 대신 []의 MonadPlus 인스턴스를 사용한다 :

이 unify` '의 반환 형식은`LP의()`, 또는`BackT (ST A를 사용한다

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