Теория категорий в программировании: функторы, монады, F-алгебры, линзы

В предыдущей статье трека — Теория категорий: объекты, морфизмы, функторы, естественные преобразования — мы построили аппарат: категория, функтор, естественное преобразование, начальный объект. Всё это выглядело как «абстрактная чепуха» (сами категорщики называют свою науку abstract nonsense, и это комплимент).

Эта статья отвечает на вопрос «и что?». Ответ короткий: теория категорий — это теория композиции, а программирование в большом — тоже про композицию. Когда вы спрашиваете «почему Optional.map не даёт склеить два запроса к базе», «почему валидация формы должна собирать все ошибки, а не первую», «почему обновление вложенного JSON превращается в лапшу из спредов» — вы задаёте категорные вопросы, и у них есть точные ответы с доказуемыми законами.

Практическая ставка здесь одна: закон, который выполняется, — это рефакторинг, который безопасен. Если ваш тип честный функтор, переписать xs.map(f).map(g) в xs.map(g . f) можно не «наверное», а по теореме.

Категория типов: где именно мы работаем

Определение. Категория C состоит из класса объектов Ob(C); для каждой пары A, B — множества морфизмов C(A, B); композиции . : C(B,C) × C(A,B) -> C(A,C); тождеств id_A ∈ C(A, A). Аксиомы:

ассоциативность:   h . (g . f) = (h . g) . f
единица:           f . id_A = f = id_B . f      для f : A -> B

Это всё. Никаких «элементов» внутри объектов — объекты непрозрачны, вся информация живёт в стрелках. Этим категория отличается от множества: множество описывают через «что в нём лежит», категорию — через «что во что отображается».

Категория типов вашего языка. Объекты — типы (int, str, list[int], User), морфизмы A -> B — функции, композиция обычная, id_A = lambda x: x.

def compose(f, g):
    """(f . g)(x) = f(g(x)) — сначала g, потом f."""
    return lambda x: f(g(x))

def identity(x):
    return x

f, g, h = lambda n: n + 1, lambda n: n * 2, str      # int->int, int->int, int->str
assert compose(compose(h, g), f)(5) == compose(h, compose(g, f))(5) == "12"
assert compose(f, identity)(5) == f(5) == compose(identity, f)(5)

Честная оговорка: «Hask — не категория». В любом реальном языке есть незавершение: исключения, бесконечные циклы, undefined, null. В Haskell это ⊥ (bottom), живущее в каждом типе, и закон единицы ломается на seq — разбор в Hask is not a category Андрея Бауэра. Вывод не «всё пропало», а: мы работаем в категории, где законы выполняются с точностью до неопределённости и побочных эффектов. Пока вы не вызываете seq/unsafePerformIO и не бросаете исключения из чистых функций, всё дальнейшее верно. В Python оговорка жёстче: язык не проверяет ни чистоту, ни законы — ответственность на вас и тестах.

Функтор: не «контейнер», а сохраняющее структуру отображение

Определение. Функтор F : C -> D — пара отображений: на объектах A -> F(A) и на морфизмах (f : A -> B) -> (F(f) : F(A) -> F(B)), такая что

(F1)  F(id_A) = id_{F(A)}          сохранение тождества
(F2)  F(g . f) = F(g) . F(f)       сохранение композиции

Нас интересуют эндофункторы на категории типов, F : Type -> Type. Отображение на объектах — конструктор типа (list, Maybe, Result, Future), отображение на морфизмах — map/fmap. На языке кода:

(F1)  fmap(identity, x) == x
(F2)  fmap(compose(g, f), x) == fmap(g, fmap(f, x))

Интуиция. Функтор — это изменение контекста, которое не трогает форму: list — «ноль или больше значений», Maybe — «значение может отсутствовать», Future — «значение появится потом», Either[E, _] — «значение или ошибка типа E». fmap говорит: делай своё дело с содержимым, форму контейнера не меняй. Первый закон запрещает функтору работать тайком: если применяемая функция ничего не делает, fmap тоже обязан ничего не сделать. Это отсекает «функторы», которые считают вызовы, перемешивают список или логируют. Второй закон — тот самый безопасный рефакторинг: два прохода сливаются в один. На нём стоят loop fusion в GHC, stream fusion, слияние операций в Spark и векторизованных движках БД.

Про свободные теоремы. В достаточно полиморфных языках (F2) следует из (F1) по параметричности — теорема Уодлера, Theorems for free!, FPCA 1989. В Haskell достаточно проверить один закон. В Python, TypeScript, Java параметричность нарушается (рефлексия, instanceof, мутация), поэтому проверять надо оба.

from dataclasses import dataclass
from typing import Any, Generic, TypeVar

A = TypeVar("A")

@dataclass(frozen=True)
class Just(Generic[A]):
    value: A

@dataclass(frozen=True)
class Nothing:
    pass

def fmap_maybe(f, m):
    """Действие функтора Maybe на морфизмах."""
    return Just(f(m.value)) if isinstance(m, Just) else m

inc, dbl = lambda x: x + 1, lambda x: x * 2
assert fmap_maybe(identity, Just(3)) == Just(3)                                       # (F1)
assert fmap_maybe(identity, Nothing()) == Nothing()                                   # (F1)
assert fmap_maybe(compose(inc, dbl), Just(3)) == fmap_maybe(inc, fmap_maybe(dbl, Just(3)))  # (F2)

Сложность fmap: O(1) для Maybe, O(n) времени и памяти для list, O(1) на элемент при потреблении для ленивых потоков.

Что функтором не является. Callable[[A], R] — функтор по R, но контравариантный функтор по A: есть contramap(f: X -> A) -> Callable[[X], R]. Отсюда вариантность в системах типов: Function<in T, out R> в Kotlin, Func<in T, out TResult> в C#. Predicate[A] и Comparator[A] — чистые контрафункторы: умеют contramap, но не map. А Data.Set в Haskell не может быть инстансом Functor, потому что map требует Ord — нужен ограниченный функтор.

Лестница абстракций: Functor -> Applicative -> Monad

Это не «Monad лучше Applicative». Ровно наоборот: чем слабее абстракция, тем больше о программе известно статически. Аппликатив не может посмотреть на результат шага и решить, что делать дальше, — поэтому его можно распараллелить, проанализировать, скомпилировать в план запроса. Это ключевой trade-off всей статьи.

Аппликативный функтор

Определение. F аппликативен, если есть pure : A -> F[A] и ap : F[A -> B] -> F[A] -> F[B] с законами:

identity:      ap(pure(id), v) = v
homomorphism:  ap(pure(f), pure(x)) = pure(f(x))
interchange:   ap(u, pure(y)) = ap(pure(lambda f: f(y)), u)
composition:   ap(ap(ap(pure(compose), u), v), w) = ap(u, ap(v, w))

Эквивалентная и более наглядная формулировка — лаксовый моноидальный функтор: есть unit : () -> F[()] и zip : F[A] × F[B] -> F[(A, B)], ассоциативный с точностью до изоморфизма. То есть аппликатив — «функтор, умеющий склеить два независимых контекста».

Каноническое применение: валидация с накоплением ошибок. Монада Either останавливается на первой ошибке — потому что второй шаг зависит от первого. Аппликатив знает все шаги заранее и собирает все ошибки. Это не стилистика, а следствие сигнатуры.

@dataclass(frozen=True)
class Valid:
    value: Any

@dataclass(frozen=True)
class Invalid:
    errors: tuple                    # моноид: конкатенация

def pure(x): return Valid(x)

def ap(vf, va):
    if isinstance(vf, Valid) and isinstance(va, Valid):
        return Valid(vf.value(va.value))
    if isinstance(vf, Invalid) and isinstance(va, Invalid):
        return Invalid(vf.errors + va.errors)          # <- накопление, а не короткое замыкание
    return vf if isinstance(vf, Invalid) else va

def liftA3(f, a, b, c):
    curried = lambda x: lambda y: lambda z: f(x, y, z)
    return ap(ap(ap(pure(curried), a), b), c)

def check(cond, value, msg):
    return Valid(value) if cond else Invalid((msg,))

@dataclass(frozen=True)
class User:
    name: str; age: int; email: str

def validate(name, age, email):
    return liftA3(User,
                  check(len(name) > 0, name,  "имя пустое"),
                  check(0 < age < 130, age,   "возраст вне диапазона"),
                  check("@" in email,  email, "email без @"))

print(validate("Ada", 36, "ada@example.com"))
# Valid(value=User(name='Ada', age=36, email='ada@example.com'))
print(validate("", 999, "nope"))
# Invalid(errors=('имя пустое', 'возраст вне диапазона', 'email без @'))

Invalid требует, чтобы ошибки лежали в моноиде (ассоциативная операция + нейтральный элемент — см. Абстрактная алгебра). Это не случайность: Validation[E, _] аппликативен ровно тогда, когда E — полугруппа. Так устроены cats.data.Validated в Scala, Data.Validation в Haskell, Ecto.Changeset в Elixir.

