Свёртки всерьёз: foldr, foldl и foldl’

Свёртка это не “ещё одна функция из стандартной библиотеки”, а способ видеть структуру рекурсии. В этом уроке: foldr против foldl против foldl’, куда встают скобки и почему это вопрос семантики, а не стиля, ранний выход и бесконечные списки, отложенная горка вычислений у foldl и какие функции Prelude оказываются свёртками. Первый M-уровень раздела.

Идея

Положи рядом три функции из урока 03:

sumList []       = 0
sumList (x : xs) = x + sumList xs

productList []       = 1
productList (x : xs) = x * productList xs

concatAll []       = []
concatAll (x : xs) = x ++ concatAll xs

Меняются ровно два места: оператор между головой и рекурсией, и значение для пустого списка. В уроке 04 ты вынес в параметр “что сделать с элементом” и получил map. Сегодня выносим оба места сразу и получаем самую общую функцию обхода:

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr _ z []       = z
foldr f z (x : xs) = f x (foldr f z xs)

Это свёртка, и у неё есть картинка, которая объясняет больше, чем определение. Вспомни из урока 03: список это цепочка cons-ячеек. foldr f z переименовывает конструкторы: каждый (:) становится f, а [] становится z:

1 :  (2 :  (3 :  []))      список как он есть
1 +  (2 +  (3 +  0))       foldr (+) 0
1 *  (2 *  (3 *  1))       foldr (*) 1
1 : (2 : (3 : []))         foldr (:) [] вернул список нетронутым

Никакого обхода “слева направо” в этой картинке нет: есть подстановка одной формы в другую. Скобки при этом наследуются от списка, а список по построению вложен вправо. Отсюда буква r в имени: правая свёртка.

Вторая свёртка выросла из другого паттерна урока 03, помощника go с аккумулятором:

foldl :: (b -> a -> b) -> b -> [a] -> b
foldl _ acc []       = acc
foldl f acc (x : xs) = foldl f (f acc x) xs

Узнаёшь? Это твой reverseAcc, обобщённый до произвольного оператора: иди по списку, таскай с собой накопленное. Скобки у результата вложены влево: ((0 + 1) + 2) + 3. На первый взгляд разница с foldr косметическая. Весь остальной урок разбираем, насколько она не косметическая: от выбора скобок зависит, завершится ли программа вообще.