Изучай Haskell во имя добра! - Миран Липовача

Чтобы увидеть, как это достигается, мы можем просто проследить за выполнением. Сначала у нас есть список [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, то результирующий список состоял бы просто из пустых кортежей. Вот определение в форме генератора списка: