Свертки: разбор полетов

В чем идея функций foldl и foldr? Сами функции мы написали, а теперь давайте запросим у интерпретатора их тип:

foldl :: (a -> b -> a) -> a -> [b] -> a

foldr :: (b -> a -> a) -> a -> [b] -> a

Обе функции принимают какую-то бинарную операцию, принимают нулевой элемент, он же есть начальное значение аккумулятора типа a, и принимают список значений какого-то типа b. Теперь посмотрим на тип операции: эта операция принимает аккумулятор a, очередной элемент b, и возвратить она должна новое значение аккумулятора a. Отличие сигнатуры типов только в том, в каком порядке принимает операция свои аргументы: (a -> b -> a) для foldl и (b -> a -> a) для foldr.

В чем идея этих функций? Робот map шел вдоль-по списку-конвейеру, преобразовывал каждый элемент и складывал обратно. Робот filter шел по списку-конвейеру, проверял каждый элемент и какие-то выкидывал. А какая аналогия здесь?

Такая аналогия на самом деле есть. Робот foldl тоже идет по списку, как и робот map, но в отличие от последнего, робот foldl имеет аккумулятор, то есть память. Он идет вдоль конвейера, держа в руках нечто полусобранное – текущее состояние аккумулятора. Робот берет каждый элемент, и применяет какую-то операцию к этому элементу и своему полусобранному предмету, получая в результате новый полусобранный предмет, с которым в руках идет дальше. В итоге, к концу конвейера в его руках будет нечто, потенциально собранное из всех предметов на конвейере.

Признаюсь, foldl – моя любимая функция. Чудится мне в ней аллегория на все возможные вычисления вообще. Ведь аккумулятор у foldl совсем ничем не ограничен – он может быть вообще произвольным. В аккумуляторе у foldl может находиться целиком все состояние памяти компьютера, и тогда каждый шаг функции foldl – это выполнение какой-то команды, взятой с конвейера, которая как-то изменяет состояние аккумулятора, то есть ей памяти, и передает это состояние на следующий шаг вычислений. Впечатляет, не так ли?

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

cnt xs =

foldl (\ (sm,bg) c ->

if isLower c then (sm+1,bg)

else (sm,bg+1))

(0,0)

xs

Причем формальный параметр xs можно и опустить, а при большом желании и без лямбды обойтись:

cnt = foldl docnt (0,0) where

docnt (sm,bg) c | isLower c = (sm+1,bg)

| otherwise = (sm,bg+1)

В заключение о свертках: попробуйте сами разобраться, могут ли функции foldr и foldl работать с бесконечными списками? Очень полезное мероприятие. Думаю, не ошибусь, если предскажу, что в процессе поиска правильного ответа на этот вопрос, вы несколько раз поменяете свое мнение :).

Выявление общей функциональности

Давайте оглянемся на найденные функции map, filter, foldl и foldr и подумаем, что мы сделали.

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

Идея каждой функции была достаточно общей, чтобы охватить достаточно большое количество конкретных функций, встречающихся в жизни. Достаточно общей – но не более того. Например, функция map у нас преобразовывала каждый элемент списка с помощью общей функции, которой было доступно только значение элемента, – но не его порядковый номер, или значения соседних элементов. Вполне можно было бы написать и более общую функцию, которая бы позволяла обрабатывать элемент, учитывая его порядковый номер:

map :: (Integer -> a -> b) -> [a] -> [b]

map f xs = mapN f 1 xs

mapN f _ [] = []

mapN f n (x:xs) = f n x : mapN f (n+1) xs

Здесь каждый элемент преобразовывается с помощью функции f, которая принимает не только очередной элемент x, но и его порядковый номер n.

В таком случае, некоторые функции можно было бы записать проще именно с такой версией функции map. Помните, была у нас задача – занулить те числа в списке, которые совпадают со своим порядковым номером? Элементарно, Ватсон!

zeroSome xs = mapN (\n x -> if x==n then 0 else x) xs

Но подождите, ведь того же самого мы добились и с помощью обычной функции map, приклеив дополнительно к каждому элементу его номер?

zeroSome xs = map f (zip [1..] xs) where

f (n,x) = if x==n then 0 else x

Кстати, зная теперь, что такое композиция, мы перепишем последнюю функцию еще короче:

zeroSome = map f . zip [1..] where

f (n,x) = if x==n then 0 else x

Что получается? Да, модифицированная версия функции map может все то же самое, что и классическая версия функции map. Но часто ли требуется такое преобразование? Лучше так: достаточно ли часто требуется такая функциональность, чтобы устать от повторного использования zip?