Учебник по Haskell

Кажется мы ошиблись в аргументах, ведь 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 Развёртка

С помощью развёртки мы постепенно извлекаем значение рекурсивного типа из значения какого-нибудь

другого типа. Этот процесс очень похож на процесс вычисления по имени. Сначала у нас есть отложенное

вычисление или 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: