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

问题描述

谁能解释一下(用简单的英语示例更好)列表 monad 可以做什么来模拟非确定性计算?即问题是什么以及列表 monad 可以提供什么解决方案.

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:

您有两枚硬币，分别标记为 Biased 和 Fair.Biased 硬币有两个正面，Fair 硬币有一个正面和一个反面.随机选择这些硬币中的一个，扔它并观察结果.如果结果是正面，那么您选择 Biased 硬币的概率是多少?

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?

我们可以在 Haskell 中进行如下建模.首先，你需要硬币的类型和它们的面

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)

我们知道，抛一枚公平的硬币可以出现 Head 或 Tail，而偏向硬币总是出现 Head.我们用一系列可能的替代方案对此进行建模(其中隐含地，每种可能性的可能性都相同).

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

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

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]

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

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屋！