Учебник по Haskell

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

этом все конструкторы заменяются на функции, которые возвращают новый тип.

Развёрткой (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)