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

вычислений нескольких значений Maybe a.

Пьер решил сделать рабочий перерыв на рыбной ферме и попробовать заняться канатоходством. На удивление, ему это неплохо удаётся, но есть одна проблема: на балансировочный шест приземляются птицы! Они прилетают, немного отдыхают, болтают со своими пернатыми друзьями, а затем срываются в поисках хлебных крошек. Это не сильно беспокоило бы Пьера, будь количество птиц c левой стороны шеста всегда равным количеству птиц с правой стороны. Но порой всем птицам почему-то больше нравится одна сторона. В результате канатоходец теряет равновесие и падает (не волнуйтесь, он использует сетку безопасности!).

Давайте предположим, что Пьер удержит равновесие, если количество птиц на левой стороне шеста и на правой стороне шеста разнится в пределах трёх. Покуда, скажем, на правой стороне одна птица, а на левой – четыре, всё в порядке. Но стоит пятой птице опуститься на левую сторону, канатоходец теряет равновесие и кубарем летит вниз.

Мы сымитируем посадку и улёт птиц с шеста и посмотрим, останется ли Пьер на канате после некоторого количества прилётов и улётов птиц. Например, нам нужно увидеть, что произойдёт с Пьером, если первая птица прилетит на левую сторону, затем четыре птицы займут правую, а потом птица, которая была на левой стороне, решит улететь.

Код, код, код

Мы можем представить шест в виде простой пары целых чисел. Первый компонент будет обозначать количество птиц на левой стороне, а второй – количество птиц на правой:

type Birds = Int

type Pole = (Birds, Birds)

Сначала мы создали синоним типа для Int, названный Birds, потому что мы используем целые числа для представления количества имеющихся птиц. Затем создали синоним типа (Birds, Birds) и назвали его Pole (учтите: это означает «шест» – ничего общего ни с поляками, ни с человеком по имени Поль).

А теперь как насчёт того, чтобы добавить функции, которые принимают количество птиц и производят их приземление на одной стороне шеста или на другой?

landLeft :: Birds –> Pole –> Pole

landLeft n (left, right) = (left + n, right)

landRight :: Birds –> Pole –> Pole

landRight n (left, right) = (left, right + n)

Давайте проверим их:

ghci> landLeft 2 (0, 0)

(2,0)

ghci> landRight 1 (1, 2)

(1,3)

ghci> landRight (-1) (1,2)

(1,1)

Чтобы заставить птиц улететь, мы просто произвели приземление отрицательного количества птиц на одной стороне. Поскольку приземление птицы на Pole возвращает Pole, мы можем сцепить применения функций landLeft и landRight:

ghci> landLeft 2 (landRight 1 (landLeft 1 (0, 0)))

(3,1)

Когда мы применяем функцию landLeft 1 к значению (0, 0), у нас получается результат (1, 0). Затем мы усаживаем птицу на правой стороне, что даёт в результате (1, 1). Наконец, две птицы приземляются на левой стороне, что даёт в результате (3, 1). Мы применяем функцию к чему-либо, сначала записывая функцию, а затем её параметр, но здесь было бы лучше, если бы первым шел шест, а потом функция посадки. Предположим, мы создали вот такую функцию:

x -: f = f x

Можно применять функции, сначала записывая параметр, а затем функцию:

ghci> 100 -: (*3)

300

ghci> True -: not

False

ghci> (0, 0) -: landLeft 2

(2,0)

Используя эту форму, мы можем многократно производить приземление птиц на шест в более «читабельном» виде:

ghci> (0, 0) -: landLeft 1 -: landRight 1 -: landLeft 2

(3,1)

Круто!.. Эта версия эквивалентна предыдущей, где мы многократно усаживали птиц на шест, но выглядит она яснее. Здесь очевиднее, что мы начинаем с (0, 0), а затем усаживаем одну птицу слева, потом одну – справа, и в довершение две – слева.

Я улечу

Пока всё идёт нормально, но что произойдёт, если десять птиц приземлятся на одной стороне?

ghci> landLeft 10 (0, 3)

(10,3)

Десять птиц с левой стороны и лишь три с правой?! Этого достаточно, чтобы отправить в полёт самого Пьера!.. Довольно очевидная вещь. Но что если бы у нас была примерно такая последовательность посадок:

ghci> (0, 0) -: landLeft 1 -: landRight 4 -: landLeft (-1) -: landRight (-2)

(0,2)

Может показаться, что всё хорошо, но если вы проследите за шагами, то увидите, что на правой стороне одновременно находятся четыре птицы – а на левой ни одной! Чтобы исправить это, мы должны ещё раз взглянуть на наши функции landLeft и landRight.

