отличие. Они всегда содержат хотя бы один элемент. Пустой список не может быть представлен в виде
такого дерева. Например это различие сказывается, еслим вы захотите определить функцию-аналог
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: Случайное и конечное состояние игры пятнашки
Программа будет перемешивать фишки и отображать поле для игры. Она будет спрашивать следующий
ход и обновлять поле после хода. Если мы расставим все фишки по порядку, программа сообщит нам об этом
и предложит начать новую игру. В каждый момент мы можем не только сделать ход, но и покинуть игру или
начать всё заново. Известно, что не из любого положения можно расставить фишки по порядку. Поэтому наш