Хотя Python не является языком функционального программирования в чистом виде, с его помощью можно многое сделать и в этой парадигме. И большую часть этого «многого» можно сделать при помощи всего одной функции — reduce.
Знакомство с reduce в Python
Хотите скачать книги по Python в 2 клика? Тогда вам в наш телеграм канал PythonBooks
Для начала давайте разберемся, что собой представляет reduce в Python.
Функция reduce(function, iterable[, initializer]) модуля functools кумулятивно применяет функцию function к элементам итерируемой последовательности, сводя ее к единственному значению. Если присутствует необязательный аргумент initializer, он помещается перед элементами iterable в вычислении. initializer — это базовое значение, с которого требуется начать отсчет. Он также служит значением по умолчанию, когда итерируемый объект является пустым.
Проще говоря, reduce — это функция, которая принимает функцию и итерируемый объект в качестве параметров и применяет полученную функцию к парам значений из итерируемого объекта, пока не останется только одно значение.
Самый простой способ понять, что делает reduce, — рассмотреть пример. Вот как можно реализовать вычисление факториала с помощью этой функции:
from functools import reduce import operator # Signature: reduce(function, iterable[, initializer]) # Factorial reduce(lambda x, y: y*x, range(1, 6), 1) reduce(operator.mul, range(1, 6)) (((((1 * 1) * 2) * 3) * 4) * 5) # 120
То, что мы знаем как reduce в Python, в функциональных языках программирования, таких как Haskell, известно как fold — «свёртка». Вот эквивалентная реализация вычисления факториала на языке Haskell с использованием foldl («свертка слева»):
factorial n = foldl (*) 1 [1..n] main = do let f = factorial 5 print(f) # 120
По виду это не сильно отличается от версии на Python.
Различные версии свертки (слева, справа, с инициализатором или без него) являются очень мощными функциями общего назначения. Если вы когда-нибудь пробовали писать код на Haskell, то знаете, что fold можно использовать для реализации чего угодно. Поэтому давайте посмотрим, сработает ли это с reduce в Python.
Свёртка
Как уже отмечалось, сокращение/сворачивание — это очень мощный инструмент. Все, что можно вычислить из последовательности элементов, может быть выражено (пусть и неуклюже) как свертка. В качестве доказательства можно привести другие встроенные функции Python, реализованные с помощью reduce:
from functools import reduce import operator _sum = lambda d: reduce(operator.add, d, 0) # sum() f = str _map = lambda d: reduce(lambda x, y: x + [f(y)], d, []) # map() is_prime = lambda n: all(n%j for j in range(2, int(n**0.5)+1)) and n > 1 _filter = lambda d: reduce(lambda x, y: x + [y] if is_prime(y) else x, d, []) # filter(is_prime, range(10)) _reversed = lambda d: reduce(lambda x, y: [y] + x, d, []) # reversed(data) _min = lambda d: reduce(lambda x, y: x if x < y else y, d) # min(data) _max = lambda d: reduce(lambda x, y: x if x > y else y, d) # max(data)
Как видите, с помощью reduce можно реализовать и другие базовые концепции функционального программирования, такие как map и filter. Таким образом, хотя это и не практично, но написать правильный код функционального программирования с помощью reduce определенно возможно.
Как упоминалось ранее, reduce также известна как foldl, потому что свертка происходит слева. А как насчет foldr — свертки справа? В Python нет встроенной версии reduce, которая «сворачивает» справа, но с помощью reduce можно реализовать что угодно, верно?
data = [7, 4, 3, 6, 2] foldr = lambda f, d: reduce(lambda x, y: f(y, x), d[::-1]) foldr(data) == (7 - (4 - (3 - (6 - 2)))) # True reduce(operator.sub, [7, 4, 3, 6, 2]) == ((((7 - 4) - 3) - 6) - 2) # True
reduce хорошо работает для левоассоциативных операций типа / (отношение) или ассоциативных операций в целом, типа * или +, например, (((((1 * 1) * 2) * 3) * 4) * 5). Если же вы хотите выполнять операции с другой стороны, то вам понадобится foldr (выше приведена его быстрая реализация).
Помимо свертки
Хотя свертка — это интересное упражнение, существует множество более практичных примеров использования reduce в Python.
Композиция функций в Python при помощи reduce
Композиция функций — это фундаментальная концепция функционального программирования, и она очень полезна для объединения нескольких функций в цепочку. Вот как это выглядит:
import functools
def compose(*funcs):
return lambda x: functools.reduce(lambda acc, f: f(acc), funcs, x)
# f3(f2(f1(value)))
func = compose(f1, f2, f3)
func(value)
В приведенном выше однострочном предложении для объединения в цепочку любого количества функций нужны только reduce и lambda.
Обратите внимание, что порядок здесь имеет значение. Мы передаем функции для объединения как (f1, f2, f3), но они вычисляются как f3(f2(f1(...))). Если бы мы хотели, чтобы они вычислялись как f1(f2(f3(...))), нам пришлось бы изменить список функций, используя funcs[::-1].
Получение вложенных значений
Отойдя от чистого функционального программирования, предположим, что у нас есть большой JSON (словарь), возвращаемый каким-то API. Мы ищем какой-нибудь глубоко вложенный ключ, используя следующий код:
data = {
"deeply": {
"nested": {
"python": {
"dict": "value"
}
}
}
}
print(reduce(lambda d, key: d[key], ["deeply", "nested", "python", "dict"], data))
# value
Здесь мы используем словарный геттер, чтобы пройти по уровням словаря. Если вам не нравятся лямбды, то это также можно сделать с помощью dict.get.
Аналогичным образом мы можем добраться до атрибутов класса:
class SomeClass:
pass
c = SomeClass()
c.one = SomeClass()
c.one.two = SomeClass()
c.one.two.three = "data"
attrs = ["one", "two", "three"]
reduce(getattr, attrs, c)
# prints: "data"
Хеширование
Функция хеширования является хорошим примером сокращения. Она преобразует массив входных данных произвольной длины в выходную битовую строку установленной длины, постоянно применяя одну и ту же функцию к фрагментам значения, пока оно не сократится до постоянной длины. Вот код:
import operator
from random import choice
from string import ascii_uppercase
# 100 random uppercase characters
random_string = ''.join(choice(ascii_uppercase) for i in range(100))
def _hash(data):
n = 5
# Break into chunks of 5 chars and compute their hash
chunks = [hash(data[i:i+n]) for i in range(0, len(data), n)]
# Reduce hash components into single value
return reduce(operator.xor, chunks, 0)
print(_hash(random_string))
# 5469166689487367977
В этом примере мы сначала разбиваем текст, который хотим хэшировать, на несколько фрагментов. Затем мы вычисляем хэш каждого фрагмента и сохраняем его в списке. Чтобы создать окончательный хэш, мы комбинируем reduce с operator.xor для итеративного объединения хэшей фрагментов, пока не останется только одно значение.
Допустим, у вас есть словарь с числовыми значениями, и вы хотите получить их сумму. Для этого можно использовать цикл for, но reduce позволяет получить лаконичное решение:
data = {"key": 4, "other-key": 6, "another": 7}
print(reduce(lambda x, key: x + data[key], data, 0))
# 17
Естественно, сокращения весьма полезны для многих математических операций, таких как вычисление nCr или комбинаций:
import operator as op
from functools import reduce
# https://en.wikipedia.org/wiki/Combination
def comb(n, k):
k = min(k, n-k)
numerator = reduce(op.mul, range(n, n-k, -1), 1)
denominator = reduce(op.mul, range(1, k+1), 1)
return numerator // denominator
Я намеренно назвал функцию comb, потому что в модуле math есть одноименная функция, которая делает то же самое. Как мы все знаем, Python поставляется с батарейками в комплекте, поэтому всегда имеет смысл заглянуть в стандартную библиотеку, прежде чем реализовывать собственное решение.
Вообще, в модуле math есть несколько функций, которые могут быть реализованы с помощью reduce. Их разбор может стать хорошим упражнением в использовании reduce и понимании того, как работает эта функция. Несколько кандидатов — factorial, fsum, gcd, lcm или prod.
Использование reduce с pandas
Раз уж речь зашла о математике, мы также можем использовать reduce в сочетании с pandas. Например, чтобы вычислить объединение датафреймов, можно сделать следующее:
import pandas as pd
dfs = [pd.DataFrame([(1, 2, 3), (4, 5, 6), (7, 8, 9)]),
pd.DataFrame([(3, 7, 9), (1, 3, 5), (0, 1, 2)]),
pd.DataFrame([(9, 7, 1), (6, 2, 5), (1, 2, 4)])]
df = reduce(pd.DataFrame.add, dfs)
print(df)
# 0 1 2
# 0 13 16 13
# 1 11 10 16
# 2 8 11 15
Обычно мы используем x.DataFrame.add(y), поскольку это более естественно для Python, но здесь мы предоставляем pd.DataFrame.add в качестве функции свертки. Хитрость здесь заключается в том, что первым аргументом DataFrame.add является self, поэтому вместо lambda x, y: x.DataFrame.add(y) можно написать pd.DataFrame.add(x, y).
Продолжая предыдущий пример, мы можем еще раз использовать reduce в pandas, на этот раз для выполнения сокращения по столбцам:
dfs = ... df = reduce(pd.DataFrame.add, dfs) sums = df.apply(lambda x: reduce(operator.add, x), axis=0) print(sums.to_string()) # 0 42 # 1 37 # 2 34 sums = [reduce(operator.add, df[row]) for row in df] print(sums) # [32, 37, 44]
От редакции Pythonist: если вы не знакомы с pandas, рекомендуем почитать «Полное руководство по Pandas для начинающих».
Суммирование элементов
Аналогично тому, что мы делали ранее со словарями, мы также можем использовать reduce для суммирования элементов разных итерируемых объектов. Допустим, мы хотим просуммировать третьи элементы кортежей в списке:
data = [("John", "Smith", 5300.0), ("Ben", "Greene", 1532.30), ("Amy", "Holmes", 3550.75)]
# With list comprehension
print(reduce(lambda a, b: a+b, [sub[2] for sub in data]))
# Simpler
print(reduce(lambda a, b: a+b[2], data, 0))
# 10383.05
И раз уж мы рассматриваем примеры сокращения разных итерируемых объектов Python, давайте также возьмем пример со множеством:
data = [
[1, 6, 8, 2, 3],
[2, 9, 4, 1, 6],
[1, 7, 5, 6, 2]
]
print(reduce(set.intersection, map(set, data)))
# {1, 2, 6}
Здесь при помощи оператора set.intersection мы можем вычислить пересечение любого количества итерируемых объектов.
Проверка типов
И наконец, если вы являетесь поклонником проверки типов или статической типизации, или хотите четко видеть, что входит в выражение reduce, а что выходит, то вы можете попробовать добавить подсказки типов к вашим сокращениям. Это можно сделать даже для встроенных лямбда-выражений:
from collections.abc import Callable
from functools import reduce
from typing import cast, TypeAlias, TypeVar
FloatFunc: TypeAlias = Callable[[float, float], float]
ReverseFunc: TypeAlias = Callable[[list, str], list]
T = TypeVar("T")
MapFunc: TypeAlias = Callable[[list, Callable[T, T]], list]
_sum = lambda d: reduce(cast(FloatFunc, lambda x, y: x+y), d, 0.0)
_min = lambda d: reduce(cast(FloatFunc, lambda x, y: x if x < y else y), d)
_max = lambda d: reduce(cast(FloatFunc, lambda x, y: x if x > y else y), d)
_reversed = lambda d: reduce(cast(ReverseFunc, lambda x, y: [y] + x), d, [])
_map = lambda d: reduce(cast(MapFunc, lambda x, y: x + [f(y)]), d, [])
Здесь используется функция cast. Она подает инструменту проверки типов сигнал о том, что возвращаемое значение будет определенного типа. Однако имейте в виду, что это ни на что не влияет при выполнении программы, это просто информация для таких инструментов проверки типов, как mypy.
Выражения с reduce не очень просты для понимания, поэтому знание типов входных и выходных данных может оказаться полезным. Но хотя это и добавляет ясности, это также делает выражения более многословными, что не способствует удобочитаемости. В общем, решайте сами, стоит ли включать подсказки типов в подобные однострочные выражения.
От редакции Pythonist: возможно, вас заинтересует статья «Аннотации типов Python».
Заключение
Fold и, следовательно, reduce — это абстракция общего назначения, которая полезна не только для чистого функционального программирования. Эти сокращения позволяют избавиться от шаблонов и решить задачи, которые могут быть естественно выражены рекурсивно, а таких задач очень много.
При этом, хотя Python предоставляет некоторые инструменты для функционального программирования (itertools, functools, лямбды, декораторы), он не является функциональным языком программирования, поэтому не пытайтесь превратить его в таковой. Некоторые примеры в этой статье приведены для наглядности, их использование может быть не самой лучшей идеей.
Кроме того, даже в ситуациях, когда свертки или другие концепции функционального программирования могут стать хорошим решением, учитывайте, что будущие читатели вашего кода могут быть не знакомы с ними и им будет трудно понять, что происходит в коде.
Перевод статьи «Reduce — The Power of a Single Python Function».