Необходимо дать функциям landLeft и landRight возможность завершаться неуспешно. Нам нужно, чтобы они возвращали новый шест, если равновесие поддерживается, но завершались неуспешно, если птицы приземляются неравномерно. И какой способ лучше подойдёт для добавления к значению контекста неудачи, чем использование типа Maybe? Давайте переработаем эти функции:

landLeft :: Birds –> Pole –> Maybe Pole

landLeft n (left,right)

   | abs ((left + n) - right) < 4 = Just (left + n, right)

   | otherwise                    = Nothing

landRight :: Birds –> Pole –> Maybe Pole

landRight n (left,right)

   | abs (left - (right + n)) < 4 = Just (left, right + n)

   | otherwise                    = Nothing

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

Давайте опробуем этих деток:

ghci> landLeft 2 (0, 0)

Just (2,0)

ghci> landLeft 10 (0, 3)

Nothing

Когда мы приземляем птиц, не выводя Пьера из равновесия, мы получаем новый шест, обёрнутый в конструктор Just. Но когда значительное количество птиц в итоге оказывается на одной стороне шеста, в результате мы получаем значение Nothing. Всё это здорово, но, похоже, мы потеряли возможность многократного приземления птиц на шесте! Выполнить landLeft 1 (landRight 1 (0, 0)) больше нельзя, потому что когда landRight 1 применяется к (0, 0), мы получаем значение не типа Pole, а типа Maybe Pole. Функция landLeft 1 принимает параметр типа Pole, а не Maybe Pole.

Нам нужен способ получения Maybe Pole и передачи его функции, которая принимает Pole и возвращает Maybe Pole. К счастью, у нас есть операция >>=, которая делает именно это для типа Maybe. Давайте попробуем:

ghci> landRight 1 (0, 0) >>= landLeft 2

Just (2,1)

Вспомните, что функция landLeft 2 имеет тип Pole –> Maybe Pole. Мы не можем просто передать ей значение типа Maybe Pole, которое является результатом вызова функции landRight 1 (0, 0), поэтому используем операцию >>=, чтобы взять это значение с контекстом и отдать его функции landLeft 2. Операция >>= действительно позволяет нам обрабатывать значения типа Maybe как значения с контекстом. Если мы передадим значение Nothing в функцию landLeft 2, результатом будет Nothing, и неудача будет распространена:

ghci> Nothing >>= landLeft 2

Nothing

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

ghci> return (0, 0) >>= landRight 2 >>= landLeft 2 >>= landRight 2

Just (2,4)

Вначале мы использовали функцию return, чтобы взять шест и обернуть его в конструктор Just. Мы могли бы просто применить выражение landRight 2 к значению (0, 0) – это было бы то же самое, – но так можно добиться большего единообразия, используя оператор >>= для каждой функции. Выражение Just (0, 0) передаётся в функцию landRight 2, что в результате даёт результат Just (0, 2). Это значение в свою очередь передаётся в функцию landLeft 2, что в результате даёт новый результат (2, 2), и т. д.

Помните следующий пример, прежде чем мы ввели возможность неудачи в инструкции Пьера?

ghci> (0, 0) -: landLeft 1 -: landRight 4 -: landLeft (-1) -: landRight (-2)

(0,2)

Он не очень хорошо симулировал взаимодействие канатоходца с птицами. В середине его равновесие было нарушено, но результат этого не отразил. Давайте теперь исправим это, используя монадическое применение (оператор >>=) вместо обычного:

ghci> return (0, 0) >>= landLeft 1 >>= landRight 4 >>= landLeft (-1) >>= landRight (-2)

Nothing

Окончательный результат представляет неудачу, чего мы и ожидали. Давайте посмотрим, как этот результат был получен:

1. Функция return помещает значение (0, 0) в контекст по умолчанию, превращая значение в Just (0, 0).

2. Происходит вызов выражения Just (0, 0) >>= landLeft 1. Поскольку значение Just (0, 0) является значением Just, функция landLeft 1 применяется к (0, 0), что в результате даёт результат Just (1, 0), потому что птицы всё ещё находятся в относительном равновесии.

3. Имеет место вызов выражения Just (1, 0) >>= landRight 4, и результатом является выражение Just (1, 4), поскольку равновесие птиц пока ещё не затронуто, хотя Пьер уже удерживается с трудом.

4. Выражение Just (1, 4) передаётся в функцию landLeft (–1). Это означает, что имеет место вызов landLeft (–1) (1, 4). Теперь ввиду особенностей работы функции landLeft в результате это даёт значение Nothing, так как результирующий шест вышел из равновесия.

