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

4 回答

• 16

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

  你有两个硬币，标记为偏见和公平 . 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
  

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

  >> experiment
  [Biased, Biased, Fair]
  

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

  回复于 2024-04-20T10:36:12+08:00
• 8

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

  Learn You A 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]
  

  回复于 2024-04-20T10:36:12+08:00
• 34

  列表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 . 这两个非确定性计算的"composition"应该是另一个非确定性计算，它采用 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)]
  

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

  （将列表用于非确定性有一些尴尬，因为它们也具有元素的排序 . 对于非确定性建模，列表可能是更自然的方式 . 列表当然包含足够的信息来模拟非确定性，但是订购意味着我们有更多的信息 . ）

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

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

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

  回复于 2024-04-20T10:36:12+08:00
• 10

  因此，非确定性' means here, since it'与其在非确定性算法中的感知方式不完全相同 . 这里捕获的意义是计算分支 - 可能存在系统可以在任何特定点移动的多个状态 .

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

  回复于 2024-04-20T10:36:12+08:00