Поэтому аппликативны парсер-комбинаторы (структура грамматики известна до разбора — можно строить таблицы), формы в UI (поля независимы, валидируются параллельно), Promise.all (запросы летят одновременно). На этом же Facebook строит автоматический батчинг обращений к бэкендам — Haxl: A Big Hammer for Concurrency, ICFP 2014.

Монада: композиция эффектных функций

Три эквивалентных определения — от самого абстрактного к самому рабочему.

(1) Категорное. Монада на C — тройка (T, eta, mu), где T : C -> C — эндофунктор, eta : Id ~> T и mu : T∘T ~> T — естественные преобразования, причём mu . T(mu) = mu . mu_T (ассоциативность) и mu . T(eta) = id = mu . eta_T (единица).

(2) «Моноид в категории эндофункторов». Знаменитая фраза Mac Lane. Расшифровка простая: в категории эндофункторов [C, C] композиция ∘ — это «умножение», Id — «единица». Моноид в этой моноидальной категории — объект T со стрелками mu : T ⊗ T -> T и eta : I -> T, то есть ровно T∘T -> T и Id -> T. Никакой мистики: аксиомы моноида, где «элементы» заменены на функторы.

(3) Программистское, через Клейсли. Даны unit : A -> M[A] (он же pure, return) и bind : M[A] -> (A -> M[B]) -> M[B] (он же flatMap, >>=, then) с законами:

левая единица:   bind(unit(a), k)    == k(a)
правая единица:  bind(m, unit)       == m
ассоциативность: bind(bind(m, k), h) == bind(m, lambda x: bind(k(x), h))

Третья форма полезнее всего. Она говорит: функции вида A -> M[B] (стрелки Клейсли) образуют свою категорию Kl(M), где композиция — (f >=> g)(x) = bind(f(x), g), а тождество — unit. Законы монады — это в точности аксиомы категории для Kl(M). Монада делает эффектные функции композируемыми так же, как обычные.

import math

def bind_maybe(m, k):
    return k(m.value) if isinstance(m, Just) else m

def safe_div(a, b):  return Just(a / b) if b != 0 else Nothing()
def safe_sqrt(x):    return Just(math.sqrt(x)) if x >= 0 else Nothing()

k, h = lambda x: safe_div(10, x), safe_sqrt
assert bind_maybe(Just(5), k) == k(5)                                          # левая единица
assert bind_maybe(Just(5), Just) == Just(5)                                    # правая единица
assert (bind_maybe(bind_maybe(Just(5), k), h)
        == bind_maybe(Just(5), lambda x: bind_maybe(k(x), h)))                 # ассоциативность

def kleisli(f, g):
    """Композиция стрелок Клейсли: f >=> g."""
    return lambda x: bind_maybe(f(x), g)

pipeline = kleisli(lambda x: safe_div(100, x), safe_sqrt)
print(pipeline(4), pipeline(0))     # Just(value=5.0) Nothing()  — короткое замыкание бесплатно

Ассоциативность — не педантизм: она означает, что группировка шагов конвейера не влияет на результат. Три шага можно вынести в отдельную функцию и вставить в середину пайплайна, ничего не сломав; без этого закона рефакторинг «выдели метод» перестаёт быть безопасным.

Каждая стрелка — морфизм в Kl(Result[_, E]). Обработка ошибок не написана явно нигде: она встроена в композицию. Ровно это делают ? в Rust, with в Elixir, do-нотация в Haskell, for-comprehension в Scala, async/await в JS/C#/Python.

Какие монады вы уже используете

list как монада — это SQL.

def bind_list(xs, k):
    return [y for x in xs for y in k(x)]

pyth = bind_list(range(1, 21), lambda a:
        bind_list(range(a, 21), lambda b:
         bind_list(range(b, 21), lambda c:
          [(a, b, c)] if a * a + b * b == c * c else [])))
print(pyth)  # [(3, 4, 5), (5, 12, 13), (6, 8, 10), (8, 15, 17), (9, 12, 15), (12, 16, 20)]

Тот же bind_list — это SELECT ... FROM a, b, c WHERE .... Реляционная алгебра и монада списка совпадают с точностью до нотации; отсюда LINQ в C#, где SelectMany буквально и есть монадическое связывание.

State как монада — это компилятор.

from typing import Callable

