如何使用列表monad来计算/表示非确定性计算的结果？

Question

我想构建一个计算,其中上下文是引导当前(形成一个树)的所有路径的历史,并且该函数是以过去状态为条件的当前状态.函数本身是非确定性的,因此一个过去的状态可能导致几个未来状态,因此树分支.将这个计算的结果表示为树是有意义的,但有没有办法用列表monad简洁地表达它？或者其他一些我不知道的结构？

Answer 1

使用list monad可以让你像树一样构建计算,但它会丢失源信息.最后,您将得到一个结果列表,但您不知道每个结果的来源.

如果您只关心这一点,那么列表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.)

总结:使用列表monad,计算本身的形状就像一棵树,但你只能在最后查看结果.从所涉及的类型中可以清楚地看出这一点:最后,你会得到一个[State],它本质上是扁平的.但是,函数State -> [State]分支,所以到达终点的计算必须看起来像一棵树.

对于类似的东西,列表类型使用起来非常方便.

Answer 2

我想补充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内部[(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用于分支monadic计算的用法.它是使用更方便mplus和mzero(或衍生的msum,mfilter,guard从等)MonadPlus不是直接使用的列表操作.如果您以后更改monad堆栈,例如从[]我们更改,我们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})]