Изучай Haskell во имя добра! - Миран Липовача

Свёртки могут быть использованы для реализации любой функции, где вы вычисляете что-либо за один обход списка[8]. Если вам нужно обойти список для того, чтобы что-либо вычислить, скорее всего, вам нужна свёртка. Вот почему свёртки, наряду с функциями map и filter, – одни из наиболее часто используемых функций в функциональном программировании.

Функции foldl1 и foldr1

Функции foldl1 и foldr1 работают примерно так же, как и функции foldl и foldr, только нет необходимости явно задавать стартовое значение. Они предполагают, что первый (или последний) элемент списка является стартовым элементом, и затем начинают свёртку со следующим элементом. Принимая это во внимание, функцию maximum можно реализовать следующим образом:

maximum' :: (Ord a) => [a] -> a

maximum' = foldl1 max

Мы реализовали функцию maximum, используя foldl1. Вместо использования начального значения функция foldl1 предполагает, что таковым является первый элемент списка, после чего перемещается к следующему. Поэтому всё, что ей необходимо, – это бинарная функция и сворачиваемый лист! Мы начинаем с «головы» списка и сравниваем каждый элемент с аккумулятором. Если элемент больше аккумулятора, мы сохраняем его в качестве нового значения аккумулятора; в противном случае сохраняем старое. Мы передаём функцию max в качестве параметра foldl1, поскольку она ровно это и делает: берёт два значения и возвращает большее. К моменту завершения свёртки останется самый большой элемент.

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

С другой стороны, функции foldl и foldr хорошо работают с пустыми списками. Подумайте, имеет ли смысл свёртка для пустых списков в вашем контексте. Если функция не имеет смысла для пустого списка, то, возможно, вы захотите использовать функции foldl1 или foldr1 для её реализации.

Примеры свёрток

Для того чтобы показать, насколько мощны свёртки, мы собираемся реализовать с их помощью несколько стандартных библиотечных функций. Во-первых, реализуем свою версию функции reverse:

reverse' :: [a] -> [a]

reverse' = foldl (acc x -> x : acc) []

Здесь мы обращаем список, пользуясь пустым списком как начальным значением аккумулятора, и, обходя затем исходный список слева, добавляем текущий элемент в начало аккумулятора.

Функция acc x -> x : acc – почти то же, что и операция :, за исключением порядка следования параметров. Поэтому функцию reverse' можно переписать и так:

reverse' :: [a] -> [a]

reverse' = foldl (flip (:)) []

Теперь реализуем функцию product:

product' :: (Num a) => [a] -> a

product' = foldl (*) 1

Чтобы вычислить произведение всех элементов списка, следует начать с аккумулятора равного 1. Затем мы выполняем свёртку функцией (*), которая перемножает каждый элемент списка на аккумулятор.

Вот реализация функции filter:

filter' :: (a -> Bool) -> [a] -> [a]

filter' p = foldr (x acc -> if p x then x : acc else acc) []

Здесь начальное значение аккумулятора является пустым списком. Мы сворачиваем список справа налево и проверяем каждый элемент, пользуясь предикатом p. Если p x возвращает истину, элемент x помещается в начало аккумулятора. В противном случае аккумулятор остаётся без изменения.

Напоследок реализуем функцию last:

last' :: [a] -> a

last' = foldl1 ( x -> x)

Для получения последнего элемента списка мы применяем foldr1. Начинаем с «головы» списка, а затем применяем бинарную функцию, которая игнорирует аккумулятор и устанавливает текущий элемент списка как новое значение аккумулятора. Как только мы достигаем конца списка, аккумулятор — то есть последний элемент – возвращается в качестве результата свёртки.

Иной взгляд на свёртки

Есть ещё один способ представить работу правой и левой свёртки. Скажем, мы выполняем правую свёртку с бинарной функцией f и стартовым значением z. Если мы применяем правую свёртку к списку [3,4,5,6], то на самом деле вычисляем вот что:

f 3 (f 4 (f 5 (f 6 z)))

Функция f вызывается с последним элементом в списке и аккумулятором; получившееся значение передаётся в качестве аккумулятора при вызове функции с предыдущим значением, и т. д. Если мы примем функцию f за операцию сложения и начальное значение за нуль, наш пример преобразуется так:

