Знакомство с map, filter, reduce

Классические ФВП

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

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

map

При работе со списками часто встаёт задача применить некоторое преобразование (одно и то же) к каждому элементу. Конечно, мы всегда можем написать цикл. Однако этот цикл будет выглядеть одинаково практически во всех случаях:

def f(x):
    …

new_list = []
for item in old_list:
    new_item = f(item)
    new_list.append(new_item)

# …
# используем new_list

В таких случаях меняется только применяемая функция f. Так почему бы нам не обобщить этот код так, чтобы функция была параметром? Так и сделаем:

>>> def map(function, items):
...     result = []
...     for item in items:
...         result.append(function(item))
...     return result
>>> map(str, range(5))
["0", "1", "2", "3", "4"]

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

filter

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

>>> def filter(predicate, items):
...     result = []
...     for item in items:
...         if predicate(item):
...             result.append(item)
...     return result
...
>>> def is_odd(x):
...     return x % 2
...
>>> filter(is_odd, range(6))
[1, 3, 5]

Наша функция filter применяет предикат к каждому элементу и добавляет в выходной список только те элементы, для которых предикат вернул True.

У функции filter имя более "говорящее" и менее академичное, но такое же популярное — многие языки имеют аналогичную функцию с тем же именем.

reduce

И map, и filter работали с отдельными элементами независимо. Но ведь встречаются и циклы, которые агрегируют результат — формируют результирующее значение (одно), комбинируя элементы между собой с использованием аргумента-аккумулятора.

Типичными примером агрегации может быть сумма всех элементов списка. Или, скажем, произведение. Представим, что нам нужно сложить элементы списка [1, 2, 3, 4, 5]. С точки зрения математики сумма

1 + 2 + 3 + 4 + 5

может быть выражена как

(((((0 + 1) + 2) + 3) + 4) + 5).

Ноль здесь — тот самый аккумулятор (его начальное состояние). Он не добавляет к сумме ничего, но может служить отправной точкой. А ещё — будет результатом, если входной список пуст.

С помощью цикла мы бы суммировали так:

acc = 0
for item in items:
    acc = acc + item

А умножали бы так:

acc = 1
for item in items:
    acc = acc * item

Замечаете тенденцию? Циклы отличаются только начальным значением аккумулятора (0 и 1) и операцией, которая комбинирует элемент и аккумулятор (+ и *). Обобщаем!

>>> def reduce(operation, initial_value, items):
...     acc = initial_value
...     for item in items:
...         acc = operation(acc, item)
...     return acc
...
>>> from operator import add, mul
>>> reduce(add, 0, [1, 2, 3, 4, 5])
15
>>> reduce(mul, 1, [1, 2, 3, 4, 5])
120

В примере я использовал функции add и mul из модуля operator. Так вот, это аналоги + и * в виде функций, которые можно использовать в связке с ФВП. Возьмите этот модуль на заметку и поэкспериментируйте с его содержимым!

Функции, называемой в Python reduce не так повезло с именем, как двум предыдущим. Уж как только эту функцию не называют — и inject, и reduce, и aggregate.

И лишь в математике всё однозначно: такая функция называется левая свёртка (left fold). И имя "свёртка" вполне себе говорящее — применяя эту функцию, мы сворачиваем список в одно значение!

А левая наша свёртка потому, что "схлопывать" элементы с аккумулятором мы начинаем слева. Существует ещё и правая свёртка (right fold), но в виде встроенной функции в Python она не представлена. Правая свёртка для суммы выглядит так:

(1 + (2 + (3 + (4 + (5 + 0)))))

В большинстве случаев обе свёртки дают одинаковый результат, если применяемая операция ассоциативна (т.е. позволяет расставлять скобки произвольно — как в случае наших сумм). Но через цикл итерации элементов проще реализовать именно левую, поэтому она и используется чаще.

map/filter/reduce против цикла for

Мы с вами реализовали целые три функции, каждая из которых, имеет меньшую мощность, чем цикл for. Более того, цикл for позволяет гибко управлять процессом итерации с помощью команд break и continue. Зачем же тогда нужны эти отдельные маломощные версии, когда есть одна универсальная?

А нужны эти функции затем, что каждая функция делает ровно одну работу, что значительно упрощает рассуждение о коде, его чтение и написание. С первого взгляда на имя функции мы можем понять, что filter — фильтрует, а map — преобразует элементы, но не наоборот! Более того, по построению filter не меняет элементы, а только лишь отбрасывает их часть. А map меняет значение элементов, но не меняет их количество и позиции. Это знание того, что код сделать не может, дорогого стоит! Имей же мы на руках цикл for, нам бы пришлось (и приходится!) "выполнить код в уме" (как ещё говорят, "поработать интерпретатором"), ведь цикл for может делать что угодно — и менять элементы, и отбрасывать их и агрегировать результат, и даже делать всё это одновременно!

И пусть все случаи применения цикла заменить на функции не получится. Но в тех простых случаях, когда можно достигнуть нужного результата с применением менее мощного и вместе с тем более простого в понимании инструмента — стоит, как минимум, подумать об этой альтернативе!