10

モチベーション。私はモナド変換子を作成しようとしています。これは、「、f <||> gを含むこのブロック全体をf <||> g、1回fは、、次はを含む」という意味の特別な命令を使用して作成していgます。他のアプリケーションを想像することはできますが、これはDSL変換を目的としています。

使用例。モナドは、computationさまざまな可能な選択肢（この場合は印刷するもの）を表します。このprintme関数は、それぞれの異なる結果をどう処理するかを示します。この場合、実行前に「計算の開始」を出力し、実行後に「---」を出力します。

computation = do
    lift (print "start -- always")
    (lift (print "first choice") <||> lift (print "second choice"))
    lift (print "intermediate -- always")
    (lift (print "third choice") <||> lift (print "fourth choice"))
    lift (print "end -- always")

printme x = do
    putStrLn "=== start computation"
    xv <- x
    putStrLn "---\n"
    return xv

test = runIndep printme computation

出力は次のとおりです。

=== start computation
"start -- always"
"first choice"
"intermediate -- always"
"third choice"
"end -- always"
---

=== start computation
"start -- always"
"first choice"
"intermediate -- always"
"fourth choice"
"end -- always"
---

=== start computation
"start -- always"
"second choice"
"intermediate -- always"
"third choice"
"end -- always"
---

=== start computation
"start -- always"
"second choice"
"intermediate -- always"
"fourth choice"
"end -- always"
---

質問。ある種の継続渡しスタイルのモナド変換子を使用して上記の動作を実現するためのクリーンな方法はありますか？Oleg et al。の「モナド変換子のバックトラッキング、インターリーブ、および終了」の論文を見ましたが、それらの実装を完全に把握することはできません（msplit継続して実装に到達すると）。

現在の実装。私の現在の実装は、行われる分岐決定のリストを渡すことです。モナドは実際に選択したブランチのリストを返し、次に可能な最後のブランチを切り替えます。コードは次のとおりです（7.0.3で実行する必要があります）。

import Control.Monad.Trans.Class

data IndepModelT  α = IndepModelT {
    unIndepModelT :: [Bool] ->  (α, [Bool]) }

instance Monad  => Monad (IndepModelT ) where
    return x = IndepModelT $ \choices -> return (x, [])
    (IndepModelT x) >>= f = IndepModelT $ \choices -> do
        (xv, branches) <- x choices
        let choices' = drop (length branches) choices
        (fxv, branches') <- unIndepModelT (f xv) choices'
        return (fxv, branches ++ branches')

instance MonadTrans IndepModelT where
    lift x = IndepModelT $ \c -> liftWithChoice [] x
liftWithChoice cs mx = mx >>= \xv -> return (xv, cs)

(<||>)
  :: Monad  => IndepModelT  α -> IndepModelT  α -> IndepModelT  α
(IndepModelT f) <||> (IndepModelT g) = IndepModelT go where
    go (False:cs) = do
        (fv, branches) <- f cs
        return (fv, False : branches)
    go (True:cs) = do
        (fv, branches) <- g cs
        return (fv, True : branches)

run_inner next_choices k comp@(IndepModelT comp_inner) = do
    (xv, branches) <- k $ comp_inner next_choices
    case (get_next_choices branches) of
        Nothing -> return ()
        Just choices -> run_inner (choices ++ repeat False) k comp
    where
        get_next_choices [] = Nothing
        get_next_choices [True] = Nothing
        get_next_choices [False] = Just [True]
        get_next_choices (c:cs)
            | Just cs' <- get_next_choices cs = Just $ c:cs'
            | c Prelude.== False = Just [True]
            | otherwise = Nothing

runIndep :: Monad  =>
    ( (α, [Bool]) ->  (β, [Bool]))
    -> IndepModelT  α
    ->  ()
runIndep = run_inner (repeat False)

runIndepFirst (IndepModelT comp) = comp (repeat False)
4

3 に答える 3

8

ここに問題があります: これはモナドではありません! 動作は明確に定義されていません。この場合、何をすべきか:

do
  b <- ...randomly True or False...
  if b then ...some choices... else ...some other choices...

しかし、それはApplicativeです。必要な型は で[IO a]、これは 2 つのアプリカティブ ファンクターの構成なのでData.Functor.Compose、transformers パッケージから使用できます。これにより、for freeのAlternativeインスタンスも提供されます。<|>Rebindable Syntax を使用して、Applicative の do 表記を使用します。

{-# LANGUAGE RebindableSyntax #-}
import Prelude hiding ((>>), (>>=))
import Control.Applicative
import Data.Functor.Compose

lift :: Applicative f => g a -> Compose f g a
lift = Compose . pure

(>>) :: Applicative f => f a -> f b -> f b
(>>) = (*>)

computation :: Alternative f => Compose f IO ()
computation = do
    lift (print "start -- always")
    lift (print "first choice") <|> lift (print "second choice")
    lift (print "intermediate -- always")
    lift (print "third choice") <|> lift (print "fourth choice")
    lift (print "end -- always")

printme x = do
    putStrLn "=== start computation"
    x
    putStrLn "---\n"

test = mapM printme $ getCompose computation
于 2011-12-06T11:16:01.293 に答える
3

これまでに得た提案は機能しません。その方法は次のとおりです。

f <||> g = ContT $ \k -> do
  xs <- runContT f k
  ys <- runContT g k
  return $ xs ++ ys

test = runContT computation (return . (:[]))

しかし、それは選択ごとに計算全体を再開するわけではありません。結果は次のようになります。

"start -- always"
"first choice"
"intermediate -- always"
"third choice"
"end -- always"
"fourth choice"
"end -- always"
"second choice"
"intermediate -- always"
"third choice"
"end -- always"
"fourth choice"
"end -- always"

私はまだ良い解決策を見つけていません。

于 2011-12-05T10:27:42.273 に答える
1

特に継続ベースのアプローチを探している場合は、論文SFKTの成功/失敗の継続の実装よりもはるかに単純になることはありません。LogicT

msplitが多すぎる場合(そしてそれは非常に微妙な獣です)、このアプリケーションでは無視できます。その目的は、サンプル出力のこれらの行が順番に印刷されることを意図している場合、仕様の一部ではない公正な結合と分離を可能にすることです。Monadセクション 5.1 のとMonadPlus実装に集中するだけで、準備は完了です。

更新: Sjoerd Visscher が指摘しているように、再起動はmplus計算全体ではなくからのみ発生するため、これは正しくありません。これは、最初に読んだときよりもはるかにトリッキーな問題です。

于 2011-12-05T06:39:09.733 に答える