Структурная рекурсия

Структурная рекурсия определяет способ построения и преобразования значений по виду типа (по составу его конструкторов). Функции, которые преобразуют значения мы будем называть свёрткой (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)

Maybe

Вспомним определение типа для результата частично определённых функций:

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.

Вычислительные особенности foldl и foldr

Если посмотреть на выражение, которое получается в результате вычисления 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 и не сразу понятно что мы строим: натуральные числа, списки или ещё что-то.

Краткое содержание

В этой главе мы познакомились с особым видом рекурсии. Мы познакомились со структурной рекурсией. Типы определяют не только значения, но и способы их обработки. Структурная рекурсия может быть выведена из определения типа. Есть языки программирования, в которых мы определяем тип и получаем функции структурной рекурсии в подарок. Есть языки, в которых структурная рекурсия является единственным возможным способом составления рекурсивных функций.

Обратите внимание на то, что в этой главе мы определяли рекурсивные функции, но рекурсия встречалась лишь в определении для функции свёртки и развёртки. Все остальные функции не содержали рекурсии, более того почти все они определялись в бесточечном стиле. Структурная рекурсия это своего рода комбинатор неподвижной точки, но не общий, а специфический для данного рекурсивного типа.

Структурная рекурсия бывает свёрткой и развёрткой.

Cвёрткой (fold)

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

Развёрткой (unfold)

мы получаем из произвольного типа значение данного рекурсивного типа. Мы словно разворачиваем его из значения, этот процесс очень похож на ленивые вычисления.

Мы узнали некоторые стандартные функции структурной рекурсии: cond или if-выражения, maybe, foldr, unfoldr.

Упражнения

Зарегистрировано под лицензией Creative commons Attribution-NonCommercial-NoDerivs 3.0 Generic (CC BY-NC-ND 3.0)