Встроенные map, filter, reduce

Встроенные map, filter, reduce

Все три рассмотренные нами на прошлом уроке ФВП присутствуют в Python "из коробки". При этом map и filter можно использовать сразу, а reduce нужно импортировать из модуля functools.

Сейчас же мы рассмотрим отличия каждой конкретной функции от тех простых вариантов, которые мы реализовали ранее. А начнём мы со свёртки.

functools.reduce

Взглянув на объявление функции, мы увидим

reduce(function, sequence[, initial]) -> value

Здесь стоит обратить внимание на то, что начальное значение аккумулятора — опциональный аргумент ([, initial]). Если его не указать, то reduce будет использовать в качестве начального значения первый элемент последовательности sequence. Но в этом случае нужно помнить, что если последовательность пустая, то вызов reduce завершится с ошибкой!

filter

Теперь взглянем на filter:

filter(function or None, iterable) -> filter object

С function всё понятно, но что делает None в роли предиката? Это замена для условия "всё, что угодно, лишь бы было истинно!". Тот же результат даст фильтрация с bool в качестве предиката.

Обратите внимание на возвращаемое значение filter object. Это не список, но итератор. Т.е. встроенный filter — ленивый. Возвращает элементы по одному, если находит подходящие, конечно.

map

Встроенный map отличается от нашей наивной реализации:

map(func, *iterables) --> map object

Здесь map object — тоже итератор. Это понятно. А вот жадный аргумент *iterables принимает несколько итерируемых объектов вместо одного! Если map передать более одного источника элементов, то функция func будет вызвана сначала для всех первых элементов, потом для вторых, и так далее, пока не закончатся элементы хотя бы в одном источнике. Это чем-то похоже на функцию zip, которую я упоминал в курсе по спискам, только zip всегда возвращает кортежи, а map применяет произвольную функцию (от соответствующего числу источников количества аргументов). Вот пример применения функции map к паре источников:

>>> from operator import mul
>>> list(map(mul, "abc", [3, 5, 7]))
['aaa', 'bbbbb', 'ccccccc']

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

map/filter/reduce и побочные эффекты

При использовании рассматриваемых "заменителей цикла for" следует руководствоваться одним важным правилом: применяемые с их помощью функции должны по возможности быть чистыми (pure functions).

Функция является чистой, если не производит побочные эффекты (side effects) и возвращает результат, зависящий только от аргументов. Подробно про побочные эффекты мы поговорим в последующих курсах, пока же я дам краткое определение: побочные эффекты — это наблюдаемые последствия вызова функции, не относящиеся к возвращаемому результату.

Если функция печатает что-то в консоль, пишет в файл, посылает по сети — это функция с побочными эффектами. Если вызов функции зависит от внешнего мира (глобальные изменяемые объекты, например), а не только от аргументов — функция, опять же, не чистая!

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

А ещё побочные эффекты нарушают законы, которые характерны для математических версий map, filter и reduce.

Грязные функции и reduce

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

Грязные функции и map

Если мы возьмём грязную функцию, то для map нарушится закон

map(f, map(g, l)) == map(f*g, l)

Здесь в виде f*g я записал (это псевдокод!) композицию функций, т.е. получение функции, делающей x -> f(g(x)). Встроенного оператора для композиции в Python нет, но функция композиции пишется элементарно.

Данный закон очень важен, ведь он позволяет произвести оптимизацию: превратить два прохода по последовательности в один. При использовании же функции с эффектами программа до оптимизации и после неё будет работать по-разному: до оптимизации будут выполнены сначала все эффекты функции g, потом — эффекты функции f, а после оптимизации эффекты g и f будут происходить парами!

Грязные функции и filter

Для filter возможна такая оптимизация:

filter(f, filter(g, l)) == filter(g&f, l)

Здесь g&f, это условное обозначение функции, которая делает x -> g(x) and f(x). Опять же, такого оператора в Python нет, но реализовать подобную функцию очень просто.

В случае filter после оптимизации эффекты тоже "перемешаются", как было описано выше для функции map.

Простое правило

Если вы видите, что в ФВП просится не чистая функция — перепишите на цикл. Мы помним, что цикл у нас мощный и в его теле может происходить что угодно — вот пусть и эффекты происходят в цикле, а не в чистых map/filter/reduce.

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