Функциональное программирование на Haskell
Часть 4. Свертки списков
Серия контента:
Этот контент является частью # из серии # статей: Функциональное программирование на Haskell
Этот контент является частью серии:Функциональное программирование на Haskell
Следите за выходом новых статей этой серии.
Левая и правая свертка: foldl1, foldr1
Для начала мы разберем очень простую и распространенную задачу и то, как она решается в функциональных языках программирования. Пусть требуется найти минимальный элемент в списке. Запишем рекурсивное определение минимального элемента:
- Если список состоит из одного элемента x, то минимальный элемент — x.
- Если список состоит из двух и более элементов, то сравним первый элемент x с минимальным элементом x' среди оставшихся в хвосте xs. Если x меньше или равен x', то минимальный элемент — x, иначе — x'.
Во втором случае используется вычисление минимума среди двух элементов, для которого можно выделить специальную функцию min
.
min :: (Ord a) => a -> a -> a min x y = if x <= y then x else y
Эта функция, как и практически все другие, с которыми мы будем работать, уже имеется в Prelude (она определена для класса Ord
).
Назовем интересующую нас функцию для поиска минимума в списке minimum
. Ее определение будет состоять из двух уравнений, соответствующих словесному описанию выше.
minimum :: (Ord a) => [a] -> a minimum [x] = x minimum (x:xs) = min x (minimum xs)
Рассмотрим, как это будет вычисляться, на примере списка [3,1,9,0,5]:
minimum [3,1,9,0,5] = min 3 (minimum [1,9,0,5]) = min 3 (min 1 (minimum [9,0,5])) = min 3 (min 1 (min 9 (minimum [0,5]))) = min 3 (min 1 (min 9 (min 0 (minimum [5])))) = min 3 (min 1 (min 9 (min 0 5))) = min 3 (min 1 (min 9 0)) = min 3 (min 1 0) = min 3 0 = 0
Но если нам потребуется найти в списке максимум? Рассуждения будут точно такими же:
max :: (Ord a) => a -> a -> a max x y = if x >= y then x else y maximum :: (Ord a) => [a] -> a maximum [x] = x maximum (x:xs) = max x (maximum xs) maximum [3,1,9,0,5] = max 3 (maximum [1,9,0,5]) = max 3 (max 1 (maximum [9,0,5])) = max 3 (max 1 (max 9 (maximum [0,5]))) = max 3 (max 1 (max 9 (max 0 (maximum [5])))) = max 3 (max 1 (max 9 (max 0 5))) = max 3 (max 1 (max 9 5)) = max 3 (max 1 9) = max 3 9 = 9
Прослеживается общий шаблон: вычисление обеих функций основано на том, что по списку [x1, x2, …, xn-1, xn] строится выражение
f x1 (f x2 (... (f xn-1 xn))),
где f — некоторая функция, причем, если список имеет тип [a]
, то f должна иметь тип a -> a -> a
. В одном случае это min
, а в другом — max
.
Выражение f x1 (f x2 (... (f xn-1 xn)))
называется правой сверткой (right fold) списка [x1, x2, …, xn] при помощи функции f
.
По аналогии можно ввести левую свертку (left fold):
f (f ((f x1 x2) ...) xn-1) xn.
В более привычной инфиксной записи правая и левая свертка выглядят так (напомним, что применение функции можно записать инфиксно, если взять имя функции в обратные кавычки ` `):
x1 `f` x2 (... (`f` (xn-1 `f` xn))), (((x1 `f` x2) `f` ...) `f` xn-1) `f` xn.
На примерах для минимума и максимума видно, что удобно условиться, что свертка списка из одного элемента равна этому элементу.
Как вы могли догадаться, для минимума и максимума разницы между этими свертками нет, потому что для всех a, b и c
a `min` (b `min` c) = (a `min` b) `min` c, a `max` (b `max` c) = (a `max` b) `max` c.
Результат от расстановки скобок не зависит; то есть операции min
и max
ассоциативны. В общем случае свертка осуществляется неассоциативной операцией, поэтому важно различать левую и правую свертку. Кроме того, как мы увидим далее, вычисление левой и правой свертки значительно отличается.
Функциональный подход поощряет вынесение часто используемых шаблонов в функции высшего порядка; в данном случае мы можем обобщить определение функции minimum
, заменив в нем min
на произвольную функцию f
. Назовем обобщенную функцию foldr1
:
foldr1 :: (a -> a -> a) -> [a] -> a foldr1 f [x] = x foldr1 f (x:xs) = f x (foldr1 f xs)
foldr1
вычисляет правую свертку, поэтому ее можно также называть правой сверткой.
Запишем теперь левую свертку foldl1
.
foldl1 :: (a -> a -> a) -> [a] -> a foldl1 f [x] = x foldl1 f (x:(y:ys)) = foldl1 f (f x y : ys)
В Prelude определены именно такие функции.
Здесь результат свертки передается вглубь рекурсивных вызовов в виде головы списка.
Если переписать наши определения minimum
и maximum
через свертки, то получим
minimum = foldr1 min maximum = foldr1 max
(Напомним, что уравнение minimum = foldr1 min
эквивалентно minimum xs = foldr1 min xs
.)
Кроме того, можно использовать определение:
minimum = foldl1 min maximum = foldl1 max
Обратите внимание на различия во втором уравнении для foldr1
и foldl1
: значением foldr1 f (x:xs)
считается результат применения f, а значением foldl1 f (x:(y:ys))
— результат применения той же функции foldl1
.
Если результатом рекурсивного вызова функции считается результат вызова той же функции, то такая рекурсия называется хвостовой, а функция — хвосторекурсивной.
Таким образом, foldl1
, в отличие от foldr1
, хвосторекурсивна.
В функциональных языках хвостовая рекурсия имеет следующий практический смысл: если рекурсивный вызов хвостовой, то интерпретатор может не размещать элементы в стеке. Рассмотрим характерный пример определения:
length :: [a] -> Int length [] = 0 length (x:xs) = length xs + 1
Эта функция вычисляет длину списка.
Такая рекурсия не является хвостовой, потому что значением length (x:xs)
считается результат применения (+)
, а не length
. Ситуацию можно изменить, если ввести вспомогательную функцию length'
, которая накапливает результат в своем аргументе:
length xs = let length' n [] = n length' n (x:xs) = length' (n+1) xs in length' 0 xs
Но избавились ли мы от проблемы переполнения стека? На самом деле, в силу ленивости Haskell, вычисление (n+1)
будет до последнего откладываться! Мы оставим пока подробности и вернемся к нашему рассмотрению свёрток.
Рассмотрим функцию:
paren :: String -> String -> String paren x y = concat ["(",x," * ",y,")"]
С ней удобно проследить, как строятся правые и левые свертки:
ghci> foldr1 paren ["a","b","c","d"] "(a * (b * (c * d)))" ghci> foldl1 paren ["a","b","c","d"] "(((a * b) * c) * d)"
Если операция, по которой производится свертка, ассоциативна, то можно просто думать о расстановке оператора между элементами. Например,
foldr1 (+) [x1, x2, ..., xn] = x1 + x2 + ... + xn, foldr1 (*) [x1, x2, ..., xn] = x1 * x2 * ... * xn.
Значит, foldr1 (+)
и foldr1 (*)
выражают сумму и произведение:
ghci> foldr1 (+) [1..5] 15 ghci> foldr1 (*) [1..5] 120
Обобщение на случай пустого списка: foldl, foldr
Вернемся к примеру функции length
из предыдущего раздела. Ее можно тоже рассматривать как правую свертку некоторой функцией f
. Однако для пустого списка length [] = 0
, в то время, как наши определения foldr1
и foldl1
вообще не срабатывают для []
.
Разумно расширить значение свертки для пустого списка, опираясь в рекурсивном определении на этот случай. Назовем обобщенные функции foldr
и foldl
:
foldr :: (a -> b -> b) -> b -> [a] -> b foldr f x0 [] = x0 foldr f x0 (x:xs) = f x (foldr f x0 xs) foldl :: (b -> a -> b) -> b -> [a] -> b foldl f x0 [] = x0 foldl f x0 (x:xs) = foldl f (f x0 x) xs
Таким образом, базовое значение x0
как бы дописывается в начало (при foldl
) или в конец (при foldr
) списка, после чего уже производится свертка; если список пуст, то результатом свертки считается x0
.
f x1 (f x2 (... (f xn-1 (f xn x0)) ...)), f (f (... (f (f x0 x1) x2) ...) xn-1) xn.
Обратите внимание на различия в типах foldl1
и foldl
, foldr1
и foldr
.
Пусть функция длины должна выражаться через левую свертку функцией f
(n,x), где x — элемент списка, а n — накопленное значение свертки. Длина не зависит от значений элементов и увеличивается на 1 при переходе к последующему элементу, поэтому:
f n x = n + 1.
Имеем:
length :: [a] -> Int length = foldl (\ n _ -> n+1) 0
Это определение автоматически будет хвосторекурсивным, потому что левая свертка хвосторекурсивна. Если нас это не сильно заботит, то, очевидно, мы можем заменить левую свертку на правую.
В соответствии с новым определением foldl
можно дать более аккуратное определение foldl1
:
foldl1 f (x:xs) = foldl f x xs
Пример:
ghci> foldr paren "1" ["a","b","c","d"] "(a * (b * (c * (d * 1))))" ghci> foldl paren "1" ["a","b","c","d"] "((((1 * a) * b) * c) * d)"
Разумно требовать, чтобы обобщенные свертки foldr
и foldl
согласовывались со свертками foldr1
и foldl1
. Это налагает некоторые ограничения для базового значения, которое отвечает случаю пустого списка.
Для любого не пустого списка xs
foldl f x xs = foldl1 f xs
будет выполняться, только если для всех x
f x x = x;
такой элемент x0 называется левой единицей операции f. (Эта терминология основана на аналогии с умножением на 1.)
Аналогично, если для всех не пустых xs
foldr f x xs = foldr1 f xs,
то необходимо, чтобы для всех x выполнялось
f x x = x;
то есть x0 должен быть правой единицейf
.
Например, для умножения левой и правой, единицей будет 1, а для сложения — 0. Поэтому функции sum
и product
вводятся следующим образом:
sum :: (Num a) => [a] -> a sum = foldr (+) 0 product :: (Num a) => [a] -> a product = foldr (*) 1
Факториал можно записать в виде:
fac :: Integral a => a -> a fac n = product [1..n]
Аналогично, для логического И и логического ИЛИ:
and :: [Bool] -> Bool and = foldr (&&) True or :: [Bool] -> Bool or = foldr (||) False
Обратите внимание: True
— это единица для логического И, а False
— это единица для логического ИЛИ.
Для конкатенации двух списков используется бинарный оператор ++
(мы еще рассмотрим, как реализовать ее через свертки). Единицей у конкатенации является пустой список []
. Значит, конкатенацию n списков можно записать в виде:
concat :: [[a]] -> [a] concat = foldr (++) []
У операции не обязательно должна быть левая или правая единица — это можжет указывать на то, что нужно использовать foldl1
и foldr1
.
Дополнительные примеры
amean
Выше мы уже определили функции для вычисления суммы и длины списка. Разумно записать функцию для вычисления среднего арифметического:
amean xs = let s = sum xs n = (fromIntegral.length) xs in s/n
Но что происходит при вычислении? Сначала мы проходим весь список, вычисляя сумму, а затем снова проходим его, вычисляя длину.
Можно сразу накапливать результат в паре, хранящей сумму элементов и их количество. Если свертка правая, то первым аргументом сворачивающей функции должен быть текущий элемент, а вторым — накопленное значение. Здесь свертка будет осуществляться функцией
Y x (y,n) -> (x+y, n+1)
(Чтобы не путаться, запомните, что в правой свертке накопленное значение стоит справа, а в левой — слева.)
Получаем функцию:
amean :: (Fractional a) => [a] -> a amean xs = s/n where (s,n) = foldr (\ x (y,n) -> (x+y,n+1)) (0,0) xs
Если вы помните, что такое uncurry
:
amean = uncurry (/) . foldr (\ x (y,n) -> (x+y,n+1)) (0,0)
Для пустого списка []
функция будет вычислять 0/0 и давать значение NaN (Not a Number, неопределеный числовой результат). Если это неприемлемо, то лучше, конечно, доопределить:
amean [] = 0
Или выдавать ошибку при пустом списке.
Теперь мы выпишем компактные определения для стандартных функций, используя свертки.
++
Как реализовать операцию конкатенации ++
?
Чтобы вычислить xs ++ ys
, можно добавлять к началу ys
по одному элементу xs
, начиная с конца.
Как перейти от этой идеи к свертке?
- Слова «по одному элементу
xs
» указывают, что сворачиваетсяxs
. - Далее, «начиная с конца» означает, что свертка правая.
- «Добавлять к
ys
» говорит о том, чтоys
будет исходным значением. - Операции присоединения вперед соответствует
(:)
.
Это буквально оформляется в уравнение:
(++) :: [a] -> [a] -> [a] (++) xs ys = foldr (:) ys xs reverse
Обращение списка можно определить рекурсивно:
reverse [] = [] reverse (x:xs) = (reverse xs) ++ [x]
Например,
reverse [1,2,3] = reverse [2,3] ++ [1] = = reverse [3] ++ [2] ++ [1] = = reverse [] ++ [3] ++ [2] ++ [1] = = [] ++ [3] ++ [2] ++ [1] = = [3,2,1]
Видно, что мы осуществляем правую свертку функцией Y x y -> y ++ [x]
. Отсюда:
reverse = foldr (\ x y -> y ++ [x]) []
Мы получили аккуратный код, основанный на определении обращения списка, однако присоединение в конец ++[x]
— дорогая операция, в отличие от снятия и добавления головы.
Рассмотрим другой вариант: пусть имеются списки xs
и ys
. На начальном этапе xs
будет исходным списком, а ys
— пустым. Мы будем последовательно снимать голову с xs
и добавлять к ys
. Как только xs
будет пустым списком, ys
будет содержать элементы xs
, записанные в обратном порядке.
На примере списка [1,2,3]
это выглядит так:
xs | ys |
---|---|
1 : 2 : 3 : [] | [] |
2 : 3 : [] | 1 : [] |
3 : [] | 2 : 1 : [] |
[] | 3 : 2 : 1 : [] |
Запись в виде рекурсивной функции:
reverse xs = iter xs [] where iter [] ys = ys iter (x:xs) ys = iter (x:ys) xs
Здесь результат накапливается в ys
; начальное значение — []
. Свертка левая, потому что мы проходим xs
от начала к концу. Имеем функцию для свертки Y ys x -> x : ys
, то есть flip (:)
. Получаем окончательное решение:
reverse :: [a] -> [a] reverse = foldl (flip (:)) []
— для больших списков это гораздо быстрее, нежели вариант с правой сверткой!
map
В предыдущей статье мы уже разобрали, что такое отображение списка, а также записали рекурсивное определение:
map _ [] = [] map f (x:xs) = f x : map f xs
После примеров выше, несложно разобраться, что тут производится правая свертка функцией Y x xs -> f x : xs
. Более компактно ее можно записать в виде (:) . f
.
map :: (a -> b) -> [a] -> [b] map f = foldr ((:) . f) []
concatMap
Функция concatMap
работает как map
, но также склеивает результаты отображения:
concatMap f [x1, x2, ..., xn] = f x1 ++ f x2 ++ ... ++ f xn.
Задача решается аналогично map
. Сворачивать нужно функцией Y x xs -> f x ++ xs
, которая более компактно записывается бесточечно как (++) . f
.
concatMap :: (a -> [b]) -> [a] -> [b] concatMap f = foldr ((++) . f) []
elem
elem x xs
— предикат, выражающий принадлежность x
списку xs
. Рекурсивное определение:
elem x [] = False elem x (x':xs) = if x == x' then True else elem x xs
Очевидная запись через свертку:
elem :: (Eq a) => a -> [a] -> Bool elem x = foldl (\ s x' -> if x' == x then True else s) False
filter, partition
Функция filter f xs
для предиката f
и списка xs
вычисляет список, содержащий элементы, которые удовлетворяют предикату. Она похожа на map
, только функция свертки будет не присоединять f x
к хвосту, а проверять значение f x
и в зависимости от него присоединять x:
filter :: (a -> Bool) -> [a] -> [a] filter f = foldr (\ x xs -> if f x then x : xs else xs) []
partition
возвращает пару из двух списков: удовлетворяющего и не удовлетворяющего предикату.
partition :: (a -> Bool) -> [a] -> ([a],[a]) partition f = foldr iteratee ([],[]) where iteratee x (xs,xs') = if f x then (x:xs,xs') else (xs,x:xs')
Пример:
ghci> partition Data.Char.isUpper "Avoid success at all costs" ("A","void success at all costs") ghci> filter Data.Char.isUpper "Avoid success at all costs" "A"
intersperse, intercalate
Функция intersperse
должна принимать элемент x
и список xs
и возвращать список, в котором x
стоит между каждым элементом xs
.
Реализация может опираться на последовательное присоединение к пустому списку элементов xs
. Причем если присоединение осуществляется к непустому списку, то перед очередным элементом присоединяется x
.
intersperse :: a -> [a] -> [a] intersperse x = foldr f [] where f x' xs = x' : if null xs then xs else x:xs
intercalate
работает схожим образом, но размещает данный список между списками и склеивает результат (тип [a] -> [[a]] -> [a]
). Реализация такая же, только :
нужно заменить на ++
.
intercalate x = foldr f [] where f x' xs = x' ++ if null xs then xs else x++xs
С другой стороны, лучше использовать определение:
intercalate :: [a] -> [[a]] -> [a] intercalate x xs = concat $ intersperse x xs
Примеры:
ghci> intersperse ' ' "Avoid success at all costs" "A v o i d s u c c e s s a t a l l c o s t s" ghci> intercalate " " ["Avoid","success","at","all","costs"] "Avoid success at all costs"
Прогоны
Отдельно стоит рассмотреть прогон (scan) — близкую к свертке операцию, которая вместо одного свернутого значения возвращает список последовательных сверток. Для левого прогона
scanl f x0 [x1, x2, ...] = [x0, x0 `f` x1, (x0 `f` x1) `f` x2, ...]
первым элементом прогона будет начальное значение, а последним — результат левой свертки.
Определение scanl
:
scanl :: (a -> b -> a) -> a -> [b] -> [a] scanl _ x0 [] = [x0] scanl f x0 (x:xs) = x0 : scanl f (f x0 x) xs
По аналогии с тем, как foldl1
был определен через foldl
:
scanl1 :: (a -> a -> a) -> [a] -> [a] scanl1 _ [] = [] scanl1 f (x:xs) = scanl f x xs
Пример:
ghci> scanl1 paren ["a","b","c"] ["a","(a * b)","((a * b) * c)"] ghci> scanl paren "1" ["a","b","c"] ["1","(1 * a)","((1 * a) * b)","(((1 * a) * b) * c)"]
Как можно догадаться, правый прогон должен содержать начальное значение в качестве последнего элемента и результат правой свертки в качестве первого.
scanr :: (a -> b -> b) -> b -> [a] -> [b] scanr _ x0 [] = [x0] scanr f x0 (x:xs) = f x x' : (x':xs') where (x':xs') = scanr f x0 xs scanr1 :: (a -> a -> a) -> [a] -> [a] scanr1 _ [] = [] scanr1 _ [x0] = [x0] scanr1 f (x:xs) = f x x' : (x':xs') where (x':xs') = scanr1 f xs
Пример:
ghci> scanr1 paren ["a","b","c"] ["(a * (b * c))","(b * c)","c"] ghci> scanr paren "1" ["a","b","c"] ["(a * (b * (c * 1)))","(b * (c * 1))","(c * 1)","1"]
Обратите внимание, что, по соглашению, прогоны scanl1
и scanr1
пустого списка определены и равны пустому списку, а свертки foldl1
и foldr1
для пустых списков не определены.
Вычисление сверток
До настоящего момента мы практически не вдавались в различия между правой и левой сверткой в случае ассоциативной операции. Теперь разберемся подробнее, что происходит при вычислении.
Мы покажем в этом разделе ситуации, в которых проявляется специфика ленивых вычислений. Не волнуйтесь — это больше мотивирующие примеры, и они предваряют серьезный разговор о вычислениях, который ждет нас в последующих статьях.
Деревья сверток
Рассмотрим свертку списка [1,2,3,4]
при помощи (+)
. Если вспомнить, что запись [1,2,3,4]
— это просто сокращение для 1 : (2 : (3 : (4 : [])))
, то дерево списка выглядит так:
Рис. 1. Дерево списка [1,2,3,4]
![Рис. 1. Дерево списка [1,2,3,4]](tree-1.png)
Правой свертке foldr (+) 0 [1..4]
соответствует выражение 1 + (2 + (3 + (4 + 0)))
со следующим деревом:
Рис. 2. Дерево выражения 1 + (2 + (3 + (4 + 0)))

Кликните, чтобы увидеть увеличенное изображение
То есть в дереве пустой список []
был заменен на исходное значение 0
, а конструкторы :
в узлах — на операцию +
. Левой сверткой будет (((0 + 1) + 2) + 3) + 4
со следующим деревом:
Рис. 3. Дерево выражения (((0 + 1) + 2) + 3) + 4

Кликните, чтобы увидеть увеличенное изображение
При правой свертке дерево строится сверху вниз. На нашем примере можно заключить, что вычисление производится снизу вверх (то есть, нужно рекурсивно спуститься вниз дерева, и уже оттуда производить сложение), но это лишь потому, что (+)
является строгой по обоим аргументам. Для нестрогого оператора это не обязательно так.
Свертка бесконечного списка
Рассмотрим
k x y = x
Свернем этой функцией бесконечный список из всех положительных целых чисел. Правая свертка даст 1
:
foldr1 k [1..] = (\ x y -> x) 1 (foldr1 k [2..]) = 1
Но для левой свертки дерево будет строиться бесконечно, и результат не будет найден:
foldl1 k [1..] = foldl1 k (k 1 2) [3..] = = foldl1 k (k (k 1 2) 3) [4..] = = foldl1 k (k (k (k 1 2) 3) 4) [5..] = = ...
Заметьте, что операция ассоциативна — для всех x, y, z выполняется
(x `k` y) `k` z = x `k` y = x, x `k` (y `k` z) = x.
Поэтому всё дело в принятом порядке вычисления.
При левой свертке дерево строится снизу вверх, и последние элементы находятся в вершине. Значит, для бесконечного списка левую свертку вычислить нельзя.
«Строгая» свертка foldl'
Интересно рассмотреть вычисление для строгой операции и конечного, но достаточно большого списка:
foldr1 (+) [1..10^6] = (+) 1 (foldr1 (+) [2..10^6]) = = (+) 1 ((+) 2 (foldr1 (+) [3..10^6])) = = (+) 1 ((+) 2 ((+) 3 (foldr1 (+) [4..10^6]))) = = ...
Функция (+)
требует, чтобы оба аргумента были вычислены. Как мы уже заметили, в этом случае следующее дерево строится до конца, а затем уже вычисляется снизу вверх:
Рис. 4. Дерево выражения 1 + (2 + (3 + (4 + ...)))

Кликните, чтобы увидеть увеличенное изображение
При вычислении заполняется стек, и выражение вроде foldr1 (+) [1..10^6]
может вообще не вычислиться — будет выдано сообщение «Exception: stack overflow».
Но с foldl1
дело обстоит иначе:
foldl1 (+) [1..10^6] = foldl (+) ((+) 1 2) [3..10^6] = = foldl (+) ((+) ((+) 1 2) 3) [4..10^6] = = foldl (+) ((+) ((+) ((+) 1 2) 3) 4) [5..10^6] = = ...
Выражение ((+) ((+) ((+) 1 2) 3) ...)
будет тянуться по ходу вычислений не потому, что не может быть вычислено, а потому, что принятый порядок редукции указывает, что редуцируется левый внешний редекс — здесь это применение аргумента [i..10^6]
.
В то же время, в энергичном языке вычисление будет производиться сразу, так что там левая (как мы уже убедились, хвосторекурсивная) свертка точно будет лучше. (Однако в энергичном языке наш пример, переполняющий стек, тоже не будет безобидным — там выражение вроде [1..10^6]
будет сразу вычислено в список из миллиона элементов.)
Как решить проблему в ленивом языке? В Haskell имеется специальная функция:
seq :: a -> b -> b
которая сначала приводит первый аргумент в слабую головную нормальную форму (СГНФ), то есть редуцирует до получения внешней части — значения функции или конструктора, а затем возвращает второй.
Таким образом, если в seq x y
выражение x
будет содержаться в y
в качестве подвыражения, то в результате мы получим y
с приведенным подвыражением x
.
Поэтому можно определить «строгое применение функции»:
f $! x = x `seq` f x
Вернемся к определению:
foldl f x0 (x:xs) = foldl f (f x x) xs
Здесь нас интересует выделенная часть, обозначим ее за red
. Определим foldl'
таким образом, чтобы red
редуцировалось:
foldl' :: (a -> b -> a) -> a -> [b] -> a foldl' f x0 (x:xs) = let red = f x0 x in seq red $ foldl' f red xs foldl1' :: (a -> a -> a) -> [a] -> a foldl1' f (x:xs) = foldl' f x xs
Благодаря такому подходу к вычислению, foldl'
иногда называется «строгой левой сверткой».
В результате foldl' (+) 0 [1..10^6]
не переполняет стек, в отличие от foldl (+) 0 [1..10^6]
— можете проверить в своей системе на достаточно большом списке слагаемых.
Но на самом деле «строгое применение» $!
или «строгая свертка» foldl'
не соотносятся напрямую со строгостью. Как мы уже заметили, приведение в СГНФ просто дает выражение, в котором нет редекса на верхнем уровне, это не то же самое, что и полная редукция!
foldl'
хорошо работает для (+)
и прочих простейших случаев. Если речь идет о более сложных функциях, то по мере прохода списка в памяти точно также будут накапливаться отложенные вычисления. Для бесконечного списка результат мы вообще не получим.
В foldr
же отложенные вычисления накапливаются только в виде применения foldr
к хвосту списка.
Таким образом, хотя foldl
и хвосторекурсивен, это полезно только лишь в энергичных языках, а для ленивых языков вроде Haskell предпочтителен foldr
, но в простых случаях можно имитировать энергичность через foldl'
.
Теперь мы можем пересмотреть наши примеры. В определении length
функцию foldl
можно заменить на foldl'
:
length = foldl' (\ n _ -> n+1) 0
Кроме того, можно перевести amean
на foldl'
. Наивный подход был бы таким:
amean' = uncurry (/) . foldl' (\ (y,n) x -> (x+y, n+1)) (0,0)
Но foldl'
будет только давать СГНФ для (x+y,n+1)
, где внешним уровнем является конструктор пары. То есть (x+y,n+1)
уже находится в СГНФ! Для нужного эффекта seq
требуется применять для x
и n
:
amean' = uncurry (/) . foldl' (\ (y,n) x -> x `seq` n `seq` (x+y, n+1)) (0,0)
В GHC имеется расширение bang patterns, которое позволяет указывать шаблон !p
, такой, что выражение при сопоставлении с ним приводится в СГНФ. Если использовать ghc
с флагом -XBangPatterns
, то можно обойтись записью:
amean' = uncurry (/) . foldl' (\ (!y,!n) x -> (x+y, n+1)) (0,0)
В заключение скажем, что определения foldr, foldl, foldr1, foldl1, scanr, scanl, scanr1, scanl1
можно найти в Prelude. foldl'
и foldl1'
есть в Data.List.
Заключение
Идея свертки может быть применена для многих типов данных помимо списков; например, свертки определены для Data.Map и Data.Set.
Если функция подразумевает свертку, то гораздо лучше выражать ее через предопределенные функции fold
, нежели всякий раз выписывать рекурсивные определения — код со свертками легче читать, писать и анализировать (при наличии соответствующего опыта).
В свертке прослеживается «разделение обязанностей» между функцией высокого порядка и передаваемой функцией, которой производится свертка.
Функция вроде fold
заботится о том, как работать с ресурсом и переходить к следующему элементу структуры данных, поэтому называется перечислителем (enumerator).
Напротив, передаваемая fold
функция ничего не знает о ресурсе и заботится только об элементарной операции над элементами, эту функцию можно назвать итерируемой (iteratee).
Например, функция
Data.Set.fold (+) 0
вычисляет сумму элементов множества. fold
здесь является перечислителем и отвечает за извлечение элементов структуры данных и реализует общую схему свертки, а (+)
является итерируемой функцией и может только переводить пару чисел в их сумму.
0
в этом примере является инициализирующим значением (seed) и также относится к итерируемому.
Таким образом, итерируемое представляет собой пару из функции и инициализирующего значения (в суммах и произведениях последнее играет роль аккумулятора).
Этот подход позволяет строить довольно сложные свертки.
Напоследок приведем (неполный) список языков, в которых также можно найти свертки — непосредственно или через дополнительные модули и библиотеки. Вместо слова fold в названиях функций и соответствующих операций может употребляться reduce или accumulate.
- Clojure: reduce;
- Common Lisp: reduce;
- C++: std::accumulate;
- Erlang: foldl, foldr;
- Maxima: lreduce, rreduce;
- OCaml: List.fold_left, List.fold_right;
- Perl 5: reduce;
- Perl 6: reduction metaoperator;
- Python: reduce, functools.reduce;
- Ruby: enum.inject, enum.reduce;
- Scala: foldLeft, foldRight, reduceLeft, reduceRight;
- Scheme R6RS: fold-left, fold-right;
- Standard ML: foldl, foldr.
Прилагаемые файлы: fph04.lhs.
Ресурсы для скачивания
Похожие темы
- Simon Peyton Jones et al. The Haskell 98 Laguage Report (EN).
- Haskell Hierarchical Libraries (EN).
- Graham Hutton. A tutorial on the universality and expressiveness of fold. J. Functional Programming 9 (4): pp. 355–372, 1999 (EN).
- Rinus Plasmeijer and Marko van Eekelen. Functional Programming and Parallel Graph Rewriting. Addison Wesley, 1993 (EN).
- The Glorious Glasgow Haskell Compilation System User's Guide (EN).