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