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

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 тоже является такой, если вы рассмотрите её тип.