@dataclass(frozen=True)
class State:
    run: Callable[[Any], tuple]              # s -> (a, s)

    def bind(self, k):
        def go(s):
            a, s1 = self.run(s)
            return k(a).run(s1)
        return State(go)

    def map(self, f):  return self.bind(lambda a: State.pure(f(a)))
    @staticmethod
    def pure(a):       return State(lambda s: (a, s))

def get():   return State(lambda s: (s, s))
def put(s1): return State(lambda s: (None, s1))
def fresh(prefix):                           # уникальные имена без глобального счётчика
    return get().bind(lambda n: put(n + 1).bind(lambda _: State.pure(f"{prefix}{n}")))

prog = fresh("tmp").bind(lambda a:
       fresh("tmp").bind(lambda b:
       fresh("lbl").map(lambda c: (a, b, c))))
print(prog.run(0))                           # (('tmp0', 'tmp1', 'lbl2'), 3)

Состояние здесь не переменная, а часть типа. prog — чистая функция: одинаковый вход даёт одинаковый выход, её можно гонять в тестах сколько угодно. Сложность — O(числа шагов) по времени и O(глубины цепочки) по стеку; в Python это реальное ограничение, в Scala и Haskell спасают трамплины.

Типичные заблуждения

• «Монада — это про побочные эффекты». Нет. Maybe, list, Reader, State чисты. Побочный эффект есть только у IO, и то не в монаде, а в её интерпретации рантаймом. Монада — про композицию с контекстом.
• «Монада — это контейнер/буррито». Reader[R, A] = R -> A ничего не содержит, Cont тем более. Метафора работает для list/Maybe и ломается на половине примеров — лучше думать «стрелки Клейсли композируются».
• «Promise в JS — монада». Почти, но нет: then расплющивает вложенные промисы, поэтому Promise[Promise[A]] невыразим, и левый закон единицы нарушается для thenable: Promise.resolve(x).then(f) не равно f(x), если у x есть метод then. Разбор — Promises are not monads.
• «Раз есть монада, надо всё писать монадически». Худшая ошибка: монада — самая ограничивающая ступень лестницы, она навязывает последовательность. Если шаги независимы, берите аппликатив и получите параллелизм даром. Правило: используйте самую слабую абстракцию, которой хватает.

Почему монады плохо композируются

Композиция двух функторов — всегда функтор, двух аппликативов — всегда аппликатив, а вот двух монад — в общем случае не монада: из M[N[M[N[A]]]] нельзя получить M[N[A]], не зная, как N переставляется с M. Формально за это отвечает дистрибутивный закон lambda : N∘M ~> M∘N (Бек, 1969); для многих пар его просто не существует — это теорема, а не недоработка библиотеки. Отсюда два инженерных пути: монадные трансформеры (StateT, ReaderT, ExceptT) задают перестановку вручную, но дают тяжёлые сигнатуры и квадратичную проблему lifting; алгебраические эффекты описывают эффекты как данные и интерпретируют отдельно — так устроены polysemy и effectful в Haskell, эффекты в OCaml 5, ZIO в Scala.

Естественные преобразования: интерфейсы между функторами

Определение. Пусть F, G : C -> D — функторы. Естественное преобразование alpha : F ~> G — семейство морфизмов alpha_A : F(A) -> G(A), по одному на объект, такое что для любого f : A -> B коммутирует квадрат G(f) . alpha_A = alpha_B . F(f).

В коде это полиморфная функция forall a. F[a] -> G[a], которая не смотрит на содержимое:

def head(xs):
    """list ~> Maybe. Естественное преобразование."""
    return Just(xs[0]) if xs else Nothing()

f, xs = str, [1, 2, 3]
assert fmap_maybe(f, head(xs)) == head(list(map(f, xs)))     # квадрат коммутирует
assert fmap_maybe(f, head([])) == head(list(map(f, [])))

reverse, head, to_list, Maybe -> list, sequence — всё это естественные преобразования. Их «естественность» означает: они не зависят от типа элементов, а значит, не могут их испортить. Тот же принцип, что у свободных теорем: из сигнатуры forall a. [a] -> [a] уже следует, что функция умеет только переставлять, удалять и дублировать элементы, но не создавать новые. Практически: любой честный адаптер между обобщёнными коллекциями обязан быть естественным преобразованием, иначе он ломает map.

F-алгебры и катаморфизмы: рекурсия как данные

Самая недооценённая практическая часть: она отвечает на вопрос как перестать писать одну и ту же рекурсию по AST двадцать раз.

Определение. Пусть F : Type -> Type — функтор. F-алгебра — пара (A, alg), где A — тип-носитель, alg : F[A] -> A. Морфизм F-алгебр (A, alg) -> (B, beta) — функция h : A -> B с h . alg = beta . F(h).

Теорема (Ламбек). Если в категории F-алгебр есть начальный объект (Fix F, in), то in : F[Fix F] -> Fix F — изоморфизм, то есть Fix F ≅ F[Fix F]. Начальная алгебра — это неподвижная точка функтора, и она в точности соответствует рекурсивному типу данных. Начальность даёт главный инструмент: для любой F-алгебры (A, alg) существует ровно один морфизм cata(alg) : Fix F -> A — катаморфизм (свёртка), заданный уравнением cata(alg) = alg . F(cata(alg)) . unfix.

Читается так: спуститься на уровень вниз, свернуть поддеревья рекурсивно, применить alg к результату. Коммутативность квадрата — это и есть корректность свёртки.

Зачем на практике. Классический интерпретатор AST смешивает обход структуры и логику узла. Из-за этого eval, pretty-print, оптимизация, сбор переменных, подсчёт глубины — пять почти одинаковых рекурсий, каждая со своим шансом забыть ветку. F-алгебра их разделяет: обход пишется один раз, а каждая задача — плоская нерекурсивная функция F[A] -> A, полноту веток которой проверяет match.

# сигнатурный функтор: "один слой" выражения, дырки вместо поддеревьев
@dataclass(frozen=True)
class LitF: value: int
@dataclass(frozen=True)
class VarF: name: str
@dataclass(frozen=True)
class AddF: left: Any; right: Any
@dataclass(frozen=True)
class MulF: left: Any; right: Any

@dataclass(frozen=True)
class Fix:
    """Неподвижная точка: Fix F ≅ F[Fix F] (теорема Ламбека)."""
    unfix: Any

def lit(n):    return Fix(LitF(n))
def var(s):    return Fix(VarF(s))
def add(a, b): return Fix(AddF(a, b))
def mul(a, b): return Fix(MulF(a, b))

def fmap_expr(f, fa):
    """Действие функтора ExprF на морфизмах: f применяется к дыркам."""
    match fa:
        case LitF(_) | VarF(_): return fa
        case AddF(l, r):        return AddF(f(l), f(r))
        case MulF(l, r):        return MulF(f(l), f(r))
    raise TypeError(fa)

def cata(alg, t):
    """Единственный морфизм из начальной алгебры. Обход написан ОДИН раз."""
    return alg(fmap_expr(lambda sub: cata(alg, sub), t.unfix))

# --- четыре задачи = четыре плоские функции, ни одной рекурсии ---

def show_alg(fa):                            # носитель = str
    match fa:
        case LitF(v):    return str(v)
        case VarF(n):    return n
        case AddF(l, r): return f"({l} + {r})"
        case MulF(l, r): return f"({l} * {r})"

def eval_alg(fa):                            # носитель = Callable[[dict], int] — это Reader!
    match fa:
        case LitF(v):    return lambda env: v
        case VarF(n):    return lambda env: env[n]
        case AddF(l, r): return lambda env: l(env) + r(env)
        case MulF(l, r): return lambda env: l(env) * r(env)

def vars_alg(fa):                            # носитель = frozenset[str]
    match fa:
        case LitF(_):                 return frozenset()
        case VarF(n):                 return frozenset({n})
        case AddF(l, r) | MulF(l, r): return l | r

def fold_alg(fa):                            # носитель = сам Fix ExprF — оптимизирующий проход
    match fa:
        case AddF(Fix(LitF(a)), Fix(LitF(b))): return lit(a + b)
        case MulF(Fix(LitF(a)), Fix(LitF(b))): return lit(a * b)
        case MulF(Fix(LitF(0)), _) | MulF(_, Fix(LitF(0))): return lit(0)
        case AddF(Fix(LitF(0)), x) | AddF(x, Fix(LitF(0))): return x
        case _:                                return Fix(fa)

e = add(mul(lit(2), lit(3)), mul(var("x"), add(lit(4), lit(-4))))
print(cata(show_alg, e))                  # ((2 * 3) + (x * (4 + -4)))
print(cata(eval_alg, e)({"x": 100}))      # 6
print(sorted(cata(vars_alg, e)))          # ['x']
print(cata(show_alg, cata(fold_alg, e)))  # 6   <- свёртка констант сработала

