map, filter, reduce, functools, itertools — functional tools

Python — не Haskell, но functional toolkit богат: map / filter — lazy iterators; functools.reduce — fold-аналог; functools.partial — currying; functools.lru_cache — single-line memoization; itertools — целый zoo lazy combinators (chain, islice, groupby, takewhile, и десятки других).

Этот урок покрывает требование PYTH-10 целиком. Все эти инструменты — про lazy evaluation (как gen-expr из урока 3) и composition (комбинирование маленьких функций в pipeline).

map / filter — lazy iterators

map(f, iter) возвращает итератор, yielding f(x) для каждого x из iter. Это не list — это lazy:

nums = [1, 2, 3, 4, 5]
doubled = map(lambda x: x * 2, nums)
print(type(doubled))   # <class 'map'> — iterator, не list
print(list(doubled))   # [2, 4, 6, 8, 10] — list() forces materialization

filter(pred, iter) аналогично — yields x где pred(x) truthy:

evens = filter(lambda x: x % 2 == 0, nums)
print(list(evens))     # [2, 4]

Часто эквивалентно gen-expression — выбор по читаемости:

# С map / filter:
doubled = map(lambda x: x * 2, nums)
evens = filter(lambda x: x % 2 == 0, nums)

# С gen-expr (обычно более Pythonic):
doubled = (x * 2 for x in nums)
evens = (x for x in nums if x % 2 == 0)

functools.reduce — fold

reduce(f, iter, initial=...) агрегирует iterator left-to-right с binary function. Эквивалент foldl в Haskell:

from functools import reduce
from operator import add, mul

reduce(add, [1, 2, 3, 4])         # 1+2+3+4 = 10
reduce(mul, [1, 2, 3, 4])         # 1*2*3*4 = 24
reduce(add, [1, 2, 3, 4], 100)    # 100+1+2+3+4 = 110 (initial = 100)

# Конкатенация строк через reduce:
reduce(lambda a, b: a + b, ['A', 'B', 'C'])    # 'ABC'

Семантика: для reduce(f, [x1, x2, x3], init) результат = f(f(f(init, x1), x2), x3). Без init первый элемент iterator используется как стартовое значение (требует не-пустой iter).

Когда использовать reduce: для свёрток, не покрытых sum / max / min / any / all. Если стандартный агрегатор подходит — используйте его (быстрее, читаемее).

functools.partial — currying

Создаёт новый callable с pre-filled аргументами:

from functools import partial
from operator import mul

double = partial(mul, 2)    # bind первый arg = 2
triple = partial(mul, 3)
print(double(5))            # 10
print(triple(5))            # 15

# Kwargs тоже:
log_info = partial(print, '[INFO]')
log_info('msg1', 'msg2')    # [INFO] msg1 msg2

# Адаптация sort key:
data = [(1, 'a'), (3, 'c'), (2, 'b')]
sorted_by_str = sorted(data, key=partial(lambda d, idx: d[idx], idx=1))

Внутри partial — простая структура: хранит func, args, kwargs; при вызове конкатенирует pre-filled с переданными. См. Modules/_functoolsmodule.c функция partial_call.

Use case: adapter pattern — когда чужая функция ожидает callable с определённой signature, а у вас функция с лишними параметрами; partial фиксирует «лишние» и возвращает signature-совместимый callable.

functools.lru_cache — memoization decorator

Декоратор кэширующий результаты функции по аргументам. LRU eviction (Least Recently Used) при достижении maxsize:

from functools import lru_cache

@lru_cache(maxsize=128)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(50))               # 12586269025 — мгновенно благодаря cache
print(fib.cache_info())      # CacheInfo(hits=48, misses=51, maxsize=128, currsize=51)

Без lru_cache fib(50) экспоненциально медленный (2⁵⁰ recursive вызовов). С cache — линейный по n (каждое значение вычислено один раз).

Под капотом: cache implementation использует dict (см. M02 урок 03 — open addressing с perturbation). Каждый вызов:

1. Вычисляет hash от args (требует hashable!).
2. dict.get lookup — O(1) avg.
3. На hit возвращает cached value; на miss — вызывает функцию + сохраняет.
4. На переполнении (currsize > maxsize) — evict LRU (через linked list поверх dict).

См. Modules/_functoolsmodule.c — lru_cache_wrapper — C-accelerated. Pure-Python fallback в Lib/functools.py.

@lru_cache(maxsize=None) — unbounded cache (никогда не evict). @cache (Python 3.9+) — alias для lru_cache(maxsize=None), более лаконично:

from functools import cache

@cache
def expensive(x):
    ...

itertools — комбинаторика iterators

Целая библиотека lazy combinators. Highlights:

Пример — fibonacci через generator + islice:

from itertools import islice, count, chain

def fibs():
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a + b

# Первые 10 чисел:
print(list(islice(fibs(), 10)))   # [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

groupby — особенный: группирует consecutive одинаковые элементы (требует pre-sorted input!):

from itertools import groupby

data = sorted(['apple', 'banana', 'cherry', 'avocado'], key=len)
# отсортировано по длине: ['apple', 'cherry', 'banana', 'avocado']

for length, items in groupby(data, key=len):
    print(length, list(items))
# 5 ['apple']
# 6 ['cherry', 'banana']
# 7 ['avocado']

Cite: Modules/itertoolsmodule.c — все iterators реализованы на C, использующих iterator protocol (tp_iter / tp_iternext). Это link к Phase 66 M05 (iterators / generators).

См. https://docs.python.org/3/library/itertools.html для полного списка.

operator module — callable operators

Модуль operator предоставляет callable versions всех арифметических / сравнительных операторов:

from operator import add, mul, lt, eq, itemgetter, attrgetter

reduce(add, [1, 2, 3, 4])         # эквивалентно reduce(lambda a,b: a+b, [1,2,3,4])

# Сортировка по полю:
data = [{'age': 30, 'name': 'A'}, {'age': 25, 'name': 'B'}]
sorted(data, key=itemgetter('age'))    # [B, A]

class Person:
    def __init__(self, name, age):
        self.name = name
        self.age = age

people = [Person('Alice', 30), Person('Bob', 25)]
sorted(people, key=attrgetter('age'))  # [Bob, Alice]

itemgetter('age') — эквивалент lambda d: d['age'], но быстрее (no Python frame overhead — implemented in C). Для high-frequency sort’ов / map’ов — заметная разница.

attrgetter('age') — эквивалент lambda x: x.age. Обычная convention для key= параметра в sorted / min / max / groupby.

Cross-course context

Ключевые выводы

1. map / filter — lazy iterators; gen-expression — обычно более Pythonic эквивалент. Используйте map(named_func, iter) без lambda.
2. functools.reduce — fold-агрегатор для свёрток за рамками sum / max / min. Не злоупотреблять — читаемость страдает.
3. functools.partial — bind аргументов, возвращает новый callable. Adapter / proxy pattern.
4. functools.lru_cache (или @cache) — single-line memoization. Args обязаны быть hashable (cache использует dict). C-accelerated.
5. itertools — целый zoo lazy combinators. chain / islice / count / cycle / groupby / takewhile — основные. Все на iterator protocol — preview Phase 66 M05.
6. operator module — callable operators (add, mul, itemgetter, attrgetter) — быстрее lambda для высокочастотных операций.