исходное положение. Каждым ходом мы двигаем одну фишку на пустое поле. В исходном положении фишки
идут по порядку.
9
1
4
8
1
2
3
4
13
11
5
5
6
7
8
2
10
7
3
9
10 11 12
15 14 12
6
13 14 15
Рис. 13.1: Случайное и конечное состояние игры пятнашки
Программа будет перемешивать фишки и отображать поле для игры. Она будет спрашивать следующий
ход и обновлять поле после хода. Если мы расставим все фишки по порядку, программа сообщит нам об этом
и предложит начать новую игру. В каждый момент мы можем не только сделать ход, но и покинуть игру или
начать всё заново. Известно, что не из любого положения можно расставить фишки по порядку. Поэтому наш
алгоритм перемешивания должен генерировать только такие позиции, для которых решение возможно.
Набросок решения
Программа, которую мы хотим написать, будет вести диалог с пользователем. Она показывает поле для
игры и спрашивает следующий ход. Потом она распознаёт ход, и показывает обновлённое поле. И так далее.
Нам нужно как-то организовать этот диалог.
При этом в программе можно выделить две независимые части. Одна отвечает за сам диалог. Она прини-
мает реплики пользователя и отображает поле для игры. А другая часть отвечает за правила игры пятнашки:
как ходы влияют на поле, какое положение является победным, как перемешивать фишки.
| 201
У нас будет два отдельных модуля: один для описания игры, назовём его Game, а другой для описания
диалога с пользователем. Мы назовём его Loop (петля или цикл), поскольку диалог это зацикленная проце-
дура получения реплики и реакции на реплику.
Такой вот набросок-ориентир. После этого можно приступать к реализации. Но с чего начать?
Каркас. Типы и классы
В Haskell программы обычно начинают строить с каркаса – с типов и классов. Нам нужно выделить ос-
новные сущности и подумать какие типы подходят для их описания лучше всего.
В нашей задаче есть поле с фишками и ходы. Мы делаем ходы и фишки двигаются. Поле – это матрица
или двумерный массив. У нас есть два индекса, которые пробегают значения от нуля до трёх. В каждой
ячейке массива хранятся фишки. Фишки обозначаются целыми числами:
type Pos
= (Int, Int)
type Label
= Int
type Board
= Array Pos Label
Пустую фишку мы будем также обозначать числом. Физически когда мы ходим, мы меняем положение
одной фишки. Но в нашем описании мы меняем местами две фишки, поскольку пустая фишка также обозна-
чается номером. Когда мы ходим, мы меняем положение пустой фишки, одним ходом мы можем сместить
её вверх, вниз, влево или вправо. Введём специальный тип для обозначения ходов:
data Move = Up | Down | Left | Right
Для того чтобы при каждом ходе не искать пустую клетку, давайте сохраним её текущее положение. Тип
Game будет содержать текущее положение пустой клетки и положение фишек:
data Game = Game {
emptyField
:: Pos,
gameBoard
:: Board }
Вот и все типы для описания игры. Сохраним их в модуле Game. Теперь подумаем о типах для диалога
с пользователем. В этом модуле наверняка будет много функций с типом IO, потому что в нём происходит
взаимодействие с игроком. Но, что является каркасом для диалога?
Если мы хотим с кем-нибудь общаться, необходимо чтобы у нас был с собеседником общий язык, он и
будет каркасом для диалога. Вспомним, что мы ожидаем от пользователя. Пользователь может:
• Сделать ход
• Начать новую игру
• Выйти из игры
Если пользователь делает ход мы показываем новое положение поля, если он начинает новую игру мы
показываем ему новую перемешанную позицию, давайте у нас будет разная степень перемешанности фи-
гур. При перемешивании мы стартуем из победного положения и начинаем случайным образом делать хо-
ды. Чем больше ходов мы сделаем тем сложнее будет собрать игру. Поэтому пользователь будет указывать
число шагов для перемешивания при запросе новой игры. Если пользователь попросит закончить игру мы
попрощаемся и выйдем из игры.
На основе этих рассуждений вырисовывается следующий тип для сообщений:
data Query = Quit | NewGame Int | Play Move
Значение типа Query (запрос) может быть константа Quit (выход), запрос новой игры NewGame с числом,
которое указывает на сложность новой игры, также игрок может просто сделать ход Play Move.
А каков формат наших ответов? Все наши ответы на самом деле будут вызовами функции putStrLn мы
будем отвечать пользователю изменениями экрана. Поэтому у нас нет специального типа для ответов. Итак
у нас есть каркас, который можно начинать покрывать значениями. На этом этапе у нас есть два модуля. Это
модуль Loop:
module Loop where
import Game
data Query = Quit | NewGame Int | Play Move
202 | Глава 13: Поиграем
И модуль Game:
module Game where
import Data.Array
data Move = Up | Down | Left | Right
deriving (Enum)
type Label = Int
type Pos = (Int, Int)
type Board = Array Pos Label
data Game = Game {
emptyField
:: Pos,
gameBoard
:: Board }
Ленивое программирование
Мы уже знаем как происходят ленивые вычисления. Мы принимаем выражение и начинаем очищать его
от синонимов от корня к листьям или сверху вниз. Оказывается таким способом можно писать программы.
Более того в функциональном программировании это очень распространённый подход. Мы начинаем со
спецификации задачи (неформального описания) и потихоньку вытягиваем из него выражения языка Haskell.
Начинаем мы с корня, с самой верхней функции. Эта функция будет состоять из подвыражений. Когда мы
напишем верхнюю функцию, мы перейдём к подвыражениям. И так мы будем спускаться пока не напишем
всю программу.
Кажется, что такой подход очень не надёжен. Ведь мы сможем запустить программу только когда напи-
шем её целиком. На каждом промежуточном шаге у нас есть неопределённые подвыражения. Получается,
что очень долгое время мы будем писать программу, не зная работает она или нет.
Оказывается, что в Haskell есть решение этой проблемы. Нам поможет значение undefined. Мы будем
писать только тип функции (и мысленно будем говорить, пусть она делает то-то), а вместо определения
будем писать undefined. При этом конечно мы не сможем выполнять программу, вычислитель подорвётся
на первом же значении, но мы сможем узнать осмысленна ли наша программа с точки зрения компилятора,
проходит ли она проверку типов. В Haskell это большой плюс. Если программа прошла проверку типов, то
скорее всего она будет работать.
Такой подход написания программ называется написанием сверху вниз. Мы начинаем с самой верхней
функции и потихоньку вычищаем все undefined. Если вспомнить ленивые вычисления, то там роль undefined
выполняли отложенные вычисления.
В чём преимущества такого подхода? Посмотрим на дерево (рис. ?? ). Если мы идём сверху вниз, то в
самом начале у нас лишь одна задача, потом их становится всё больше и больше. Они дробятся, но источ-
ник у них один. Мы всегда знаем, что нам нужно чтобы закончить нашу задачу. Написать это, это и это
подвыражение. Беда только в том, что это подвыражение содержит ещё больше подвыражений. Но сложные
подвыражения мы можем оставить на потом и заняться другими. А потом, когда мы их доделаем может вдруг
оказаться, что это сложное выражение нам и не нужно.
Рис. 13.2: Дерево задач
Стратегия написания программ | 203
Если же мы начинаем идти из листьев, то у нас много отправных точек, которые должны сойтись в одной
цели. При этом они могут и не сойтись, мы можем застрять в одной точке и потратить слишком много
