Сопоставление с образцом и неудача в вычислениях

Привязывая монадические значения к идентификаторам в нота- ции do, мы можем использовать сопоставление с образцом так же, как в выражениях let и параметрах функции. Вот пример сопостав- ления с образцом в выражении do:

justFirst:: Maybe Char justFirst = do

(x:xs) <– Just "привет" return x

Мы используем сопоставление с образцом для получения пер- вого символа строки "привет", а затем возвращаем его в качестве результата. Поэтому justFirst возвращает значение Just 'п'.

Что если бы это сопоставление с образцом окончилось неус- пешно? Когда сопоставление с образцом в функции оканчивается неуспешно, происходит сопоставление со следующим образцом. Если сопоставление проходит по всем образцам для данной функ- ции с невыполнением их условий, выдаётся ошибка и происходит аварийное завершение работы программы. С другой стороны, со- поставление с образцом, окончившееся неудачей в выражениях let, приводит к незамедлительному возникновению ошибки, по-

 

тому что в выражениях let отсутствует механизм прохода к следу- ющему образцу при невыполнении условия.

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

fail:: (Monad m) => String –> m a fail msg = error msg

Так что по умолчанию она действительно заставляет програм- му завершаться аварийно. Но монады, содержащие в себе контекст возможной неудачи (как тип Maybe), обычно реализуют её самостоя- тельно. Для типа Maybe она реализована следующим образом:

fail _ = Nothing

Она игнорирует текст сообщения об ошибке и производит зна- чение Nothing. Поэтому, когда сопоставление с образцом оканчива- ется неуспешно в значении типа Maybe, записанном в нотации do, результат всего значения будет равен Nothing. Предпочтительнее, чтобы ваша программа завершила свою работу неаварийно. Вот выражение do, включающее сопоставление с образцом, которое обречено на неудачу:

wopwop:: Maybe Char wopwop = do

(x:xs) <– Just "" return x

Сопоставление с образцом оканчивается неуспешно, поэтому эффект аналогичен тому, как если бы вся строка с образцом была заменена значением Nothing. Давайте попробуем это:

ghci> wopwop Nothing

Неуспешно окончившееся сопоставление с образцом вызвало неуспех только в контексте нашей монады, вместо того чтобы вы- звать неуспех на уровне всей программы. Очень мило!..

 

Списковая монада

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

недетерминированность в ясном и «читабельном» виде.

В главе 11 мы говорили о том, каким образом списки представ- ляют недетерминированные значения, когда они используются как аппликативные функторы. Значение вроде 5 является детерми- нированным – оно имеет только один результат, и мы точно зна- ем, какой он. С другой стороны, значение вроде [3,8,9] содержит несколько результатов, поэтому мы можем рассматривать его как одно значение, которое в то же время, по сути, является множеством значений. Использование списков в качестве аппликативных функ- торов хорошо демонстрирует эту недетерминированность:

ghci> (*) <$> [1,2,3] <*> [10,100,1000]

[10,100,1000,20,200,2000,30,300,3000]

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

Этот контекст недетерминированности очень красиво переводит- ся в монады. Вот как выглядит экземпляр класса Monad для списков:

instance Monad [] where return x = [x]

xs >>= f = concat (map f xs) fail _ = []

 

Как вы знаете, функция return делает то же, что и функция pure, и вы уже знакомы с функцией return для списков. Она прини- мает значение и помещает его в минимальный контекст по умол- чанию, который по-прежнему возвращает это значение. Другими словами, функция return создаёт список, который содержит толь- ко одно это значение в качестве своего результата. Это полезно, когда нам нужно просто обернуть обычное значение в список, чтобы оно могло взаимодействовать с недетерминированными значениями.

Суть операции >>= состоит в получении значения с контекс- том (монадического значения) и передаче его функции, которая принимает обычное значение и возвращает значение, обладаю- щее контекстом. Если бы эта функция просто возвращала обыч- ное значение вместо значения с контекстом, то операция >>= не была бы столь полезна: после первого применения контекст был бы утрачен.

Давайте попробуем передать функции недетерминированное значение:

ghci> [3,4,5] >>= \x –> [x,-x]

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

Когда мы использовали операцию >>= со значениями типа 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, мы из- влекаем элементы из монадического значения и обрабатываем их как обычные значения, а операция >>= беспокоится о контексте за нас. Контекстом в данном случае является недетерминирован- ность.