списка, а если ложно отбросим первый элемент. Через 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.
Свёртка | 195
Вычислительные особенности 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:
196 | Глава 12: Структурная рекурсия
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
В этой функции за каждый узел мы прибавляем к результату единицу, а в списке находим максимум
среди всех поддеревьев.
12.2 Развёртка
С помощью развёртки мы постепенно извлекаем значение рекурсивного типа из значения какого-нибудь