5. Теперь, поскольку у нас есть значение Nothing, оно передаётся в функцию landRight (–2), но так как это Nothing, результатом автоматически становится Nothing, поскольку нам не к чему применить эту функцию.

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

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

Банан на канате

Давайте разработаем функцию, которая игнорирует текущее количество птиц на балансировочном шесте и просто заставляет Пьера поскользнуться и упасть. Мы назовём её banana:

banana :: Pole –> Maybe Pole

banana _ = Nothing

Мы можем поместить эту функцию в цепочку вместе с нашими приземлениями птиц. Она всегда будет вызывать падение канатоходца, поскольку игнорирует всё, что ей передаётся в качестве параметра, и неизменно возвращает неудачу.

ghci> return (0, 0) >>= landLeft 1 >>= banana >>= landRight 1

Nothing

Функции banana передаётся значение Just (1, 0), но она всегда производит значение Nothing, которое заставляет всё выражение возвращать в результате Nothing. Какая досада!..

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

(>>) :: (Monad m) => m a –> m b –> m b

m >> n = m >>= \_ –> n

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

ghci> Nothing >> Just 3

Nothing

ghci> Just 3 >> Just 4

Just 4

ghci> Just 3 >> Nothing

Nothing

Если мы заменим оператор >> на вызов >>= \_ –>, легко увидеть, что происходит.

Мы можем заменить нашу функцию banana в цепочке на оператор >> и следующее за ним значение Nothing, чтобы получить гарантированную и очевидную неудачу:

ghci> return (0, 0) >>= landLeft 1 >> Nothing >>= landRight 1

Nothing

Как бы это выглядело, если бы мы не сделали разумный выбор, обработав значения типа Maybe как значения с контекстом неудачи и передав их функциям? Вот какой была бы последовательность приземлений птиц:

routine :: Maybe Pole

routine = case landLeft 1 (0, 0) of

   Nothing –> Nothing

   Just pole1 –> case landRight 4 pole1 of

      Nothing –> Nothing

      Just pole2 –> case landLeft 2 pole2 of

         Nothing –> Nothing

         Just pole3 –> landLeft 1 pole3

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

Обратите внимание, каким образом реализация операции >>= для типа Maybe отражает именно эту логику, когда проверяется, равно ли значение Nothing, и действие производится на основе этих сведений. Если значение равно Nothing, она незамедлительно возвращает результат Nothing. Если значение не равно Nothing, она продолжает работу с тем, что находится внутри конструктора Just.

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

Монады в языке Haskell настолько полезны, что они обзавелись своим собственным синтаксисом, который называется «нотация do». Вы уже познакомились с нотацией do в главе 8, когда мы использовали её для объединения нескольких действий ввода-вывода. Как оказывается, нотация do предназначена не только для системы ввода-вывода, но может использоваться для любой монады. Её принцип остаётся прежним: последовательное «склеивание» монадических значений.

Рассмотрим этот знакомый пример монадического применения:

ghci> Just 3 >>= (\x –> Just (show x ++ "!"))

Just "3!"

Это мы уже проходили! Передача монадического значения функции, которая возвращает монадическое значение, – ничего особенного. Заметьте, как параметр x становится равным значению 3 внутри анонимной функции, когда мы выполняем код. Как только мы внутри этой анонимной функции, это просто обычное значение, а не монадическое. А что если бы у нас был ещё один вызов оператора >>= внутри этой функции? Посмотрите:

ghci> Just 3 >>= (\x –> Just "!" >>= (\y –> Just (show x ++ y)))

Just "3!"

Ага-а, вложенное использование операции >>=! Во внешней анонимной функции мы передаём значение Just "!" анонимной функции \y –> Just (show x ++ y). Внутри этой анонимной функции параметр y становится равным "!". Параметр x по-прежнему равен 3, потому что мы получили его из внешней анонимной функции. Всё это как будто напоминает мне о следующем выражении:

ghci> let x = 3; y = "!" in show x ++ y

"3!"

Главное отличие состоит в том, что значения в нашем примере с использованием оператора >>= являются монадическими. Это значения с контекстом неудачи. Мы можем заменить любое из них на неудачу:

ghci> Nothing >>= (\x –> Just "!" >>= (\y –> Just (show x ++ y))) Nothing

ghci> Just 3 >>= (\x –> Nothing >>= (\y –> Just (show x ++ y)))

Nothing

ghci> Just 3 >>= (\x –> Just "!" >>= (\y –> Nothing))

Nothing

