Функция развёртки принимает стартовый элемент, а возвращает значение типа пары от 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: Структурная рекурсия