скажется на производительности. Особенно если в конце небольшие списки:
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 Развёртка
С помощью развёртки мы постепенно извлекаем значение рекурсивного типа из значения какого-нибудь
другого типа. Этот процесс очень похож на процесс вычисления по имени. Сначала у нас есть отложенное
вычисление или thunk. Затем мы применяем к нему функцию редукции и у нас появляется корневой кон-