В первой строке передача значения Nothing функции естественным образом даёт в результате Nothing. Во второй строке мы передаём значение Just 3 функции, и параметр x становится равным 3. Но потом мы передаём значение Nothing внутренней анонимной функции, и результатом становится Nothing, что заставляет внешнюю анонимную функцию тоже произвести Nothing в качестве своего результата. Это что-то вроде присвоения значений переменным в выражениях let, только значения, о которых идёт речь, являются монадическими.

Чтобы проиллюстрировать эту идею, давайте запишем следующие строки в сценарий так, чтобы каждое значение типа Maybe занимало свою собственную строку:

foo :: Maybe String

foo = Just 3 >>= (\x –>

      Just "!">>= (\y –>

      Just (show x ++ y)))

Чтобы уберечь нас от написания всех этих раздражающих анонимных функций, язык Haskell предоставляет нам нотацию do. Она позволяет нам записать предыдущий кусок кода вот так:

foo :: Maybe String

foo = do

    x <– Just 3

    y <– Just "!"

    Just (show x ++ y)

Могло показаться, что мы получили возможность временно извлекать сущности из значений типа Maybe без необходимости проверять на каждом шагу, являются ли значения типа Maybe значениями в конструкторе Just или значениями Nothing. Вот классно!.. Если какое-либо из значений, которые мы пытаемся извлечь, равно Nothing, всё выражение do в результате вернёт значение Nothing. Мы выдёргиваем наружу их значения (если таковые существуют) и перекладываем необходимость беспокойства о контексте, идущем с этими значениями, на плечи оператора >>=.

Выражения do – это просто другой синтаксис для сцепления монадических значений.

Делай как я

В выражении do каждая строка, не являющаяся строкой let, является монадическим значением. Чтобы просмотреть её результат, мы используем символ <–. Если у нас есть значение типа Maybe String и мы привязываем её к образцу с помощью символа <–, этот образец будет иметь тип String так же, как когда мы использовали операцию >>= для передачи монадических значений анонимным функциям.

Последнее монадическое значение в выражении do – такое как Just (show x ++ y) в этом примере – не может быть использовано с символом <– для привязки его результата, потому что если бы мы преобразовали выражение do обратно в цепочку применений оператора >>=, это не имело бы смысла. Наоборот, результат последнего выражения является результатом всего склеенного монадического значения, учитывая возможную неудачу вычисления каждого из предыдущих монадических значений. Рассмотрите, например, следующую строку:

ghci> Just 9 >>= (\x –> Just (x > 8))

Just True

Поскольку левым параметром функции >>= является значение в конструкторе Just, анонимная функция применяется к значению 9, и результатом становится значение Just True. Мы можем переписать это в нотации do следующим образом:

marySue :: Maybe Bool

marySue = do

   x <– Just 9

   Just (x > 8)

Сравнивая оба варианта, легко увидеть, почему результатом всего монадического значения является результат последнего монадического значения в выражении do со всеми предыдущими монадическими значениями, сцепленными с ним.

Пьер возвращается

Инструкция нашего канатоходца может также быть выражена с использованием нотации do. Функции landLeft и landRight принимают количество птиц и шест и производят шест, обёрнутый в Just. Исключение – это когда канатоходец соскальзывает, и тогда возвращается значение Nothing. Мы использовали операцию >>= для сцепления последовательных шагов, потому что каждый из них зависел от предыдущего и каждый обладал добавленным контекстом возможной неудачи. Здесь две птицы приземляются с левой стороны, затем две птицы – с правой, а потом одна птица – снова с левой:

routine :: Maybe Pole

routine = do

   start <– return (0, 0)

   first <– landLeft 2 start

   second <– landRight 2 first

   landLeft 1 second

Давайте посмотрим, окончится ли это удачно для Пьера:

ghci> routine

Just (3,2)

Окончилось удачно!

Когда мы выполняли эти инструкции, явно записывая вызовы оператора >>=, мы обычно писали что-то вроде return (0, 0) >>= landLeft 2, потому что функция landLeft является функцией, которая возвращает значение типа Maybe. Однако при использовании выражения do каждая строка должна представлять монадическое значение. Поэтому мы явно передаём предыдущее значение типа Pole функциям landLeft и landRight. Если бы мы проверили образцы, к которым привязали наши значения типа Maybe, то start был бы равен (0, 0), first был бы равен (2, 0) и т. д.

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

Ещё раз давайте взглянем на то, как выглядел бы этот кусок кода, если бы мы не использовали монадические стороны типа Maybe:

routine :: Maybe Pole

routine =

   case Just (0, 0) of

      Nothing –> Nothing

      Just start –> case landLeft 2 start of

         Nothing –> Nothing

         Just first –> case landRight 2 first of

            Nothing –> Nothing

            Just second –> landLeft 1 second

Видите, как в случае успеха образец start получает значение кортежа внутри Just (0, 0), образец first получает значение результата выполнения landLeft 2 start и т. д.?

Если мы хотим бросить Пьеру банановую кожуру в нотации do, можем сделать следующее:

routine :: Maybe Pole

routine = do

   start <– return (0, 0)

   first <– landLeft 2 start

   Nothing

   second <– landRight 2 first

   landLeft 1 second

Когда мы записываем в нотации do строку, не связывая монадическое значение с помощью символа <–, это похоже на помещение вызова функции >> за монадическим значением, результат которого мы хотим игнорировать. Мы помещаем монадическое значение в последовательность, но игнорируем его результат, так как нам неважно, чем он является. Плюс ко всему это красивее, чем записывать эквивалентную форму _ <– Nothing.

Когда использовать нотацию do, а когда явно использовать вызов операции >>=, зависит от вас. Я думаю, этот пример хорошо подходит для того, чтобы явно использовать операцию >>=, потому что каждый шаг прямо зависит от предыдущего. При использовании нотации do мы должны явно записывать, на каком шесте садятся птицы, но каждый раз мы просто используем шест, который был результатом предшествующего приземления. Тем не менее это дало нам некоторое представление о нотации do.

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

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

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

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

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

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

Да! Генераторы списков! В нашем примере, использующем нотацию do, образец n принимал значения всех результатов из списка [1,2]. Для каждого такого результата образцу ch был присвоен результат из списка ['a','b'], а последняя строка помещала пару (n, ch) в контекст по умолчанию (одноэлементный список) для возврата его в качестве результата без привнесения какой-либо дополнительной недетерминированности. В генераторе списка произошло то же самое, но нам не нужно было писать вызов функции return в конце для возврата пары (n, ch) в качестве результата, потому что выводящая часть генератора списка сделала это за нас.

На самом деле генераторы списков являются просто синтаксическим сахаром для использования списков как монад. В конечном счёте генераторы списков и списки, используемые в нотации do, переводятся в использование операции >>= для осуществления вычислений, которые обладают недетерминированностью.

Класс MonadPlus и функция guard

Генераторы списков позволяют нам фильтровать наши выходные данные. Например, мы можем отфильтровать список чисел в поиске только тех из них, которые содержат цифру 7:

ghci> [x | x <– [1..50], '7' `elem` show x]

[7,17,27,37,47]

Мы применяем функцию show к параметру x чтобы превратить наше число в строку, а затем проверяем, является ли символ '7' частью этой строки.

Чтобы увидеть, как фильтрация в генераторах списков преобразуется в списковую монаду, мы должны рассмотреть функцию guard и класс типов MonadPlus.

Класс типов MonadPlus предназначен для монад, которые также могут вести себя как моноиды. Вот его определение:

class Monad m => MonadPlus m where

   mzero :: m a

   mplus :: m a –> m a –> m a

Функция mzero является синонимом функции mempty из класса типов Monoid, а функция mplus соответствует функции mappend. Поскольку списки являются моноидами, а также монадами, их можно сделать экземпляром этого класса типов:

instance MonadPlus [] where

   mzero = []

   mplus = (++)

Для списков функция mzero представляет недетерминированное вычисление, которое вообще не имеет результата – неуспешно окончившееся вычисление. Функция mplus сводит два недетерминированных значения в одно. Функция guard определена следующим образом:

guard :: (MonadPlus m) => Bool –> m ()

guard True = return ()

guard False = mzero

Функция guard принимает значение типа Bool. Если это значение равно True, функция guard берёт пустой кортеж () и помещает его в минимальный контекст, который по-прежнему является успешным. Если значение типа Bool равно False, функция guard создаёт монадическое значение с неудачей в вычислениях. Вот эта функция в действии:

ghci> guard (5 > 2) :: Maybe ()

Just ()

ghci> guard (1 > 2) :: Maybe ()

Nothing

ghci> guard (5 > 2) :: [()]

[()]

ghci> guard (1 > 2) :: [()]

[]

Выглядит интересно, но чем это может быть полезно? В списковой монаде мы используем её для фильтрации недетерминированных вычислений:

ghci> [1..50] >>= (\x –> guard ('7' `elem` show x) >> return x)

[7,17,27,37,47]

Результат аналогичен тому, что был возвращён нашим предыдущим генератором списка. Как функция guard достигла этого? Давайте сначала посмотрим, как она функционирует совместно с операцией >>:

