Изучай Haskell во имя добра!

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