3 + (4 + (5 + (6 + 0)))

Или, если записать оператор + как префиксную функцию, получится:

(+) 3 ((+) 4 ((+) 5 ((+) 6 0)))

Аналогичным образом левая свёртка с бинарной функцией g и аккумулятором z является эквивалентом выражения

g (g (g (g z 3) 4) 5) 6

Если заменить бинарную функцию на flip (:) и использовать [] как аккумулятор (выполняем обращение списка), подобная запись эквивалентна следующей:

flip (:) (flip (:) (flip (:) (flip (:) [] 3) 4) 5) 6

Если вычислить это выражение, мы получим [6,5,4,3].

Свёртка бесконечных списков

Взгляд на свёртки как на последовательное применение функции к элементам списка помогает понять, почему правая свёртка иногда отлично работает с бесконечными списками. Давайте реализуем функцию and с помощью foldr, а потом выпишем последовательность применений, как мы это делали в предыдущих примерах. Тогда мы увидим, как ленивость языка Haskell позволяет правой свёртке обрабатывать бесконечные списки.

Функция and принимает список значений типа Bool и возвращает False, если хотя бы один из элементов равен False; в противном случае она возвращает True. Мы будем обходить список справа, используя True как начальное значение. В качестве бинарной функции будем использовать операцию &&, потому что должны вернуть True только в том случае, когда все элементы списка истинны. Функция && возвращает False, если хотя бы один из параметров равен False, поэтому если мы встретим в списке False, то аккумулятор будет установлен в значение False и окончательный результат также будет False, даже если среди оставшихся элементов списка обнаружатся истинные значения.

and' :: [Bool] -> Bool

and' xs = foldr (&&) True xs

Зная, как работает foldr, мы видим, что выражение and' [True,False,True] будет вычисляться следующим образом:

True && (False && (True && True))

Последнее True здесь – это начальное значение аккумулятора, тогда как первые три логических значения взяты из списка [True,False,True]. Если мы попробуем вычислить результат этого выражения, получится False.

А что если попробовать то же самое с бесконечным списком, скажем, repeat False? Если мы выпишем соответствующие применения, то получится вот что:

False && (False && (False && (False …

Ленивость Haskell позволит вычислить только то, что действительно необходимо. Функция && устроена таким образом, что если её первый параметр False, то второй просто игнорируется, поскольку и так ясно, что результат должен быть False.

Функция foldr будет работать с бесконечными списками, если бинарная функция, которую мы ей передаём, не требует обязательного вычисления второго параметра, если значения первого ей достаточно для вычисления результата. Такова функция && – ей неважно, каков второй параметр, при условии, что первый — False.

Сканирование

Функции scanl и scanr похожи на foldl и foldr, только они сохраняют все промежуточные значения аккумулятора в список. Также существуют функции scanl1 и scanr1, которые являются аналогами foldl1 и foldr1.

ghci> scanl (+) 0 [3,5,2,1]

[0,3,8,10,11]

ghci> scanr (+) 0 [3,5,2,1]

[11,8,3,1,0]

ghci> scanl1 (acc x –> if x > acc then x else acc) [3,4,5,3,7,9,2,1]

[3,4,5,5,7,9,9,9]

ghci> scanl (flip (:)) [] [3,2,1]

[[],[3],[2,3],[1,2,3]]

При использовании функции scanl финальный результат окажется в последнем элементе итогового списка, тогда как функция scanr поместит результат в первый элемент.

Функции сканирования используются для того, чтобы увидеть, как работают функции, которые можно реализовать как свёртки. Давайте ответим на вопрос: как много корней натуральных чисел нам потребуется, чтобы их сумма превысила 1000? Чтобы получить сумму квадратов натуральных чисел, воспользуемся map sqrt [1..]. Теперь, чтобы получить сумму, прибегнем к помощи свёртки, но поскольку нам интересно знать, как увеличивается сумма, будем вызывать функцию scanl1. После вызова scanl1 посмотрим, сколько элементов не превышают 1000. Первый элемент в результате работы функции scanl1 должен быть равен единице. Второй будет равен 1 плюс квадратный корень двух. Третий элемент – это корень трёх плюс второй элемент. Если у нас x сумм меньших 1000, то нам потребовалось (x+1) элементов, чтобы превзойти 1000.