34

任何人都可以解释（用简单的英语示例更好）列表单子可以对非确定性计算进行建模吗？即问题是什么以及列表单子可以提供什么解决方案。

4

4 回答 4

44

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

您有两个硬币，分别标记为Biased和Fair。Biased币有两个头，Fair币有一个头和一个尾。随机选择其中一枚硬币，将其抛掷并观察结果。如果结果是正面，你选择有偏硬币的概率是多少？

我们可以在 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

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

>> experiment
[Biased, Biased, Fair]

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

于 2013-12-17T21:11:20.557 回答
21

当我们说它是非确定性时，它意味着它具有多个值。

《Learn You A Haskell》一书很好地解释了这一点：

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

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]
于 2013-12-17T16:52:44.557 回答
11

列表单子可以表示“来自非确定性计算的所有可能结果”。例如，函数

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

可以解释为一种非确定性计算，它接受x并返回 和 中的x一个。x+1x+2

功能

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

可以解释为非确定性计算，它接受x并返回2 * x或3 * x。这两个非确定性计算的“组合”应该是另一个非确定性计算，它采用x，将其转换为或之一x，然后将其加倍或加倍。因此，就列表而言，结果应该是所有六种可能性的列表x + 1x + 2

现在

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

所以确实如我们所料，这模拟了非确定性。

（将列表用于非确定性有一些尴尬，因为它们也有元素的顺序。“set monad”可能是一种更自然的方式来模拟非确定性。列表当然包含足够的信息来模拟非确定性，但订购意味着我们拥有比必要更多的信息。）

编辑：事实上，我写的只是使用列表应用实例。为了获得充分利用单子接口的东西，您需要一个返回许多取决于其输入的结果的计算，例如

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

尽管不可否认，这是一个完全武断且没有动机的例子！

于 2013-12-17T16:55:32.257 回答
11

因此，重要的是在这里明确定义“非确定性”的含义，因为它与在非确定性算法中的感知方式并不完全相同。这里捕捉到的感觉是计算分支- 系统可以在任何特定点移动到多个状态。

列表对此进行建模，因为简单地说，它们包含多个元素。更重要的是，一元推导为我们提供了一种组合非确定性结果的方法——即一次建模探索所有分支。

于 2013-12-17T16:58:58.913 回答