ghci> guard (5 > 2) >> return "клёво" :: [String]

["клёво"]

ghci> guard (1 > 2) >> return "клёво" :: [String]

[]

Если функция guard срабатывает успешно, результатом, находящимся в ней, будет пустой кортеж. Поэтому дальше мы используем операцию >>, чтобы игнорировать этот пустой кортеж и предоставить что-нибудь другое в качестве результата. Однако если функция guard не срабатывает успешно, функция return впоследствии тоже не сработает успешно, потому что передача пустого списка функции с помощью операции >>= всегда даёт в результате пустой список. Функция guard просто говорит: «Если это значение типа Bool равно False, верни неуспешное окончание вычислений прямо здесь. В противном случае создай успешное значение, которое содержит в себе значение-пустышку ()». Всё, что она делает, – позволяет вычислению продолжиться.

Вот предыдущий пример, переписанный в нотации do:

sevensOnly :: [Int]

sevensOnly = do

   x <– [1..50]

   guard ('7' `elem` show x)

   return x

Если бы мы забыли представить образец x в качестве окончательного результата, используя функцию return, то результирующий список состоял бы просто из пустых кортежей. Вот определение в форме генератора списка:

ghci> [x | x <– [1..50], '7' `elem` show x]

[7,17,27,37,47]

Поэтому фильтрация в генераторах списков – это то же самое, что использование функции guard.

Ход конём

Есть проблема, которая очень подходит для решения с помощью недетерминированности. Скажем, у нас есть шахматная доска и на ней только одна фигура – конь. Мы хотим определить, может ли конь достигнуть определённой позиции в три хода. Будем использовать пару чисел для представления позиции коня на шахматной доске. Первое число будет определять столбец, в котором он находится, а второе число – строку.

Создадим синоним типа для текущей позиции коня на шахматной доске.

type KnightPos = (Int, Int)

Теперь предположим, что конь начинает движение с позиции (6, 2). Может ли он добраться до (6, 1) именно за три хода? Какой ход лучше сделать следующим из его нынешней позиции? Я знаю: как насчёт их всех?! К нашим услугам недетерминированность, поэтому вместо того, чтобы выбрать один ход, давайте просто выберем их все сразу! Вот функция, которая берёт позицию коня и возвращает все его следующие ходы:

moveKnight :: KnightPos –> [KnightPos]

moveKnight (c,r) = do

   (c',r') <– [(c+2,r-1),(c+2,r+1),(c-2,r-1),(c-2,r+1)

              ,(c+1,r-2),(c+1,r+2),(c-1,r-2),(c-1,r+2)

              ]

   guard (c' `elem` [1..8] && r' `elem` [1..8])

   return (c',r')

Конь всегда может перемещаться на одну клетку горизонтально или вертикально и на две клетки вертикально или горизонтально, причём каждый его ход включает движение и по горизонтали, и по вертикали. Пара (c', r') получает каждое значение из списка перемещений, а затем функция guard заботится о том, чтобы новый ход, а именно пара (c', r'), был в пределах доски. Если движение выходит за доску, она возвращает пустой список, что приводит к неудаче, и вызов return (c', r') не обрабатывается для данной позиции.

Эта функция может быть записана и без использования списков в качестве монад. Вот как записать её с использованием функции filter:

moveKnight :: KnightPos –> [KnightPos]

moveKnight (c,r) = filter onBoard

   [(c+2,r-1),(c+2,r+1),(c-2,r-1),(c-2,r+1)

   ,(c+1,r-2),(c+1,r+2),(c-1,r-2),(c-1,r+2)

   ]

   where onBoard (c,r) = c `elem` [1..8] && r `elem` [1..8]

Обе версии делают одно и то же, так что выбирайте ту, которая кажется вам лучше. Давайте опробуем функцию:

ghci> moveKnight (6, 2)

[(8,1),(8,3),(4,1),(4,3),(7,4),(5,4)]

ghci> moveKnight (8, 1)

[(6,2),(7,3)]

Работает чудесно! Мы берём одну позицию и просто выполняем все возможные ходы сразу, так сказать.

Поэтому теперь, когда у нас есть следующая недетерминированная позиция, мы просто используем операцию >>=, чтобы передать её функции moveKnight. Вот функция, принимающая позицию и возвращающая все позиции, которые вы можете достигнуть из неё в три хода:

in3 :: KnightPos –> [KnightPos]

in3 start = do

   first <– moveKnight start

   second <– moveKnight first

   moveKnight second

Если вы передадите ей пару (6, 2), результирующий список будет довольно большим. Причина в том, что если есть несколько путей достигнуть определённой позиции в три хода, ход неожиданно появляется в списке несколько раз.

