非确定性如何用List monad建模？ [英] How can non-determinism be modeled with a List monad?

问题描述

任何人都可以解释（用简单英语的例子更好）单子列表可以做什么来模拟非确定性计算？

解决方案

以下是一个示例基于投掷硬币。问题如下：

您有两个硬币，标有 和 Fair 。 The'em'Biased''硬币有两个头部，而'Fair'硬币有一个头部和一个尾部。随机挑选这些硬币中的一个，掷出并观察结果。如果结果是头部，您选择了的硬币的概率是多少？

我们可以如下在Haskell中对此进行建模。首先，你需要硬币和他们的脸的类型

  data CoinType = Fair | Biased派生（显示）
 
数据Coin = Head |尾部派生（Eq，Show）
  

我们知道抛硬币可以达到头部或尾部，而有偏见的硬币总是出现头部。我们用一系列可能的替代方法对其进行建模（其中隐含的，每种可能性都是可能的）。

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

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

pick = [Fair， biased]


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

 = 实验=做
硬币< - 折腾它，得到结果
 guard（result == Head） - 我们只关心出现的结果头元b $ b返回硬币 - 返回在这种情况下使用的硬币
  

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

 >>实验
 [Biased，Biased，Fair] 
  

因为所有的可能性都是相同的可能性，可以得出结论，我们有2/3的机会存在偏见的硬币，而我们只有1/3的机会拥有这个公平的硬币。

Can anyone explain (better with an example in plain English) what a list monad can do to model non-deterministic calculations? Namely what the problem is and what solution a list monad can offer.

解决方案

Here's an example based on coin tossing. The problem is as follows:

You have two coins, labeled Biased and Fair. The Biased coin has two heads, and the Fair coin has one head and one tail. Pick one of these coins at random, toss it and observe the result. If the result is a head, what is the probability that you picked the Biased coin?

We can model this in Haskell as follows. First, you need the types of coin and their faces

data CoinType = Fair | Biased deriving (Show)

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

We know that tossing a fair coin can come up either Head or Tail whereas the biased coin always comes up Head. We model this with a list of possible alternatives (where implicitly, each possibility is equally likely).

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

We also need a function that picks the fair or biased coin at random

pick = [Fair, Biased]

Then we put it all together like this

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

Notice that although the code reads like we're just running the experiment once, but the list monad is modelling nondeterminism, and actually following out all possible paths. Therefore the result is

>> experiment
[Biased, Biased, Fair]

Because all the possibilities are equally likely, we can conclude that there is a 2/3 chance that we have the biased coin, and only a 1/3 chance that we have the fair coin.

这篇关于非确定性如何用List monad建模？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！