Обратите внимание на eval_alg: носитель — функциональный тип. Здесь метафора «контейнера» окончательно ломается, а формальное определение работает без запинки. И это же — стандартный приём «компиляции в замыкания» (closure conversion), дающий интерпретаторам кратное ускорение: AST разбирается один раз, дальше выполняется дерево замыканий. Сложность cata — O(n) по числу узлов и O(h) по стеку, столько же, сколько у ручной рекурсии: абстракция бесплатна по асимптотике и стоит одного вызова fmap на узел по константе.

Двойственная сторона. Перевернём стрелки: коалгебра coalg : A -> F[A] и анаморфизм ana : A -> Fix F — разворачивание. hylo = cata . ana сворачивает сразу после разворачивания, не материализуя промежуточное дерево — это буквально описание deforestation и потоковой обработки:

def hylo(alg, coalg, seed):                  # разворачиваем и тут же сворачиваем
    return alg(fmap_expr(lambda s: hylo(alg, coalg, s), coalg(seed)))

Каноническая работа — Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire (Meijer, Fokkinga, Paterson, 1991); практическая реализация — recursion-schemes.

Trade-off, о котором молчат энтузиасты. Fix в языках без специализации типов стоит лишней аллокации на узел, а плоские алгебры хуже читаются, когда логика узла требует контекста сверху («упростить, зная тип родителя»). Для таких проходов нужны paramorphism (доступ к исходному поддереву) или zygomorphism (две алгебры сразу), и сложность растёт быстро. Совет: применяйте cata там, где проходов много и они однотипны (компиляторы, линтеры, SQL-планировщики); для одного-двух проходов ручная рекурсия честнее.

Линзы и оптика: композируемый доступ к вложенным данным

Неизменяемые структуры прекрасны — до момента, когда надо поменять одно поле на пятом уровне вложенности. Спреды в JS, copy(...) в Kotlin, replace() в Python быстро превращаются в лапшу и, что хуже, не композируются: нельзя передать «путь к полю» как значение.

Определение. Линза Lens[S, A] — пара функций get : S -> A и set : S -> A -> S с тремя законами (это делает её well-behaved):

(L1) get-set:  set(s, get(s)) == s                 «положить то же — ничего не менять»
(L2) set-get:  get(set(s, b)) == b                 «что положили, то и достаём»
(L3) set-set:  set(set(s, b1), b2) == set(s, b2)   «последняя запись побеждает»

Категорно Lens[S, A] соответствует представлению S ≅ C × A для некоторого «остатка» C, то есть утверждению «S состоит из фокуса A и всего остального» — отсюда сразу видно, почему set не может испортить соседей.

from dataclasses import replace

@dataclass(frozen=True)
class Lens:
    get: Callable[[Any], Any]
    set: Callable[[Any, Any], Any]

    def over(self, s, f):
        """Модификация: применить функцию к фокусу."""
        return self.set(s, f(self.get(s)))

    def __rshift__(self, other):
        """Композиция линз — это композиция морфизмов в категории линз."""
        return Lens(get=lambda s: other.get(self.get(s)),
                    set=lambda s, b: self.set(s, other.set(self.get(s), b)))

def field(name):
    return Lens(get=lambda s: getattr(s, name),
                set=lambda s, b: replace(s, **{name: b}))

def key(k):
    return Lens(get=lambda d: d[k], set=lambda d, b: {**d, k: b})

def at(i):
    def _set(xs, b):
        ys = list(xs); ys[i] = b
        return type(xs)(ys)
    return Lens(get=lambda xs: xs[i], set=_set)

@dataclass(frozen=True)
class Addr:    city: str; zip: str
@dataclass(frozen=True)
class Person:  name: str; addr: Addr
@dataclass(frozen=True)
class Company: title: str; staff: tuple

c = Company("Acme", (Person("Ada",  Addr("Лондон",   "E1")),
                     Person("Alan", Addr("Уилмслоу", "SK9"))))

L = field("staff") >> at(0) >> field("addr") >> field("city")
print(L.get(c))                                    # Лондон
print(L.set(c, "Кембридж").staff[0].addr.city)     # Кембридж
print(c.staff[0].addr.city)                        # Лондон — исходник не тронут
print(L.over(c, str.upper).staff[0].addr.city)     # ЛОНДОН

s, b, b2 = c, "Оксфорд", "Йорк"                    # три закона линзы
assert L.get(L.set(s, b)) == b
assert L.set(s, L.get(s)) == s
assert L.set(L.set(s, b), b2) == L.set(s, b2)

