другого типа. Этот процесс очень похож на процесс вычисления по имени. Сначала у нас есть отложенное
вычисление или thunk. Затем мы применяем к нему функцию редукции и у нас появляется корневой кон-
структор. А в аргументах конструктора снова сидят thunk’и. Мы применяем редукцию к ним. И так пока не
“развернём” всё значение.
Списки
Для разворачивания списков в Data.List есть специальная функция unfoldr. Присмотримся сначала к
её типу:
unfoldr :: (b -> Maybe (a, b)) -> b -> [a]
Функция развёртки принимает стартовый элемент, а возвращает значение типа пары от Maybe. Типом
Maybe мы кодируем конструкторы списка:
data [a] b where
(:)
:: a -> b -> b
— Maybe (a, b)
[]
:: b
— Nothing
Конструктор пустого списка не нуждается в аргументах, поэтому его мы кодируем константой Nothing.
Объединение принимает два аргумента голову и хвост, поэтому Maybe содержит пару из головы и следующего
элемента для разворачивания. Закодируем это определение:
unfoldr :: (b -> Maybe (a, b)) -> b -> [a]
unfoldr f = b -> case (f b) of
Just (a, b’) -> a : unfoldr f b’
Nothing
-> []
Или мы можем записать это более кратко с помощью свёртки maybe:
unfoldr :: (b -> Maybe (a, b)) -> b -> [a]
unfoldr f = maybe [] ((a, b) -> a : unfoldr f b)
Смотрите, перед нами коробочка (типа b) с подарком (типа a), мы разворачиваем, а там пара: подарок
(типа a) и ещё одна коробочка. Тогда мы начинаем разворачивать следующую коробочку и так далее по
цепочке, пока мы не развернём не обнаружим Nothing, это означает что подарки кончились.
Типичный пример развёртки это функция iterate. У нас есть стартовое значение типа a и функция по-
лучения следующего элемента a -> a
Развёртка | 197
iterate :: (a -> a) -> a -> [a]
iterate f = unfoldr $ s -> Just (s, f s)
Поскольку Nothing не используется цепочка подарков никогда не оборвётся. Если только нам не будет
лень их разворачивать. Ещё один характерный пример это функция zip:
zip :: [a] -> [b] -> [(a, b)]
zip = curry $ unfoldr $ x -> case x of
([]
, _)
-> Nothing
(_
, [])
-> Nothing
(a:as
, b:bs)
-> Just ((a, b), (as, bs))
Если один из списков обрывается, то прекращаем разворачивать. А если оба содержат голову и хвост, то
мы помещаем в голову списка пару голов, а в следующий элемент для разворачивания пару хвостов.
Потоки
Для развёртки хорошо подходят типы у которых, всего один конструктор. Тогда нам не нужно кодировать
альтернативы. Например рассмотрим потоки:
data Stream a = a :& Stream a
Они такие же как и списки, только без конструктора пустого списка. Функция развёртки для потоков
имеет вид:
unfoldStream :: (b -> (a, b)) -> b -> Stream a
unfoldStream f
= b -> case f b of
(a, b’) -> a :& unfoldStream f b’
И нам не нужно пользоваться Maybe. Напишем функции генерации потоков:
iterate :: (a -> a) -> a -> Stream a
iterate f = unfoldStream $ a -> (a, f a)
repeat :: a -> Stream a
repeat = unfoldStream $ a -> (a, a)
zip :: Stream a -> Stream b -> Stream (a, b)
zip = curry $ unfoldStream $ (a :& as, b :& bs) -> ((a, b), (as, bs))
Натуральные числа
Если присмотреться к натуральным числам, то можно заметить, что они очень похожи на списки. Списки
без элементов. Это отражается на функции развёртки. Для натуральных чисел мы будем возвращать не пару
а просто слкедующий элемент для развёртки:
unfoldNat :: (a -> Maybe a) -> a -> Nat
unfoldNat f = maybe Zero (Succ . unfoldNat f)
Напишем функцию преобразования из целых чисел в натуральные:
fromInt :: Int -> Nat
fromInt = unfoldNat f
where f n
| n == 0
= Nothing
| n >
0
= Just (n—1)
| otherwise = error ”negative number”
Обратите внимание на то, что в этом определении не участвуют конструкторы для Nat, хотя мы и строим
значение типа Nat. Конструкторы для Nat как и в случае списков кодируются типом Maybe. Развёртка ис-
пользуется гораздо реже свёртки. Возможно это объясняется необходимостью кодирования типа результата
некоторым промежуточным типом. Определения теряют в наглядности. Смотрим на функцию, а там Maybe
и не сразу понятно что мы строим: натуральные числа, списки или ещё что-то.
198 | Глава 12: Структурная рекурсия
12.3 Краткое содержание
В этой главе мы познакомились с особым видом рекурсии. Мы познакомились со структурной рекурсией.
Типы определяют не только значения, но и способы их обработки. Структурная рекурсия может быть выведе-
на из определения типа. Есть языки программирования, в которых мы определяем тип и получаем функции
структурной рекурсии в подарок. Есть языки, в которых структурная рекурсия является единственным воз-
можным способом составления рекурсивных функций.
Обратите внимание на то, что в этой главе мы определяли рекурсивные функции, но рекурсия встреча-
лась лишь в определении для функции свёртки и развёртки. Все остальные функции не содержали рекурсии,
более того почти все они определялись в бесточечном стиле. Структурная рекурсия это своего рода комби-
натор неподвижной точки, но не общий, а специфический для данного рекурсивного типа.
Структурная рекурсия бывает свёрткой и развёрткой.
Cвёрткой (fold) мы получаем значение некоторого произвольного типа из данного рекурсивного типа. При