Вот предшествующий код без использования нотации do:

in3 start = return start >>= moveKnight >>= moveKnight >>= moveKnight

Однократное использование операции >>= даёт нам все возможные ходы с начала. Когда мы используем операцию >>= второй раз, то для каждого возможного первого хода вычисляется каждый возможный следующий ход; то же самое верно и в отношении последнего хода.

Помещение значения в контекст по умолчанию с применением к нему функции return, а затем передача его функции с использованием операции >>= – то же самое, что и обычное применение функции к данному значению; но мы сделали это здесь, во всяком случае, ради стиля.

Теперь давайте создадим функцию, которая принимает две позиции и сообщает нам, можем ли мы попасть из одной в другую ровно в три хода:

canReachIn3 :: KnightPos –> KnightPos –> Bool

canReachIn3 start end = end `elem` in3 start

Мы производим все возможные позиции в пределах трёх ходов, а затем проверяем, находится ли среди них искомая.

Вот как проверить, можем ли мы попасть из (6,2) в (6,1) в три хода:

ghci> (6, 2) `canReachIn3` (6, 1)

True

Да! Как насчёт из (6, 2) в (7, 3)?

ghci> (6, 2) `canReachIn3` (7, 3)

False

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

Так же, как в отношении функторов и аппликативных функторов, в отношении монад действует несколько законов, которым должны подчиняться все экземпляры класса Monad. Даже если что-то сделано экземпляром класса типов Monad, это ещё не означает, что на самом деле перед нами монада. Чтобы тип по-настоящему был монадой, для него должны выполняться законы монад. Эти законы позволяют нам делать обоснованные предположения о типе и его поведении.

Язык Haskell позволяет любому типу быть экземпляром любого класса типов, пока типы удаётся проверить. Впрочем, он не может проверить, выполняются ли законы монад для типа, поэтому если мы создаём новый экземпляр класса типов Monad, мы должны обладать достаточной уверенностью в том, что с выполнением законов монад для этого типа всё хорошо. Можно полагаться на то, что типы в стандартной библиотеке удовлетворяют законам, но когда мы перейдём к созданию собственных монад, нам необходимо будет проверять выполнение законов вручную. Впрочем, не беспокойтесь – эти законы совсем не сложны!

Левая единица

Первый закон монад утверждает, что если мы берём значение, помещаем его в контекст по умолчанию с помощью функции return, а затем передаём его функции, используя операцию >>=, это равнозначно тому, как если бы мы просто взяли значение и применили к нему функцию. Говоря формально, return x >>= f – это то же самое, что и f x.

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

Функция return для монады Maybe определена как вызов конструктора Just. Вся суть монады Maybe состоит в возможном неуспехе в вычислениях, и если у нас есть значение, которое мы хотим поместить в такой контекст, есть смысл в том, чтобы обрабатывать его как успешное вычисление, поскольку мы знаем, каким является значение. Вот некоторые примеры использования функции return с типом Maybe:

ghci> return 3 >>= (\x –> Just (x+100000))

Just 100003

ghci> (\x –> Just (x+100000)) 3

Just 100003

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

ghci> return "WoM" >>= (\x –> [x,x,x])

["WoM","WoM","WoM"]

ghci> (\x –> [x,x,x]) "WoM"

["WoM","WoM","WoM"]

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

Правая единица

Второй закон утверждает, что если у нас есть монадическое значение и мы используем операцию >>= для передачи его функции return, результатом будет наше изначальное монадическое значение. Формально m >>= return является не чем иным, как просто m.

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

Функция return помещает значение в минимальный контекст, который по-прежнему возвращает это значение в качестве своего результата. Это значит, что, например, для типа Maybe она не вносит никакого неуспеха в вычислениях; для списков – не вносит какую-либо дополнительную недетерминированность.

Вот пробный запуск для нескольких монад:

ghci> Just "двигайся дальше" >>= (\x –> return x)

Just "двигайся дальше"

ghci> [1,2,3,4] >>= (\x –> return x)

[1,2,3,4]

ghci> putStrLn "Вах!" >>= (\x –> return x)

Вах!

В этом примере со списком реализация операции >>= выглядит следующим образом:

xs >>= f = concat (map f xs)

Поэтому когда мы передаём список [1,2,3,4] функции return, сначала она отображает [1,2,3,4], что в результате даёт список списков [[1],[2],[3],[4]]. Затем это конкатенируется, и мы получаем наш изначальный список.

