为什么列表函数器表示非确定性选择的上下文？

Question

这句话是什么意思？

the list functor represents a context of nondeterministic choice;

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

我想我理解了函数器是某种“容器”，以及在不改变结构的情况下对容器中的元素统一应用函数的能力。因此，可能是一个表示上下文或容器的函数器，但为什么列表表示具有不确定选择的上下文或容器？

Answer 1

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

(至于为什么它被称为不确定性，我不知道...我认为不确定性是指随机的，这是完全不同的。)

Answer 2

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

在计算复杂性理论中，非确定性算法是那些在每一步都可以允许多个连续的算法(想象一个人走在森林中的一条小路上，每走一步，他就必须在道路上选择他想要走的那个叉子)。这些算法并不是对每条可能的计算路径都能得到解决方案；但是，它们可以保证对某些路径得出正确的解决方案(即，穿行在森林中的人只有在选择了一些“正确”路径的组合时才能找到他的小屋)。这些选择可以解释为搜索过程中的猜测。

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

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)

这正是你如何编程的，例如一个不确定的图灵机来解决派系问题。

Answer 3

请考虑以下几点：

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

什么是foo？好吧，它是x * y，除了x的非确定性选择是一个从1到10的数字，y是2、3、5或7。