альтернативы. Например рассмотрим потоки:
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) мы получаем значение некоторого произвольного типа из данного рекурсивного типа. При