“развернём” всё значение.
Списки
Для разворачивания списков в 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))
Если один из списков обрывается, то прекращаем разворачивать. А если оба содержат голову и хвост, то
мы помещаем в голову списка пару голов, а в следующий элемент для разворачивания пару хвостов.
Потоки