3

我想构建一个计算，其中上下文是引导现在的所有路径的历史（形成一棵树），而函数是当前状态，以过去状态为条件。该函数本身是不确定的，因此一个过去的状态可能会导致几个未来的状态，因此是树分支。将此计算的结果表示为一棵树是有意义的，但是有没有办法用 list monad 简洁地表达它？还是我不知道的其他构造？

4

3 回答 3

6

使用 list monad 可以让您像树一样构建计算，但它会丢失源信息。最后，您将获得一个结果列表，但您不知道每个单独的结果来自哪里。

如果这就是你所关心的，那么 list monad 就是完美的。假设您有一个不确定的step函数：

step :: State -> [State]

如果我们只想逐步执行很多次，我们可以编写如下内容：

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

这将在 3 个步骤后为我们提供所有可能的结果。(<=<)如果我们想将其推广到任何数字，我们可以使用来自的一元组合运算符编写一个简单的辅助函数Control.Monad。这就像.，除了表单a -> m b的函数而不是普通函数 ( a -> b)。它可能看起来像这样：

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

现在要获得三个不确定的步骤，我们可以只写stepN 3 step. （您可能想为这些函数想出更好的名称：P。）

总结：使用 list monad，计算本身的形状像一棵树，但你只能看到最后的结果。从所涉及的类型中应该清楚这一点：最后，你得到 a [State]，它本质上是 flat 。但是，函数有State -> [State]分支，因此到达末尾的计算必须看起来像一棵树。

对于这样的事情，列表类型使用起来非常方便。

于 2013-06-18T14:36:11.550 回答
6

我想补充一下 Tikhon Jelvis 的回答，如果您需要跟踪执行分支的方式，您可以使用更复杂的 monad 堆栈组合。例如：

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是 inside [(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注意for 分支单子计算的用法。与直接使用列表操作相比，使用mplus和mzero（或派生msum的，等）更方便。如果您稍后更改您的 monad 堆栈，例如从更改为 our ，您现有的代码将无需修改即可工作。mfilterguardMonadPlus[]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 回答
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跟踪您访问的每个节点，并且[]是非确定性部分。但是，如果要添加效果，则需要替换[]为等效的 monad 转换器ListT：

StateT [node] (ListT IO) r

这就是您派生branch. 在我们的特定情况下，node我们正在访问的 s 是Ints 并branch在它所采用的每条路径的末尾返回当前上下文。

当您evalStateT使用空的初始上下文时，您会得到：

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

这是一个不确定的计算，它将尝试每个分支，在结果进行时跟踪结果IO，然后在结果结束时返回本地上下文。由于我们branch将采用 8 条路径，因此将有 8 个最终结果。

如果我们使用 运行它runRespondT，我们会得到Producer：

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

该生产者将在到达每个执行路径的末端时发出结果，并在执行过程中进行跟踪。我们不必等到计算结束才能看到痕迹。我们需要查看[Int]它正在输出的 s 是将其连接到 a Consumer：

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

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

这将我们的最终计算转换为Effect基本 monad 中的一个（在本例中IO）。我们可以使用以下命令运行此效果runProxy：

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

然后，这既跟踪计算又打印出每条路径的终点。

于 2013-06-19T01:21:31.107 回答