3

コンテキストが現在に至るすべてのパスの履歴 (ツリーを形成する) であり、関数が過去の状態を条件とする現在の状態である計算を構築したいと考えています。関数自体は非決定論的であるため、1 つの過去の状態が複数の将来の状態になる可能性があるため、ツリーは分岐します。この計算の結果をツリーとして表現することは理にかなっていますが、それをリストモナドで簡潔に表現する方法はありますか? それとも、私が知らない他の構造ですか？

4

3 に答える 3

6

Tikhon Jelvis の回答に追加したいのですが、実行がどのように分岐するかを追跡する必要がある場合は、より複雑なモナド スタックの組み合わせを使用できます。例えば：

import Control.Monad
import Control.Monad.Writer
import Data.Sequence

-- | Represents a non-deterministic computation
-- that allows to trace the execution by sequences of 'w'.
type NonDet w a = WriterT (Seq w) [] a

の値WriterT (Seq w) [] aは の中[(a, Seq w)]にあります。つまり、可能な結果のリストであり、それぞれがタイプ の一連のマークとともに結果を保持しwます。これらのマークを使用して、手順を追跡します。

最初に、現在の実行トレースにマークを追加するだけのヘルパー関数を作成します。

-- | Appends a mark to the current trace.
mark :: w -> NonDet w ()
mark = tell . singleton

そしておそらく、マークを追加してから指定された計算を続行する、より便利な関数です。

