Изучай Haskell во имя добра!

Когда мы использовали операцию >>= со значениями типа Maybe, монадическое значение передавалось в функцию с заботой о возможных неудачах. Здесь она заботится за нас о недетерминированности.

Список [3,4,5] является недетерминированным значением, и мы передаём его в функцию, которая тоже возвращает недетерминированное значение. Результат также является недетерминированным, и он представляет все возможные результаты получения элементов из списка [3,4,5] и передачи их функции \x –> [x,–x]. Эта функция принимает число и производит два результата: один взятый со знаком минус и один неизменный. Поэтому когда мы используем операцию >>= для передачи этого списка функции, каждое число берётся с отрицательным знаком, а также сохраняется неизменным. Образец x в анонимной функции принимает каждое значение из списка, который ей передаётся.

Чтобы увидеть, как это достигается, мы можем просто проследить за выполнением. Сначала у нас есть список [3,4,5]. Потом мы отображаем его с помощью анонимной функции и получаем следующий результат:

[[3,-3],[4,-4],[5,-5]]

Анонимная функция применяется к каждому элементу, и мы получаем список списков. В итоге мы просто сглаживаем список – и вуаля, мы применили недетерминированную функцию к недетерминированному значению!

Недетерминированность также включает поддержку неуспешных вычислений. Пустой список в значительной степени эквивалентен значению Nothing, потому что он означает отсутствие результата. Вот почему неуспешное окончание вычислений определено просто как пустой список. Сообщение об ошибке отбрасывается. Давайте поиграем со списками, которые приводят к неуспеху в вычислениях:

ghci> [] >>= \x –> ["плохой","бешеный","крутой"]

[]

ghci> [1,2,3] >>= \x –> []

[]

В первой строке пустой список передаётся анонимной функции. Поскольку список не содержит элементов, нет элементов для передачи функции, а следовательно, результатом является пустой список. Это аналогично передаче значения Nothing функции, которая принимает тип Maybe. Во второй строке каждый элемент передаётся функции, но элемент игнорируется, и функция просто возвращает пустой список. Поскольку функция завершается неуспехом для каждого элемента, который в неё попадает, результатом также является неуспех.

Как и в случае со значениями типа Maybe, мы можем сцеплять несколько списков с помощью операции >>=, распространяя недетерминированность:

ghci> [1,2] >>= \n –> ['a','b'] >>= \ch –> return (n,ch)

[(1,'a'),(1,'b'),(2,'a'),(2,'b')]

Числа из списка [1,2] связываются с образцом n; символы из списка ['a','b'] связываются с образцом ch. Затем мы выполняем выражение return (n, ch) (или [(n, ch)]), что означает получение пары (n, ch) и помещение её в минимальный контекст по умолчанию. В данном случае это создание наименьшего возможного списка, который по-прежнему представляет пару (n, ch) в качестве результата и обладает наименее возможной недетерминированностью. Его влияние на контекст минимально. Мы говорим: «Для каждого элемента в списке [1,2] обойти каждый элемент из ['a','b'] и произвести кортеж, содержащий по одному элементу из каждого списка».

Вообще говоря, поскольку функция return принимает значение и оборачивает его в минимальный контекст, она не обладает какими-то дополнительными эффектами (вроде приведения к неуспешному окончанию вычислений в типе Maybe или получению ещё большей недетерминированности для списков), но она действительно возвращает что-то в качестве своего результата.

Когда ваши недетерминированные значения взаимодействуют, вы можете воспринимать их вычисление как дерево, где каждый возможный результат в списке представляет отдельную ветку. Вот предыдущее выражение, переписанное в нотации do:

listOfTuples :: [(Int,Char)]

listOfTuples = do

   n <– [1,2]

   ch <– ['a','b']

   return (n,ch)

Такая запись делает чуть более очевидным то, что образец n принимает каждое значение из списка [1,2], а образец ch – каждое значение из списка ['a','b']. Как и в случае с типом Maybe, мы извлекаем элементы из монадического значения и обрабатываем их как обычные значения, а операция >>= беспокоится о контексте за нас. Контекстом в данном случае является недетерминированность.

Нотация do и генераторы списков

Использование списков в нотации do может напоминать вам о чём-то, что вы уже видели ранее. Например, посмотрите на следующий кусок кода:

ghci> [(n,ch) | n <– [1,2], ch <– ['a','b']]

[(1,'a'),(1,'b'),(2,'a'),(2,'b')]