этом все конструкторы заменяются на функции, которые возвращают новый тип.
Развёрткой (unfold) мы получаем из произвольного типа значение данного рекурсивного типа. Мы словно
разворачиваем его из значения, этот процесс очень похож на ленивые вычисления.
Мы узнали некоторые стандартные функции структурной рекурсии: cond или if-выражения, maybe, foldr,
unfoldr.
12.4 Упражнения
• Определите развёртку для деревьев из модуля Data.Tree.
• Определите с помощью свёртки следующие функции:
sum, prod
:: Num a => [a] -> a
or,
and
:: [Bool] -> Bool
length
:: [a] -> Int
cycle
:: [a] -> [a]
unzip
:: [(a,b)] -> ([a],[b])
unzip3
:: [(a,b,c)] -> ([a],[b],[c])
• Определите с помощью развёртки следующие функции:
infinity
:: Nat
map
:: (a -> b) -> [a] -> [b]
iterateTree :: (a -> [a]) -> a -> Tree a
zipTree
:: Tree a -> Tree b -> Tree (a, b)
• Поэкспериментируйте в интерпретаторе с только что определёнными функциями и теми функциями,
что мы определяли в этой главе.
• Рассмотрим ещё один стандартный тип. Он определён в 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 программы обычно начинают строить с каркаса – с типов и классов. Нам нужно выделить ос-
новные сущности и подумать какие типы подходят для их описания лучше всего.
В нашей задаче есть поле с фишками и ходы. Мы делаем ходы и фишки двигаются. Поле – это матрица
или двумерный массив. У нас есть два индекса, которые пробегают значения от нуля до трёх. В каждой