4

Typed Logical Variables in Haskellという論文を読んでいますが、最終的な実装の詳細を理解できていません。特に、セクション 4 で導入されたバックトラッキング状態トランスフォーマーです。何らかの理由で、私にはわかりませんが、GHC は、以下の functionに の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

mzerotypeclass のメンバーですMonadPlus。特に

mzero :: MonadPlus m => m a

関数に使用されるモナドunifyはLPで、実際には でBackTインスタンス化されSTます。さらに、基礎となるモナドのインスタンスに依存するMonadPlusforのインスタンスを定義します。BackTそのようなインスタンスがないので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

このインスタンスは、基本的に 2 つの出力リストを連結します。あなたのニーズに合っていることを願っています。

于 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 に答える