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

Если бы мы забыли представить образец 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