如何用List monad建模非确定性？

Question

任何人都可以解释(更好的用简单英语的例子)列表monad可以做什么来模拟非确定性计算？即问题是什么以及列表monad可以提供什么解决方案.

Answer 1

这是一个基于抛硬币的例子.问题如下:

你有两个硬币,标记为偏见和公平.该偏置硬币有两个头,以及公平硬币都有一个头,一个尾巴.随机选择其中一个硬币,扔掉并观察结果.如果结果是头部,你选择有偏见的硬币的概率是多少？

我们可以在Haskell中对此进行建模,如下所示.首先,你需要硬币和它们的面孔类型

data CoinType = Fair | Biased deriving (Show)

data Coin = Head | Tail deriving (Eq,Show)

我们知道抛出一枚公平的硬币可能会出现,Head或者Tail有偏见的硬币总会出现Head.我们用可能的替代方案列表对此进行建模(隐含地,每种可能性都是同样可能的).

toss Fair   = [Head, Tail]
toss Biased = [Head, Head]

我们还需要一个随机选择公平或有偏见硬币的功能

pick = [Fair, Biased]

然后我们就像这样把它们放在一起

experiment = do
  coin   <- pick         -- Pick a coin at random
  result <- toss coin    -- Toss it, to get a result
  guard (result == Head) -- We only care about results that come up Heads
  return coin            -- Return which coin was used in this case

请注意,虽然代码读起来像我们只是运行一次实验,但是列表monad正在建模非确定性,并实际上遵循所有可能的路径.因此结果是

>> experiment
[Biased, Biased, Fair]

因为所有的可能性都是同样可能的,我们可以得出结论,我们有2/3的机会有偏见的硬币,只有1/3的机会我们有公平的硬币.

Answer 2

当我们说它是非决定论时,它意味着它有多个值.

在了解你的Haskell书很好地解释了这一点:

像5这样的值是确定性的.它只有一个结果,我们确切地知道它是什么.另一方面,像[3,8,9]这样的值包含多个结果,因此我们可以将其视为一个实际上同时具有多个值的值.使用列表作为applicative functor很好地展示了这种非确定性:

ghci> (*) <$> [1,2,3] <*> [10,100,1000]  
[10,100,1000,20,200,2000,30,300,3000]

左侧列表中的乘法元素与右侧列表中的元素的所有可能组合都包含在结果列表中.在处理非确定性时,我们可以做出很多选择,所以我们只尝试所有这些选择,因此结果也是一个非确定性的值,只有它有更多的结果.

很好地列出monad模型非确定性.它的实例是这样的:

instance Monad [] where  
    return x = [x]  
    xs >>= f = concat (map f xs)  
    fail _ = [] 

因此,当您提供非确定性值时,它将产生另一组非确定性值:

ghci> [3,4,5] >>= \x -> [x, x * 2]
[3,6,4,8,5,10]

Answer 3

列表monad可以表示"来自非确定性计算的所有可能结果".例如,功能

f x = [x, x + 1, x + 2]

可以被解释为一个非确定性计算,它接受x并返回其中一个x,x+1和x+2.

功能

g x = [2 * x, 3 * x]

可以被解释为一个非确定性计算,它接受x或返回任何一个2 * x或3 * x.这两个非确定性计算的"组成"应该是另一个非确定性计算,它将其x转换为其中之一x,x + 1或者x + 2然后将其加倍或三倍.因此,就列表而言,结果应该是所有六种可能性的列表

现在

g =<< f x = [2 * x, 3 * x, 2 * (x + 1), 3 * (x + 1), 2 * (x + 2), 3 * (x + 2)]

所以这确实模仿了我们预期的非决定论.

(将列表用于非确定性有一些尴尬,因为它们也有元素的排序."set monad"可能是一种更自然的非确定性建模方法.列表当然包含足够的信息来模拟非确定性,但订购意味着我们有更多的信息而不是必要的.)

编辑:实际上我写的只是使用列表应用实例.要获得完全利用monadic接口的东西,你需要一个计算,它返回一些取决于它的输入的结果,例如

g 0 = [1000, 1001]
g x = [2 * x, 3 * x, 4 * x]

虽然不可否认,这是一个完全武断且毫无动机的例子!

Answer 4

因此,明确定义"非确定性"在这里的意义非常重要,因为它与在非确定性算法中的感知方式不同.这里捕获的意义是计算分支 - 可能存在系统可以在任何特定点移动的多个状态.

列表对此进行建模,因为它们只包含多个元素.更重要的是,monadic理解为我们提供了一种组合非确定性结果的方法 - 即模拟一次探索所有分支.