11

这句话是什么意思？

the list functor represents a context of nondeterministic choice;

在函数式编程中的 Functor 的上下文中。

我想我理解 Functor 是某种“容器”，并且能够在不改变结构的情况下将函数统一应用于容器中的元素。所以也许是一个 Functor 代表一个可能失败的上下文或容器，但是为什么 list 代表一个具有不确定性选择的上下文或容器呢？

4

5 回答 5

11

据我所知，如果一个计算有多个可能的答案，它就是“不确定的”。好吧，一个列表可以包含多个可能的答案。所以这就是为什么。

（至于为什么它被称为 nondeterministic，我不知道......我原以为 nondeterministic 意味着random，这是完全不同的东西。）

于 2012-04-18T21:13:33.377 回答
8

传统上，在可计算性和复杂性方面，非确定性计算模型指的是在这种情况下您可以“分支”的模型。维基百科是这样解释的：

在计算复杂性理论中，非确定性算法是这样一种算法，在每一个可能的步骤中，都可以允许多个延续（想象一个人走在森林里的一条小路上，每次他走得更远，他都必须选择他想要的岔路口采取）。这些算法并没有为每一个可能的计算路径得出一个解决方案；然而，他们保证为某些路径得出正确的解决方案（即，穿过森林的人可能只有在选择“正确”路径的某种组合时才能找到他的小屋）。这些选择可以解释为搜索过程中的猜测。

在 list monad 中，这正是您正在做的事情。例如，考虑在 list monad中对clique 问题的决策版本的解决方案：

cliques :: Int -> Graph -> [[Node]]
cliques 0 _ = [[]]
cliques minCliqueSize graph = do
  v <- nodes graph
  vs <- cliques (minCliqueSize - 1) (deleteNode v graph)
  mapM_ (\ w -> guard (isAdjacent v w graph)) vs
  return (v:vs)

这正是您编写例如非确定性图灵机来解决集团问题的方式。

于 2012-04-18T22:02:25.383 回答
5

考虑以下：

foo = do
  x <- [1 .. 10]
  y <- [2, 3, 5, 7]
  return (x * y)

是什么foo？嗯，它是x * y，除了不确定性选择x是从 1 到 10 的数字，并且 y 是 2、3、5 或 7。因此，foo 是[2, 3, 5, 7, 4, 6, 10, 14, etc... ]

于 2012-04-18T21:59:39.680 回答
5

除了将函子视为容器之外，您还可以将其视为某种上下文。您的值在该上下文中，如果您想对它们进行操作，您可以使用map将函数提升到上下文中。另一种说法是，您的价值观会随着该上下文而增强。

要了解列表函子如何成为非确定性选择的上下文，了解另一个函子如何成为上下文可能会很有用：Maybe 函子是可能失败的计算的上下文。如果您尝试将函数应用于 Maybe 函子中的值，则结果值仍将保持与最初是否是失败计算相同的上下文。

同样，可以将列表视为没有确定性结果的计算结果，但其结果可能会从几个值之一中非确定性地选择。如果您尝试在具有 3 个元素的列表上映射函数，这些元素将被更改，但能够在三个值之间进行选择的上下文将保持不变。

借用 Dan Burtons 的回答，看看列表的一元符号：

foo = do
  x <- [1 .. 10]
  y <- [2, 3, 5, 7]
  return (x * y)

起初看起来有点奇怪，因为符号似乎表明，您可以从每个列表中提取一个值，但随后您会得到一个长度为 40 个元素的列表。当您将函子（在本例中为单子）视为单个值的上下文时，它会更有意义。在示例中，x和y是这样的值，但它们的上下文是它们是不确定的。当您将两个这样的值相乘时，您会得到更多的不确定性，从而导致更长的列表。因此，使用 monad 和>>=，可以更改上下文，而使用仿函数 and map，则不能。

于 2012-04-18T22:50:47.640 回答
4

“经典”计算采用 1 个输入并给出 1 个输出。您想用这些非确定性计算表示的是：如果我不确定输入，我能对输出说些什么？

表示不确定性的两种常用方法是考虑：

  1. 输入是给定集合的一个元素
  2. 输入由已知的概率分布给出

例如，考虑将其输入加倍的函数 (2*)。当输入是掷骰子的结果时，您对该函数的输出有何看法？

  1. 我知道骰子有 6 个面，所以结果在集合 {2,4,6,8,10,12}
  2. 我知道每张脸的概率是 1/6，所以我知道这些数字中的每一个都有 1/6 的概率出现

列表函子代表 1. 意义上的非确定性计算：它代表列表的集合。

于 2012-04-18T21:35:53.600 回答