Структурная рекурсия определяет способ построения и преобразования значений по виду типа (по составу его конструкторов). Функции, которые преобразуют значения мы будем называть свёрткой (fold), а функции которые строят значения – развёрткой (unfold). Эта рекурсия встречается очень часто, мы уже пользовались ею и не раз, но в этой главе мы остановимся на ней поподробнее.
Свёртку значения можно представить как процесс, который заменяет в дереве значения все конструкторы на подходящие по типу функции.
Вспомним определение логических значений:
data Bool = True | False
У нас есть два конструктора-константы. Любое значение типа Bool может состоять либо из одного конструктора True, либо из одного конструктора False. Функция свёртки в данном случае принимает две константы одинакового типа a и возвращает функцию, которая превращает значение типа Bool в значение , заменяя конструкторы на переданные значения:
foldBool :: a -> a -> Bool -> a
foldBool true false = \b -> case b of
True -> true
False -> false
Мы написали эту функцию в композиционном стиле для того, чтобы подчеркнуть, что функция преобразует значение типа Bool. Определим несколько знакомых функций через функцию свёртки, начнём с отрицания:
not :: Bool -> Bool not = foldBool False True
Мы поменяли конструкторы местами, если на вход поступит True, то мы вернём False и наоборот. Теперь посмотрим на “и” и “или”:
(||), (&&) :: Bool -> Bool -> Bool (||) = foldBool (const True) id (&&) = foldBool id (const False)
Определение функций “и” и “или” через свёртки подчёркивает, что они являются взаимно обратными. Смотрите, эти функции принимают значение типа Bool и возвращают функцию Bool -> Bool. Фактически функция свёртки для Bool является if-выражением, только в этот раз мы пишем условие в конце.
У нас был тип для натуральных чисел Пеано:
data Nat = Zero | Succ Nat
Помните мы когда-то записывали определения типов в стиле классов:
data Nat where
Zero :: Nat
Succ :: Nat -> Nat
Если мы заменим конструктор Zero на значение типа a, то конструктор Succ нам придётся заменять на функцию типа a -> a, иначе мы не пройдём проверку типов. Представим, что Nat это класс:
data Nat a where
zero :: a
succ :: a -> a
Из этого определения следует функция свёртки:
foldNat :: a -> (a -> a) -> (Nat -> a)
foldNat zero succ = \n -> case n of
Zero -> zero
Succ m -> succ (foldNat zero succ m)
Обратите внимание на рекурсивный вызов функции foldNat мы обходим всё дерево значения, заменяя каждый конструктор. Определим знакомые функции через свёртку:
isZero :: Nat -> Bool isZero = foldNat True (const False)
Посмотрим как вычисляется эта функция:
isZero Zero
=> True -- заменили конструктор Zero
isZero (Succ (Succ (Succ Zero)))
=> const False (const False (const False True))
-- заменили и Zero и Succ
=> False
Что интересно за счёт ленивых вычислений на самом деле во втором выражении произойдёт лишь одна замена. Мы не обходим всё дерево, нам это и не нужно, а смотрим лишь на первый конструктор, если там Succ, то произойдёт замена на постоянную функцию, которая игнорирует свой второй аргумент и рекурсивного вызова функции свёртки не произойдёт, совсем как в исходном определении!
even, odd :: Nat -> Bool even = foldNat True not odd = foldNat False not
Эти функции определяют чётность числа, здесь мы пользуемся тем свойством, что not (not a) == a.
Определим сложение и умножение:
add, mul :: Nat -> Nat -> Nat add a = foldNat a Succ mul a = foldNat Zero (add a)
Вспомним определение типа для результата частично определённых функций:
data Maybe a = Nothing | Just a
Перепишем словно это класс:
data Maybe a b where
Nothing :: b
Just :: a -> b
Этот класс принимает два параметра, поскольку исходный тип Maybe принимает один. Теперь несложно догадаться как будет выглядеть функция свёртки, мы просто получим стандартную функцию maybe. Дадим определение экземпляра функтора и монады через свёртку:
instance Functor Maybe where
fmap f = maybe Nothing (Just . f)
instance Monad Maybe where
return = Just
ma >>= mf = maybe Nothing mf ma
Функция свёртки для списков это функция foldr. Выведем её из определения типа:
data [a] = a : [a] | []
Представим, что это класс:
class [a] b where
cons :: a -> b -> b
nil :: b
Теперь получить определение для foldr совсем просто:
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr cons nil = \x -> case x of
a:as -> a `cons` foldr cons nil as
[] -> nil
Мы обходим дерево значения, заменяя конструкторы методами нашего воображаемого класса. Определим несколько стандартных функций для списков через свёртку.
Первый элемент списка:
head :: [a] -> a head = foldr const (error "empty list")
Объединение списков:
(++) :: [a] -> [a] -> [a] a ++ b = foldr (:) b a
В этой функции мы реконструируем заново первый список но в самом конце заменяем пустой список в хвосте a на второй аргумент, так и получается объединение списков. Обратите внимание на эту особенность, скорость выполнения операции (++) зависит от длины первого списка. Поэтому между двумя выражениями
((a ++ b) ++ c) ++ d a ++ (b ++ (c ++ d))
Нет разницы в итоговом результате, но есть огромная разница по скорости вычисления! Второй гораздо быстрее. Убедитесь в этом! Реализуем объединение списка списков в один список:
concat :: [[a]] -> [a] concat = foldr (++) []
Через свёртку можно реализовать и функцию преобразования списков:
map :: (a -> b) -> [a] -> [b] map f = foldr ((:) . f) []
Если смысл выражения ((:) . f) не совсем понятен, давайте распишем его типы:
f (:) a -------> b -------> ([b] -> [b])
Напишем функцию фильтрации:
filter :: (a -> Bool) -> [a] -> [a] filter p = foldr (\a as -> foldBool (a:as) as (p a)) []
Тут у нас целых две функции свёртки. Если значение предиката p истинно, то мы вернём все элементы списка, а если ложно отбросим первый элемент. Через foldr можно даже определить функцию с хвостовой рекурсией foldl. Но это не так просто. Всё же попробуем. Для этого вспомним определение:
foldl :: (a -> b -> a) -> a -> [b] -> a foldl f s [] = s foldl f s (a:as) = foldl f (f s a) as
Нам нужно привести это определение к виду foldr, нам нужно выделить два метода воображаемого класса списка cons и nil:
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr cons nil = \x -> case x of
a:as -> a `cons` foldr cons nil as
[] -> nil
Перенесём два последних аргумента определения foldl в правую часть, воспользуемся лямбда-функциями и case-выражением:
foldl :: (a -> b -> a) -> [b] -> a -> a
foldl f = \x -> case x of
[] -> \s -> s
a:as -> \s -> foldl f as (f s a)
Мы поменяли местами порядок следования аргументов (второго и третьего). Выделим тождественную функцию в первом уравнении case-выражения и функцию композиции во втором.
foldl :: (a -> b -> a) -> [b] -> a -> a
foldl f = \x -> case x of
[] -> id
a:as -> foldl f as . (flip f a)
Теперь выделим функции cons и nil:
foldl :: (a -> b -> a) -> [b] -> a -> a
foldl f = \x -> case x of
[] -> nil
a:as -> a `cons` foldl f as
where nil = id
cons = \a b -> b . flip f a
= \a -> ( . flip f a)
Теперь запишем через foldr:
foldl :: (a -> b -> a) -> a -> [b] -> a foldl f s xs = foldr (\a -> ( . flip f a)) id xs s
Кажется мы ошиблись в аргументах, ведь foldr принимает три аргумента. Дело в том, что в функции foldr мы сворачиваем списки в функции, последний аргумент предназначен как раз для результирующей функции. Отметим, что из определения можно исключить два последних аргумента с помощью функции flip.
Если посмотреть на выражение, которое получается в результате вычисления foldr и foldl можно понять почему они так называются.
В левой свёртке foldl скобки группируются влево, поэтому на конце l (left):
foldl f s [a1, a2, a3, a4] =
(((s `f` a1) `f` a2) `f` a3) `f` a4
В правой свёртке foldr скобки группируются вправо, поэтому на конце r (right):
foldr f s [a1, a2, a3, a4]
a1 `f` (a2 `f` (a3 `f` (a4 `f` s)))
Кажется, что если функция f ассоциативна
(a `f` b) `f` c = a `f` (b `f` c)
то нет разницы какую свёртку применять. Разницы нет по смыслу, но может быть существенная разница в скорости вычисления. Рассмотрим функцию concat, ниже два определения:
concat = foldl (++) [] concat = foldr (++) []
Какое выбрать? Результат и в том и в другом случае одинаковый (функция ++ ассоциативна). Стоит выбрать вариант с правой свёрткой. В первом варианте скобки будут группироваться влево, это чудовищно скажется на производительности. Особенно если в конце небольшие списки:
Prelude> let concatl = foldl (++) [] Prelude> let concatr = foldr (++) [] Prelude> let x = [1 .. 1000000] Prelude> let xs = [x,x,x] ++ map return x
Последним выражением мы создали список списков, в котором три списка по миллиону элементов, а в конце миллион списков по одному элементу. Теперь попробуйте выполнить concatl и concatr на списке xs. Вы заметите разницу по скорости печати. Также для сравнения можно установить флаг: :set +s.
Также интересной особенностью foldr является тот факт, что за счёт ленивых вычислений foldr не нужно знать весь список, правая свёртка может работать и на бесконечных списках, в то время как foldl не вернёт результат, пока не составит всё выражение. Например такое выражение будет вычислено:
Prelude> foldr (&&) undefined $ True : True : repeat False False
За счёт ленивых вычислений мы отбросили оставшуюся (бесконечную) часть списка. По этим примерам может показаться, что левая свёртка такая не нужна совсем, но не все операции ассоциативны. Иногда полезно собирать результат в обратном порядке, например так в Prelude определена функция reverse, которая переворачивает список:
reverse :: [a] -> [a] reverse = foldl (flip (:)) []
Мы можем определить свёртку и для деревьев. Вспомним тип:
data Tree a = Node a [Tree a]
Запишем в виде класса:
data Tree a b where
node :: a -> [b] -> b
В этом случае есть одна тонкость. У нас два рекурсивных типа: само дерево и внутри него – список. Для преобразования списка мы воспользуемся функцией map:
foldTree :: (a -> [b] -> b) -> Tree a -> b
foldTree node = \x -> case x of
Node a as -> node a (map (foldTree node) as)
Найдём список всех меток:
labels :: Tree a -> [a] labels = foldTree $ \a bs -> a : concat bs
Мы объединяем все метки из поддеревьев в один список и присоединяем к нему метку из текущего узла.
Сделаем дерево экземпляром класса Functor:
instance Functor Tree where
fmap f = foldTree (Node . f)
Очень похоже на map для списков. Вычислим глубину дерева:
depth :: Tree a -> Int depth = foldTree $ \a bs -> 1 + foldr max 0 bs
В этой функции за каждый узел мы прибавляем к результату единицу, а в списке находим максимум среди всех поддеревьев.
С помощью развёртки мы постепенно извлекаем значение рекурсивного типа из значения какого-нибудь другого типа. Этот процесс очень похож на процесс вычисления по имени. Сначала у нас есть отложенное вычисление или 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) . f
Смотрите, перед нами коробочка (типа b) с подарком (типа a), мы разворачиваем, а там пара: подарок (типа a) и ещё одна коробочка. Тогда мы начинаем разворачивать следующую коробочку и так далее по цепочке, пока мы не развернём не обнаружим Nothing, это означает что подарки кончились.
Типичный пример развёртки это функция iterate. У нас есть стартовое значение типа a и функция получения следующего элемента a -> a
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) . 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 и не сразу понятно что мы строим: натуральные числа, списки или ещё что-то.
В этой главе мы познакомились с особым видом рекурсии. Мы познакомились со структурной рекурсией. Типы определяют не только значения, но и способы их обработки. Структурная рекурсия может быть выведена из определения типа. Есть языки программирования, в которых мы определяем тип и получаем функции структурной рекурсии в подарок. Есть языки, в которых структурная рекурсия является единственным возможным способом составления рекурсивных функций.
Обратите внимание на то, что в этой главе мы определяли рекурсивные функции, но рекурсия встречалась лишь в определении для функции свёртки и развёртки. Все остальные функции не содержали рекурсии, более того почти все они определялись в бесточечном стиле. Структурная рекурсия это своего рода комбинатор неподвижной точки, но не общий, а специфический для данного рекурсивного типа.
Структурная рекурсия бывает свёрткой и развёрткой.
мы получаем значение некоторого произвольного типа из данного рекурсивного типа. При этом все конструкторы заменяются на функции, которые возвращают новый тип.
мы получаем из произвольного типа значение данного рекурсивного типа. Мы словно разворачиваем его из значения, этот процесс очень похож на ленивые вычисления.
Мы узнали некоторые стандартные функции структурной рекурсии: cond или if-выражения, maybe, foldr, unfoldr.
Определите развёртку для деревьев из модуля 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)
Поэкспериментируйте в интерпретаторе с только что определёнными функциями и теми функциями, что мы определяли в этой главе.
Рассмотрим ещё один стандартный тип. Он определён в Prelude. Это тип Either (дословно – один из двух). Этот тип принимает два параметра:
data Either a b = Left a | Right b
Значение может быть либо значением типа a, либо значением типа b. Часто этот тип используют как Maybe с информацией об ошибке. Конструктор Left хранит сообщение об ошибке, а конструктор Right значение, если его удалось вычислить.
Например мы можем сделать такие определения:
headSafe :: [a] -> Either String a headSafe [] = Left "Empty list" headSafe (x:_) = Right x divSafe :: Fractional a => a -> a -> Either String a divSafe a 0 = Left "division by zero" divSafe a b = Right (a/b)
Для этого типа также определена функция свёртки она называется either. Не подглядывая в Prelude, определите её.
Список является частным случаем дерева. Список это дерево, в каждом узле которого, лишь один дочерний узел. Деревья из модуля Data.Tree похожи на списки, но есть в них одно существенное отличие. Они всегда содержат хотя бы один элемент. Пустой список не может быть представлен в виде такого дерева. Например это различие сказывается, если вы захотите определить функцию-аналог takeWhile для деревьев.
Определите деревья, которые не страдают от этого недостатка. Определите для них функции свёртки/развёртки, а также функции, которые мы определили для стандартных деревьев. Определите функцию takeWhile (в рекурсивном виде и в виде развёртки) и сделайте их экземпляром класса Monad, похожий на экземпляр для списков.