-- | A helper function appends a mark and proceeds.
(#>) :: w -> NonDet w a -> NonDet w a
(#>) x = (mark x >>)

非常に単純な例として、ツリーをトラバースしたいとしましょう

data Tree a = Leaf a | Bin (Tree a) (Tree a)

（実際には、もちろんツリーはありません。分岐は、洗練されたものによって決定されます。）

そして、一連の方向を使用して横断したパスを覚えます。

data Direction = L | R
  deriving (Show, Read, Eq, Ord, Enum, Bounded)

トラバーサル関数は次のようになります。

traverse :: Tree a -> NonDet Direction a
traverse (Leaf x)  = return x
traverse (Bin l r) = (L #> traverse l) `mplus` (R #> traverse r)

通話中

runWriterT $ traverse $ Bin (Bin (Leaf "a") (Leaf "b")) (Leaf "c")

で生産

[("a",fromList [L,L]),("b",fromList [L,R]),("c",fromList [R])]

ノート：

  • mplusモナド計算の分岐に を使用していることに注意してください。リスト操作を直接使用するよりもmplusand mzero(または派生msumしたmfilter、guardなど)を使用する方が便利です。MonadPlus後でモナド スタックを変更した場合、たとえば から[]ourに変更した場合NonDet Direction、既存のコードは変更なしで機能します。

  • WriterTシーケンスだけでなく、任意のモノイドを使用できるからです。たとえば、必要なのが実行された歩数だけである場合、次のように定義できます。

    type NonDet a = WriterT (Sum Int) [] a

mark :: NonDet w ()
mark tell (Sum 1)

    次に、呼び出しmarkはカウンターをインクリメントするだけで、呼び出しの結果 (わずかに変更されたtraverse) は次のようになります。

    [("a",Sum {getSum = 2}),("b",Sum {getSum = 2}),("c",Sum {getSum = 1})]
于 2013-06-18T15:53:49.977 に答える
6

リスト モナドを使用すると、計算をツリーのように構造化できますが、ソース情報が失われます。最後に、結果のリストが表示されますが、個々の結果がどこから来たのかはわかりません。

これだけ気にするなら、リストモナドは完璧です。非決定論的な関数があるとしましょうstep:

step :: State -> [State]

何度もステップ実行したい場合は、次のように記述できます。

startState >>= step >>= step >>= step

これにより、3 つのステップの後に考えられるすべての結果が得られます。これを任意の数に一般化する場合は、単項合成演算子(<=<)fromを使用して単純なヘルパー関数を記述できますControl.Monad。これは、通常の関数 ( ) ではなく.形式の関数を除いて、 と同じように機能します。次のようになります。a -> m ba -> b

stepN :: Int -> (State -> [State]) -> State -> [State]
stepN n f = foldr (<=<) return (replicate n f)

3 つの非決定論的なステップを取得するには、次のように記述しstepN 3 stepます。(おそらく、関数のより良い名前を考え出したいと思うでしょう:P.)

要約すると、リストモナドを使用すると、計算自体はツリーのような形になりますが、最後に結果を見るだけです。これは、関連する型から明らかなはずです。最後に、 が得られます[State]。これは、本質的にフラットです。ただし、関数はState -> [State]分岐するため、最後に到達するための計算はツリーのように見える必要があります。

そんな時はリスト型がとても便利です。

于 2013-06-18T14:36:11.550 に答える
2

実際には、他の提案されたソリューションよりもさらに優れたことができます。連続する分岐ごとに独立した履歴を保持し、実行パスをリアルタイムでトレースできます。

これを使用する方法は次のpipes-4.0.0とおりです（現在はまだGithubにあります）：

import Control.Monad.Trans.Class (lift)
import Control.Monad.Trans.State
import Pipes
import qualified Pipes.Prelude as P

branch :: Int -> StateT [Int] (ListT' IO) [Int]
branch n =
    if (n <= 0) then get
    else do
        path <- lift $ P.each [1, 2]
        lift $ lift $ putStrLn $ "Taking path " ++ show path
        modify (path:)
        branch (n - 1)

pipe :: () -> Producer' [Int] IO ()
pipe () = runRespondT (evalStateT (branch 3) [])

main = runProxy $ (pipe >-> P.print) ()

出力されるものは次のとおりです。

Taking path 1
Taking path 1
Taking path 1
[1,1,1]
Taking path 2
[2,1,1]
Taking path 2
Taking path 1
[1,2,1]
Taking path 2
[2,2,1]
Taking path 2
Taking path 1
Taking path 1
[1,1,2]
Taking path 2
[2,1,2]
Taking path 2
Taking path 1
[1,2,2]
Taking path 2
[2,2,2]

通常、現在訪問している状態のコンテキストを保存したい場合は、次を使用します。

StateT [node] [] r

...nodeはあなたが訪れた場所です。 StateTアクセスしたすべてのノードを追跡し[]、非決定論的な部分です。ただし、効果を追加したい場合は、[]同等のモナド変換子に置き換える必要があります: ListT:

StateT [node] (ListT IO) r

これが の型を導出する方法ですbranch。私たちの特定nodeのケースでは、訪問している はであり、たどる各パスの最後に現在のコンテキストを返しますInt。branch

evalStateT空の初期コンテキストを使用すると、次のようになります。

evalStateT (branch 3) [] :: ListT IO [Int]

IOこれは、各分岐を試行し、結果を追跡して、結果の最後にローカル コンテキストを返す非決定論的な計算です。branch合計 8 つのパスを使用するため、最終的な結果は 8つになります。

を使用してそれを実行するとrunRespondT、次のようになりますProducer。

pipe :: () -> Producer' [Int] IO ()

このプロデューサーは、各実行パスの最後に到達すると結果を出力し、その過程でトレースします。トレースを確認するために計算が終了するまで待つ必要はありません。[Int]出力しているを表示するために必要なのは、それを に接続することだけですConsumer:

P.print :: () -> Consumer [Int] IO r

pipe >-> P.print :: () -> Effect IO ()

これにより、最終的な計算Effectが基底モナド (この場合はIO) の に変換されます。以下を使用してこの効果を実行できますrunProxy。

runProxy $ (pipe >-> P.print) () :: IO ()

これにより、計算がトレースされ、各パスの終点が出力されます。

于 2013-06-19T01:21:31.107 に答える