Учебник по Haskell

• Поэкспериментируйте в интерпретаторе с только что определёнными функциями и теми функциями,

что мы определяли в этой главе.

• Рассмотрим ещё один стандартный тип. Он определён в Prelude. Это тип Either (дословно – один из

двух). Этот тип принимает два параметра:

data Either a b = Left a | Right b

Значение может быть либо значением типа a, либо значением типа b. Часто этот тип используют как

Maybe с информацией об ошибке. Конструктор Left хранит сообщение об ошибке, а конструктор Right

значение, если его удалось вычислить.

Например мы можем сделать такие определения:

headSafe :: [a] -> Either String a

headSafe []

= Left ”Empty list”

headSafe (x:_)

= Right x

divSafe :: Fractional a => a -> a -> Either String a

divSafe a 0 = Left ”division by zero”

divSafe a b = Right (a/b)

Для этого типа также определена функция свёртки она называется either. Не подглядывая в Prelude,

определите её.

Краткое содержание | 199

• Список является частным случаем дерева. Список это дерево, в каждом узле которого, лишь однин

дочерний узел. Деревья из модуля Data.Tree похожи на списки, но есть в них одно существенное

отличие. Они всегда содержат хотя бы один элемент. Пустой список не может быть представлен в виде

такого дерева. Например это различие сказывается, еслим вы захотите определить функцию-аналог

takeWhile для деревьев.

Определите деревья, которые не страдают от этого недостатка. Определите для них функции свёрт-

ки/развёртки, а также функции, которые мы определили для стандартных деревьев. Определите функ-

цию takeWhile (в рекурсивном виде и в виде развёртки) и сделайте их экземпляром класса Monad,

похожий на экземпляр для списков.

200 | Глава 12: Структурная рекурсия

Глава 13

Поиграем

Вот и закончилась первая часть книги. Мы узнали основные конструкции языка Haskell. В этой главе

мы напишем законченную программу для игры в пятнашки. Ну или почти законченную, глава венчается

упражнениями.

13.1 Стратегия написания программ

Описание задачи

Решение задачи начинается с описания проблемы и наброска решения. Мы хотим создать программу,

в которой можно будет играть в пятнашки. Если вам не знакома это игра, то взгляните на рисунок. Игра

начинается с позиции, в которой все фишки перемешаны. Необходимо, переставляя фишки, вернуться в

исходное положение. Каждым ходом мы двигаем одну фишку на пустое поле. В исходном положении фишки

идут по порядку.

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

Пустую фишку мы будем также обозначать числом. Физически когда мы ходим, мы меняем положение

одной фишки. Но в нашем описании мы меняем местами две фишки, поскольку пустая фишка также обозна-

чается номером. Когда мы ходим, мы меняем положение пустой фишки, одним ходом мы можем сместить

её вверх, вниз, влево или вправо. Введём специальный тип для обозначения ходов: