Я изучал Haskell из Learn You A Haskell и только что наткнулся на следующее утверждение:
Выполнение
(+) <$> [1,2] <*> [4,5,6]приводит к недетерминированному вычислениеx + y, гдеxпринимает каждое значение из[1,2]иyпринимает на каждое значение от[4,5,6].
Я не думаю, что понимаю, что не является детерминированным в этом вопросе. Разве только, что порядок результатов или порядок вычислений не гарантируется одинаковым каждый раз?
В книге используется другое чувство "недетерминированных вычислений", чем вы.
Вы думаете о "недетерминированном вычислении", как в "программе, которая не полностью определяет ее выход". Такой тип недетерминированности распространен при использовании нескольких параллельных потоков выполнения; существует много возможных выходов, и какой из них вы произвольно определяете точным порядком, в котором все происходит во время выполнения.
В параграфе, который вы цитируете LYAH, речь идет о просмотренных списках как о модели "недетерминированных вычислений", в смысле, подразумеваемой парадигмой логического программирования (если вы когда-либо делали много программирования с помощью Prolog язык, вы, вероятно, знакомы с этим). Недетерминированные программы в этом смысле имеют множественные (или нулевые!) Выходы, потому что они специально запрограммированы для этого, а не потому, что они не полностью определяют, каков должен быть их вывод.
Если "недетерминированный код" - это просто код, который имеет "ноль или более выходов типа t", это очень похоже на функцию, возвращающую список t. Список экземпляров Аппликативный (и Functor и Monad) - это просто очевидный способ сказать, как объединить такие "неиндексирные ценности" друг с другом и с чистыми функциями. Например, экземпляр Functor говорит, что если вы можете применить функцию к A для получения B, тогда вы также можете сопоставить эту функцию для работы с "недетерминированным A", чтобы получить "неинтерминированный B" (по применяя неизбранную функцию к любому возможному значению "недетерминированного А" ).
(+) <$> [1,2] <*> [4,5,6], рассматриваемый таким образом, является примером "недетерминированного сложения". Вы добавляете число, которое может быть 1 или 2, другому числу, которое может быть 4, 5 или 6; результат может быть 5, 6, 7, 6, 7 или 8 (некоторые возможности повторяются, потому что существует более одного способа их генерации).
В этом контексте, что недетерминированным не является вычисление, которое выполняет Haskell, а вместо этого вычисление, которое представляется. Если рассматривать как монаду (или аппликативный функтор), списки представляют собой недетерминированные вычисления: так же, как a Maybe a - это вычисление a, которое могло быть неудачным, или IO a - вычисление a, которое I/O, a [a] - недетерминированное вычисление a a. Таким образом, список [1,2] при этой интерпретации представляет собой вычисление, которое недетерминистически возвращает 1 или 2, и аналогично для [4,5,6]. Или, опять же, с помощью аналогии: вычисление Nothing в Haskell преуспевает, хотя это значение представляет отказ; вычисление [1,2] в Haskell является детерминированным (и довольно скучным), но это значение кодирует форму недетерминизма.
Таким образом, (+) <$> [1,2] <*> [4,5,6] вычисляет x + y недетерминированно. Опять же, это не то, что написано в коде - то, что представляет собой код. Сам код детерминистически вычисляет представление недетерминированного вычисления!
Как это работает, функция <$> и <*> выполняет вычисления подъема внутри аппликативного функтора, поэтому фрагмент говорит о вычислении (+) внутри аппликативного функтора списка, что означает, что он вычисляет (+) недетерминистически:
[1,2] представляет собой вычисление, которое может возвращать либо 1, либо 2. Вызвать его результат x.[4,5,6] представляет собой вычисление, которое могло бы возвращать любые из 4, 5 или 6. Вызвать его результат y.x + y - могло бы оценить сумму любого из возможных значений для x и y.Это то, что говорится в цитате, чуть более иными словами: -)
Фактически, (+) <$> [1,2] <*> [4,5,6] в точности эквивалентен [x + y | x <- [1,2], y <- [4,5,6]], где "недетерминизм" вместо этого x и y каждый итерация по их соответствующим спискам. Это все, что подразумевается под недетерминизмом, в конце концов!
Что касается того, как вы думали о понимании этого: помните, что код Haskell гарантированно будет детерминированным в его результатах, благодаря чисто функциональному характеру Haskell. Однако порядок вычислений не влияет на это, поэтому остается довольно неограниченным, пока функции не сбой слишком рано (например, const () undefined должен оцениваться до ()). Мы получаем только недетерминизм, представляя его как эффект; списки - это одна кодировка этого (и IO может быть другой, для совершенно другого типа недетерминизма).
В списке monad мне нравится думать о [1, 2] как о представлении набора возможных вариантов: 1 или 2. Когда мы выполняем операции над таким набором, мы создаем набор возможных результатов. Что такое "1 или 2" плюс 4? Естественно, "5 или 6". В Haskell мы можем сформулировать этот вопрос как (+ 4) <$> [1, 2] и получить ожидаемый ответ [5, 6].
Монада списка представляет собой недетерминизм в том смысле, что он позволяет нам говорить обо всем дереве возможных вариантов, не совершая при этом ни одного из этих выборов. Итак, что такое "1 или 2" плюс "4, 5 или 6"? Ну, это может быть:
Мы можем кодировать вопрос в Haskell с монадой списка (как исчерпывающий расчет всех решений в порядке):
do
x <- [1, 2] -- if x is 1 or 2
y <- [4, 5, 6] -- and y is 4, 5, or 6
return (x + y) -- then what are the possible values of x + y?
Или с помощью списка (сделайте то же самое):
(+) <$> [1, 2] <*> [4, 5, 6]
И ответ, конечно, [5, 6, 7, 6, 7, 8].
Если это помогает, вы также можете подумать о монаде списка или о понимании списков как о своем декартовом произведении.
Другим способом кодирования является запуск независимого параллельного вычисления для каждого из вариантов сразу же, выводя конечные результаты без какого-либо неотъемлемого порядка.