# та же линза работает с JSON-конфигом: key и field живут в одной категории
cfg = {"server": {"http": {"port": 8080, "host": "0.0.0.0"}}}
port = key("server") >> key("http") >> key("port")
print(port.over(cfg, lambda p: p + 1))
# {'server': {'http': {'port': 8081, 'host': '0.0.0.0'}}}

Ключевое свойство: линза — это значение. Её можно положить в словарь, передать в функцию, собрать динамически из строки пути, переиспользовать в тестах — ничего из этого не даёт синтаксис доступа к полям. Сложность get/set — O(d) по глубине пути; set копирует только узлы на пути (см. SVG выше), остальное разделяется — то же persistent-обновление, что в структурах Clojure и в immer/Redux.

Семейство оптик

Все они композируются между собой, и результат «понижается» до наименее мощной оптики в цепочке: Lens >> Prism = Affine, Lens >> Traversal = Traversal. Та же лестница, что у Functor/Applicative/Monad, и снова: слабее = больше свободы у реализации. Красивая унификация — ван-Лааровеновское представление: одна сигнатура задаёт всю иерархию, а тип оптики определяется констрейнтом на функтор F:

Optic S T A B = forall F. Constraint F => (A -> F[B]) -> (S -> F[T])

F ~ Functor      => Lens
F ~ Applicative  => Traversal
F ~ Const        => Getter / Fold
F ~ Identity     => Setter

Поэтому в библиотеке lens все оптики композируются обычным .: они буквально функции. Ещё более общее — профункторная оптика (Profunctor Optics: Modular Data Accessors, Pickering, Gibbons, Wu, 2017), на которой построены monocle (Scala), optics-ts (TypeScript), lens-rs (Rust).

Traversal через аппликатив

Обход — место, где аппликатив возвращается в полный рост: traverse обходит структуру, выполняя эффект, и собирает результат.

def traverse_list(f, xs, pure_, ap_):
    """f : A -> F[B]; результат: F[list[B]]. Работает для ЛЮБОГО аппликатива."""
    acc = pure_([])
    for x in xs:
        acc = ap_(ap_(pure_(lambda ys: lambda y: ys + [y]), acc), f(x))
    return acc

def parse_port(s):
    try:
        n = int(s)
    except ValueError:
        return Invalid((f"{s!r}: не число",))
    return Valid(n) if 1 <= n <= 65535 else Invalid((f"{n}: вне диапазона",))

print(traverse_list(parse_port, ["80", "8080", "443"], pure, ap))
# Valid(value=[80, 8080, 443])
print(traverse_list(parse_port, ["80", "abc", "99999"], pure, ap))
# Invalid(errors=("'abc': не число", '99999: вне диапазона'))

Подставьте вместо Validation монаду IO — получите «выполнить N запросов и собрать результаты». Подставьте Future — получите Promise.all. Один traverse, разные аппликативы. Теория за этим — The Essence of the Iterator Pattern (Gibbons, Oliveira, 2009), где классический GoF-паттерн Iterator оказывается ровно Traversable.

Free-монада: программа как данные

Категорные идеи дают не только утилиты, но и архитектуру. Идея: вместо выполнения эффектов построим дерево описаний эффектов (свободная монада над функтором инструкций) и отдадим его интерпретатору. Одна программа — много интерпретаторов: боевой, тестовый, анализирующий.

@dataclass(frozen=True)
class Pure: value: Any
@dataclass(frozen=True)
class Free: op: Any
@dataclass(frozen=True)
class ReadKey:  key: str; next: Callable[[Any], Any]
@dataclass(frozen=True)
class WriteKey: key: str; value: Any; next: Callable[[None], Any]

def read_key(k):     return Free(ReadKey(k, lambda v: Pure(v)))
def write_key(k, v): return Free(WriteKey(k, v, lambda _: Pure(None)))

def bind(prog, f):                       # bind «доклеивает» f к продолжению
    match prog:
        case Pure(v):                 return f(v)
        case Free(ReadKey(k, n)):     return Free(ReadKey(k,     lambda v: bind(n(v), f)))
        case Free(WriteKey(k, v, n)): return Free(WriteKey(k, v, lambda u: bind(n(u), f)))

program = bind(read_key("counter"), lambda v:
          bind(write_key("counter", v + 1), lambda _: Pure(v + 1)))

def run_pure(prog, store):               # интерпретатор: чистый, для тестов, без моков
    match prog:
        case Pure(v):                 return v
        case Free(ReadKey(k, n)):     return run_pure(n(store.get(k, 0)), store)
        case Free(WriteKey(k, v, n)): store[k] = v; return run_pure(n(None), store)

store = {"counter": 41}
print(run_pure(program, store), store)   # 42 {'counter': 42}

program — это значение, а не выполнение: тот же объект можно скормить интерпретатору поверх Redis, логгеру или анализатору, собирающему список затрагиваемых ключей.

Ограничение. Проанализировать Free-программу целиком статически нельзя: продолжение спрятано в замыкании и зависит от результата предыдущего шага, поэтому анализатор увидит только первую ветку. Для батчинга берут Free Applicative (FreeAp) — там структура полностью статична; тот же trade-off «монада против аппликатива», но на уровне архитектуры. По производительности наивная Free даёт квадратичное поведение при левоассоциативных bind (та же проблема, что у конкатенации списков слева); лечится Codensity/Church-кодированием (Van der Ploeg, Kiselyov, 2014). В проде вместо Free чаще берут tagless final или готовые эффект-системы (ZIO, cats-effect, polysemy).

Trade-offs: когда это окупается, а когда нет

Окупается. Компиляторы, линтеры, планировщики запросов — много однотипных проходов по одной структуре, катаморфизмы экономят реально. Валидация и парсинг — аппликатив даёт накопление ошибок и параллелизм из коробки. Большие неизменяемые конфиги и состояние — оптика убирает лапшу и делает пути переиспользуемыми. Тестируемость эффектов — Free и tagless final заменяют горы моков одним чистым интерпретатором.

Не окупается. В языках без высших родов (* -> * как параметр типа) — Go, Java, Python — нельзя написать «функцию для любого функтора» с проверкой типов, и абстракция вырождается в соглашение, а соглашения ломаются. В небольших кодовых базах с одним проходом по данным cata + Fix дороже понятной рекурсии. В команде без общего словаря стоимость поддержки перевешивает выигрыш: категорные имена не самоцель, можно назвать bind словом and_then и получить 90 % пользы. На горячем пути обёртки, замыкания и Fix стоят аллокаций — меряйте.

Самая частая ошибка — тянуть абстракцию сильнее, чем нужно. Иерархия Functor -> Applicative -> Monad задумана как лестница, по которой поднимаются ровно на нужную ступень: каждая следующая покупает выразительность ценой потери информации о программе.

Мини-итог

• Категория типов: объекты — типы, морфизмы — функции; все законы про композицию и тождество.
• Функтор (map) — отображение, сохраняющее композицию. Закон (F2) = право слить два прохода в один.
• Аппликатив (ap/zip) — комбинация независимых эффектов: накопление ошибок, параллелизм, статический анализ.
• Монада (bind) — композиция стрелок Клейсли A -> M[B]. Зависимость шага от предыдущего ценой строгой последовательности; композируется плохо, отсюда трансформеры и эффект-системы.
• Естественное преобразование — полиморфный адаптер forall a. F[a] -> G[a], коммутирующий с map.
• F-алгебра и катаморфизм — обход рекурсивной структуры написан один раз, логика узла — плоская функция F[A] -> A.
• Линзы и оптика — доступ к вложенным данным как композируемое значение с тремя законами; set копирует только путь.
• Free-монада — программа как данные, много интерпретаторов на одном описании.

Источники

• Saunders Mac Lane. Categories for the Working Mathematician, 2nd ed., Springer, 1998 — канон.
• Bartosz Milewski. Category Theory for Programmers — бесплатная книга и видеокурс; лучшая точка входа для инженера.
• Eugenio Moggi. Notions of Computation and Monads, Information and Computation, 1991.
• Philip Wadler. Monads for functional programming, 1995 — самое читаемое введение.
• Conor McBride, Ross Paterson. Applicative programming with effects, JFP 2008.
• Pickering, Gibbons, Wu. Profunctor Optics: Modular Data Accessors, arXiv:1703.10857.
• Документация recursion-schemes и lens на Hackage.
• Cats (Scala) и Arrow (Kotlin) — промышленные реализации всей иерархии.

Что дальше

Мы всё время говорили о том, как структурировать вычисления. Следующая статья спрашивает противоположное: что вообще вычислимо — и показывает, что у любой, сколь угодно красивой абстракции есть жёсткая граница, за которой не помогут ни монады, ни катаморфизмы.

Теория вычислимости: машина Тьюринга, лямбда-исчисление, проблема остановки