Левое тождество и правое тождество являются, по сути, законами, которые описывают, как должна вести себя функция return. Это важная функция для превращения обычных значений в монадические, и было бы нехорошо, если бы монадическое значение, которое она произвела, имело больше, чем необходимый минимальный контекст.

Ассоциативность

Последний монадический закон говорит, что когда у нас есть цепочка применений монадических функций с помощью операции >>=, не должно иметь значения то, как они вложены. В формальной записи выполнение (m >>= f) >>= g – точно то же, что и выполнение m >>= (\x –> f x >>= g).

Гм-м, что теперь тут происходит? У нас есть одно монадическое значение, m, и две монадические функции, f и g. Когда мы выполняем выражение (m >>= f) >>= g, то передаём значение m в функцию f, что даёт в результате монадическое значение. Затем мы передаём это новое монадическое значение функции g. В выражении m >>= (\x –> f x >>= g) мы берём монадическое значение и передаём его функции, которая передаёт результат применения f x функции g. Нелегко увидеть, почему обе эти записи равны, так что давайте взглянем на пример, который делает это равенство немного более очевидным.

Помните нашего канатоходца Пьера, который пытался удержать равновесие, в то время как птицы приземлялись на его балансировочный шест? Чтобы симулировать приземление птиц на балансировочный шест, мы создали цепочку из нескольких функций, которые могли вызывать неуспешное окончание вычислений:

ghci> return (0, 0) >>= landRight 2 >>= landLeft 2 >>= landRight 2

Just (2,4)

Мы начали со значения Just (0, 0), а затем связали это значение со следующей монадической функцией landRight 2. Результатом было другое монадическое значение, связанное со следующей монадической функцией, и т. д. Если бы надлежало явно заключить это в скобки, мы написали бы следующее:

ghci> ((return (0, 0) >>= landRight 2) >>= landLeft 2) >>= landRight 2

Just (2,4)

Но мы также можем записать инструкцию вот так:

return (0, 0) >>= (\x –>

landRight 2 x >>= (\y –>

landLeft 2 y >>= (\z –>

landRight 2 z)))

Вызов return (0, 0) – то же самое, что Just (0, 0), и когда мы передаём это анонимной функции, образец x принимает значение (0, 0). Функция landRight принимает количество птиц и шест (кортеж, содержащий числа) – и это то, что ей передаётся. В результате мы имеем значение Just (0, 2), и, когда передаём его следующей анонимной функции, образец y становится равен (0, 2). Это продолжается до тех пор, пока последнее приземление птицы не вернёт в качестве результата значение Just (2, 4), что в действительности является результатом всего выражения.

Поэтому неважно, как у вас вложена передача значений монадическим функциям. Важен их смысл. Давайте рассмотрим ещё один способ реализации этого закона. Предположим, мы производим композицию двух функций, f и g:

(.) :: (b –> c) –> (a –> b) –> (a –> c)

f . g = (\x –> f (g x))

Если функция g имеет тип a –> b и функция f имеет тип b –> c, мы компонуем их в новую функцию типа a –> c, чтобы её параметр передавался между этими функциями. А что если эти две функции – монадические? Что если возвращаемые ими значения были бы монадическими? Если бы у нас была функция типа a –> m b, мы не могли бы просто передать её результат функции типа b –> m c, потому что эта функция принимает обычное значение b, не монадическое. Чтобы всё-таки достичь нашей цели, можно воспользоваться операцией <=<:

(<=<) :: (Monad m) => (b –> m c) –> (a –> m b) –> (a –> m c)

f <=< g = (\x –> g x >>= f)

Поэтому теперь мы можем производить композицию двух монадических функций:

ghci> let f x = [x,-x]

ghci> let g x = [x*3,x*2]

ghci> let h = f <=< g

ghci> h 3

[9,-9,6,-6]

Ладно, всё это здорово. Но какое это имеет отношение к закону ассоциативности? Просто, когда мы рассматриваем этот закон как закон композиций, он утверждает, что f <=< (g <=< h) должно быть равнозначно (f <=< g) <=< h. Это всего лишь ещё один способ доказать, что для монад вложенность операций не должна иметь значения.

Если мы преобразуем первые два закона так, чтобы они использовали операцию <=<, то закон левого тождества утверждает, что для каждой монадической функции f выражение f <=< return означает то же самое, что просто вызвать f. Закон правого тождества говорит, что выражение return <=< f также ничем не отличается от простого вызова f. Это подобно тому, как если бы f являлась обычной функцией, и тогда (f . g) . h было бы аналогично f . (g . h), выражение f . id – всегда аналогично f, и выражение id . f тоже ничем не отличалось бы от вызова f.

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