Встроенные map, filter, reduce — Python: Функции

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

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

functools.reduce

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

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

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

Пример работы функции functools.reduce:

from functools import reduce

numbers = [2, 3, 8]

def get_maximum(first_num, second_num):
    return first_num if first_num > second_num else second_num

reduce(get_maximum, numbers, 10)  # 10
reduce(get_maximum, numbers, 4)  # 8

filter

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

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

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

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

Пример работы функции filter:

numbers = [2, 3, 8, 15, 34, 42]

def is_even(num):
    return num % 2 == 0

filter(is_even, numbers)  # <filter object at ...>
list(filter(is_even, numbers))  # [2, 8, 34, 42]

map

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

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

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

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

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 как раз и нацелены на упрощение понимания логики, а мы с помощью грязных функций снова всё запутываем!

Остались вопросы? Задайте их в разделе «Обсуждение»

Вам ответят команда поддержки Хекслета или другие студенты.