Что означает эта цитата?
the list functor represents a context of nondeterministic choice;
В контексте функторов в функциональном программировании.
Думаю, я понимаю, что Functor - это "контейнер" какого-то типа, а также возможность равномерного применения функции к элементам в контейнере без изменения структуры. Возможно, это Functor, представляющий контекст или контейнер с возможным сбоем, но почему список представляет собой контекст или контейнер с недетерминированным выбором?
Насколько я могу судить, расчет "недетерминирован", если он имеет несколько возможных ответов. Ну, список может содержать несколько возможных ответов. Поэтому почему.
(Что касается того, почему он называется недетерминистским, я понятия не имею... Я бы ожидал, что недетерминистский означает случайный, что совсем другое.)
Традиционно, в вычислимости и сложности, недетерминированная вычислительная модель ссылалась на модель, в этом случае вы можете "вступить". Википедия объясняет это так:
В теории вычислительной сложности недетерминированные алгоритмы - это те, которые на каждом возможном этапе могут допускать множественные продолжения (представьте, что человек идет по тропинке в лесу и каждый раз, когда он продвигается дальше, он должен выбрать, какую вилку в дороги, которую он хочет взять). Эти алгоритмы не приходят к решению для всех возможных вычислительных путей; однако они гарантированно придут к правильному решению для какого-либо пути (т.е. человек, идущий по лесу, может найти только свою каюту, если он выберет комбинацию "правильных" путей). Выбор можно интерпретировать как догадки в процессе поиска.
В списке monad это именно то, что вы делаете. Например, рассмотрите это решение для решения проблемы clique в списке monad:
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)
Именно так вы программируете, например. недетерминированную машину Тьюринга для решения проблемы клики.
В дополнение к просмотру функтора в качестве контейнера вы также можете рассматривать его как определенный вид контекста. Ваши значения в этом контексте, и если вы хотите работать с ними, вы используете map, чтобы поднять функцию в контексте. Другой способ выразить это - то, что ваши ценности дополняются этим контекстом.
Чтобы понять, как функтор списка является контекстом недетерминированного выбора, может быть полезно увидеть, как другой функтор является контекстом: возможно, функтор Maybe является контекстом вычисления, которое может потерпеть неудачу. Если вы попытаетесь применить функцию к значению в функторе Maybe, результирующее значение по-прежнему будет поддерживать тот же контекст, независимо от того, было ли это неудачное вычисление в первую очередь.
Таким же образом список можно рассматривать как результат вычисления, не имеющего детерминированного результата, но результат которого может быть выбран недетерминистически из одного из нескольких значений. Если вы попытались сопоставить функцию над списком с 3 элементами, эти элементы были бы изменены, но контекст возможности выбора между тремя значениями остался бы таким же.
Заимствуя немного ответа от Дэна Бертсона, посмотрите на монадическую нотацию для списков:
foo = do
x <- [1 .. 10]
y <- [2, 3, 5, 7]
return (x * y)
Сначала кажется немного странным, так как обозначение указывает на то, что вы можете извлечь одно значение из каждого из списков, но затем вы получите в результате список длиной 40 элементов. Это имеет смысл, когда вы смотрите на функторы (ну, монады в этом случае) в качестве контекста для одного значения. В этом примере x и y являются такими значениями, но их контекст заключается в том, что они недетерминированы. Когда вы умножаете два таких значения, вы получаете еще больше недетерминизма, в результате чего получается более длинный список. Таким образом, с помощью monads и >>= контекст может быть изменен, тогда как с функторами и map он не может.
"Классические" вычисления принимают 1 вход и дают 1 выход. То, что вы хотите представить с помощью этих недетерминированных вычислений: Что я могу сказать о выходе, если я не уверен в отношении ввода?
Два обычных способа представления неопределенности - рассмотреть:
В качестве примера рассмотрим функцию (2 *), которая удваивает ее ввод. Что вы можете сказать о выходе этой функции, когда вход является результатом броска штампа?
Функтор списка представляет собой недетерминированные вычисления в смысле 1: он представляет множества по спискам.
Рассмотрим следующее:
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... ]