gro*_*odt 11 haskell functional-programming
这句话是什么意思？
the list functor represents a context of nondeterministic choice;
在功能编程中的Functors的上下文中.
我想我明白Functor是某种"容器",能够在不改变结构的情况下将函数统一地应用于容器中的元素.所以也许是一个Functor代表一个可能失败的上下文或容器,但为什么list代表一个具有非确定性选择的上下文或容器？
Mat*_*hid 11
据我所知,如果它有多个可能的答案,那么计算就是"不确定的".好吧,列表可以包含多个可能的答案.所以这就是为什么.
(至于为什么它被称为非确定性,我不知道......我本来期望非确定性意味着随机,这是完全不同的.)
传统上,在可计算性和复杂性方面,非确定性计算模型已经引用了一个模型,在这种情况下,您可以"分支".维基百科解释如下:
在计算复杂性理论中,非确定性算法是在每个可能的步骤中都可以允许多个连续的算法(想象一个人走在森林中的路径上,每当他走得更远时,他必须选择他想要的道路中的哪个叉子采取).这些算法没有为每个可能的计算路径找到解决方案; 然而,他们保证能够为某些路径找到正确的解决方案(即,如果他选择"正确"路径的某种组合,那么穿过森林的人可能只能找到他的小屋).选择可以解释为搜索过程中的猜测.
在monad列表中,这正是您正在做的事情.例如,在列表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)
这正是你如何编程,例如一个非确定性的图灵机来解决集团问题.
考虑以下:
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... ]
除了将仿函数视为容器之外,您还可以将其视为某种上下文.您的值在该上下文中,如果您想对它们进行操作,则可以使用map将函数提升到上下文中.放置它的另一种方法是使用该上下文扩充您的值.
要理解列表仿函数是非确定性选择的上下文,查看另一个仿函数如何是一个上下文可能是有用的:Maybe仿函数是可能失败的计算的上下文.如果您尝试将函数应用于Maybe仿函数中的值,则结果值仍将保持相同的上下文,无论它是否是一个失败的计算.
以相同的方式,列表可以被视为不具有确定性结果的计算的结果,但是其结果可以替代地从几个值中的一个非确定地选择.如果您尝试在具有3个元素的列表上映射函数,则会更改这些元素,但是能够在三个值之间进行选择的上下文将保持不变.
借用Dan Burtons的回答,看看列表的monadic符号:
foo = do
x <- [1 .. 10]
y <- [2, 3, 5, 7]
return (x * y)
它似乎有点奇怪,因为符号似乎表明,您可以从每个列表中提取单个值,但随后您得到一个40个元素长的列表.当你将functor(在这种情况下,monad)看作单个值的上下文时,它会更有意义.在示例中,x并且y是这样的值,但它们的上下文是它们是不确定的.当您将两个这样的值相乘时,您会获得更多的不确定性,从而导致列表更长.所以对于monad而言>>=,上下文可以改变,而对于functor而言map,它不能.