Функциональное программирование на Haskell

Часть 4. Свертки списков

Алексей Бешенов
Опубликовано 22.03.2013

Левая и правая свертка: foldl1, foldr1

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

1. Если список состоит из одного элемента x, то минимальный элемент — x.
2. Если список состоит из двух и более элементов, то сравним первый элемент 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;

такой элемент x₀ называется левой единицей операции f. (Эта терминология основана на аналогии с умножением на 1.)

Аналогично, если для всех не пустых xs

foldr f x xs = foldr1 f xs,

то необходимо, чтобы для всех x выполнялось

f x x = x;

то есть x₀ должен быть правой единицей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] это выглядит так:

Запись в виде рекурсивной функции:

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]

Правой свертке 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.

Ресурсы для скачивания

• этот контент в PDF

Похожие темы

• 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).