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

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

listOfTuples :: [(Int,Char)]

listOfTuples = do

n <���– [1,2]

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

return (n,ch)

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

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

Генераторы списков позволяют нам фильтровать наши выходные данные. Например, мы можем отфильтровать список чисел в поиске только тех из них, которые содержат цифру 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)именно за три хода? Какой ход лучше сделать следующим из его нынешней позиции? Я знаю: как насчёт их всех?! К нашим услугам недетерминированность, поэтому вместо того, чтобы выбрать один ход, давайте просто выберем их все сразу! Вот функция, которая берёт позицию коня и возвращает все его следующие ходы: