shuffle1 :: Game -> IO Game
shuffle1 g = flip move g (randomElem $ nextMoves g)
randomElem :: [a] -> IO a
randomElem = un
nextMoves :: Game -> [Move]
nextMoves = un
Нам осталось определить всего две функции, и всё готово для игры. Определим выбор случайного эле-
мента из списка:
import System.Random
…
randomElem :: [a] -> IO a
randomElem xs = (xs !! ) randomRIO (0, length xs — 1)
Мы генерируем случайное число в диапазоне индексов списка и затем извлекаем элемент. Теперь функ-
ция определения ходов в текущем положении:
nextMoves g = filter (within . moveEmptyTo . orient) allMoves
where moveEmptyTo v = shift v (emtyField g)
allMoves = [Up, Down, Left, Right]
Мы выполняем схожие операции с теми, что были в функции move. Мы фильтруем из списка всех ходов
те, что выводят пустую фишку за пределы доски.
212 | Глава 13: Поиграем
Отображение положения
Я немного поторопился, нам осталась ещё одна функция. Это отображение позиции. Я не буду подробно
останавливаться на теле функции, скажу лишь то, что она составляет строку так как это показано в коммен-
тарии к функции.
—
+—-+—-+—-+—-+
—
|
1 |
2 |
3 |
4 |
—
+—-+—-+—-+—-+
—
|
5 |
6 |
7 |
8 |
—
+—-+—-+—-+—-+
—
|
9 | 10 | 11 | 12 |
—
+—-+—-+—-+—-+
—
| 13 | 14 | 15 |
|
—
+—-+—-+—-+—-+
—
instance Show Game where
show (Game _ board) = ”n” ++ space ++ line ++
(foldr (a b -> a ++ space ++ line ++ b) ”n” $ map column [0 .. 3])
where post id = showLabel $ board ! id
showLabel n
= cell $ show $ case n of
15 -> 0
n
-> n+1
cell ”0”
= ”
”
cell [x]
= ’ ’:’ ’: x :’ ’:[]
cell [a,b] = ’ ’: a : b :’ ’:[]
line = ”+—-+—-+—-+—-+n”
nums = ((space ++ ”|”) ++ ) . foldr (a b -> a ++ ”|” ++ b) ”n” .
map post
column i = nums $ map (x -> (i, x)) [0 .. 3]
space = ”t”
Теперь мы можем загрузить модуль Loop в интерпретатор и набрать play. Немного отвлечёмся и поигра-
ем.
Prelude> :l Loop
[1 of 2] Compiling Game
( Game. hs, interpreted )
[2 of 2] Compiling Loop
( Loop. hs, interpreted )
Ok, modules loaded: Loop, Game.
*Loop> play
Привет! Это игра пятнашки
+—-+—-+—-+—-+
|
1 |
2 |
3 |
4 |
+—-+—-+—-+—-+
|
5 |
6 |
7 |
8 |
+—-+—-+—-+—-+
|
9 | 10 | 11 | 12 |
+—-+—-+—-+—-+
| 13 | 14 | 15 |
|
+—-+—-+—-+—-+
Возможные ходы пустой клетки:
left
или l
— налево
right
или r
— направо
up
или u
— вверх
down
или d
— вниз
Другие действия:
new int
или n int — начать новую игру, int — целое число,
указывающее на сложность
quit
или q
— выход из игры
Начнём новую игру?
Укажите сложность (положительное целое число):
5
+—-+—-+—-+—-+
|
1 |
2 |
3 |
4 |
+—-+—-+—-+—-+
|
5 |
6 |
7 |
8 |
+—-+—-+—-+—-+
Пятнашки | 213
|
9 |
| 10 | 11 |
+—-+—-+—-+—-+
| 13 | 14 | 15 | 12 |
+—-+—-+—-+—-+
Ваш ход:
r
+—-+—-+—-+—-+
|
1 |
2 |
3 |
4 |
+—-+—-+—-+—-+
|
5 |
6 |
7 |
8 |
+—-+—-+—-+—-+
|
9 | 10 |
| 11 |
+—-+—-+—-+—-+
| 13 | 14 | 15 | 12 |
+—-+—-+—-+—-+
Ваш ход:
r
+—-+—-+—-+—-+
|
1 |
2 |
3 |
4 |
+—-+—-+—-+—-+
|
5 |
6 |
7 |
8 |
+—-+—-+—-+—-+
|
9 | 10 | 11 |
|
+—-+—-+—-+—-+
| 13 | 14 | 15 | 12 |
+—-+—-+—-+—-+
Ваш ход:
d
+—-+—-+—-+—-+
|
1 |
2 |
3 |
4 |
+—-+—-+—-+—-+
|
5 |
6 |
7 |
8 |
+—-+—-+—-+—-+
|
9 | 10 | 11 | 12 |
+—-+—-+—-+—-+
| 13 | 14 | 15 |
|
+—-+—-+—-+—-+
Игра окончена.
Ураа, получилось. Мы так долго писали программу, проверяя лишь типы, и в самом конце, когда мы
закончили определение, всё работает. Конечно не всё работает так гладко, я уже написал эту программу и
объясняю готовое решение, но когда общая схема программы утряслась, возможные ошибки определяются
на раз. Мы могли вызвать отображение позиции не в том порядке или забыть проверку конца игры, всё это
несколько строчек изменений.
Самые неприятные ошибки происходят, когда в середине выясняется, что мы ошиблись с типами. Типы,
которые мы выбрали не могут описать явление, возможно мы не можем делать какие-то операции, которые
нам, как неожиданно выяснилось, очень нужны. Это значит, что нужно менять каркас. Менять каркас, это
значит сносить весь дом и строить новый. Возможно разрушения окажутся локальными, мы строим не дом,
а город. И сносить придётся не всё, а несколько кварталов. Но это тоже большие перемены. Поэтому шаг
определения типов очень важен. Впрочем сносить кварталы в Haskell одно удовольствие, посольку стоит
нам изменить какой-нибудь тип, например убрать какой-нибудь тип или изменить имя, компилятор тут же
подскажет нам какие функции стали бессмысленными. Более коварные изменения связаны с добавлением
конструктора-альтернативы. Например нам вдруг не понравился тип Bool и мы решили сделать его более
человечным. Мы решили добавить ещё одно значение:
data Bool = True | False | IDonTKnow
Это может привести к неполному рассмотрению альтернатив в case-выражениях и сопоставлениях с об-
разцом в аргументах функции. Такие ошибки крайн неприятны, поскольку они происходят на этапе выпол-
нения программы, когда новое значение IDonTKnow дойдёт до case. В этом случае нам на выручку может
прийти функция свёртки, если мы вместе с типом изменим и функцию свёртки, это скажется на всех функ-
циях, которые были определены через неё. Чем больше таких функций, тем больше ошибок мы поймаем.
214 | Глава 13: Поиграем
13.3 Упражнения
• Измените диалог с пользователем. Сделайте так чтобы у игры было главное меню, в котором игрок
выбирает разные побочные функции, вроде выхода, начать новую игру, подсказка и игровое меню, в
котором игрок только передвигает фишки. Когда игрок собирает игру он попадает в главное меню.
• Добавьте в игру подсчёт статистики. Если игрок дошёл до победной позиции он узнаёт за сколько ходов
ему удалось решить задачу. Также ведётся история предыдущих попыток, по которой пользователь
может следить как изменяются его результаты.
• Подумайте можно ли выделить интерфейс игры в отдельный класс так, чтобы модуль Loop не зависел
от конкретной реализации игры. Чтобы можно было, опираясь на абстрактные методы, вроде show для
Game, или реакции на ход, вести диалог с пользователем. Попробуйте переписать игру пятнашки с
помощью такого класса.
• Попробуйте написать другую игру, например игру раскладывания пасьянса, крестики-нолики или
шашки, не меняя модуля Loop. Так чтобы вы сделали необходимые экземпляры для классов из преды-
дущего упражнения, а всё остальное поведение следовало из них.
Упражнения | 215
Глава 14
Лямбда-исчисление
В этой главе мы узнаем о лямбда-исчислении. Лямбда-исчисление описывает понятие алгоритма. Ещё
до появления компьютеров в 30-е годы двадцатого века математиков интересовал вопрос о возможности со-
здания алгоритма, который мог бы на основе заданных аксиом дать ответ о том верно или нет некоторое
логическое высказывание. Например у нас есть базовые утверждения и логические связки такие как “и”,
“или”, “для любого из”, “существует один из”, с помощью которых мы можем строить из базовых высказы-
ваний составные. Некоторые из них окажутся ложными, а другие истинными. Нам интересно узнать какие.
Но для решения этой задачи прежде всего необходимо было понять а что же такое алгоритм?
Ответ на этот вопрос дали Алонсо Чёрч (Alonso Church) и Алан Тьюринг (Alan Turing). Чёрч разработал
лямбда-исчисление, а Тьюринг теорию машин Тьюринга. Оказалось, что задача автоматического определе-
