Параметрический полиморфизм и параметричность

Generics как они есть: одна реализация на все типы — и почему сам тип многое говорит о функции.

Параметрический полиморфизм — способность одной функции работать единообразно для всех типов, выраженная квантором forall a. в её типе.

Один код, все типы

Функция length считает длину списка независимо от того, что в нём лежит: её тип forall a. List a -> Int. Функция id : forall a. a -> a возвращает аргумент любого типа. Это и есть параметрический полиморфизм — то, что в Java/C#/Rust называют generics, в C++ — шаблонами, а в Haskell/ML встроено в систему типов через System F.

Слово «параметрический» подчёркивает: функция не смотрит на конкретный тип a, обращается с ним как с непрозрачным параметром. Это отличает её от ad-hoc полиморфизма (перегрузки), который для разных типов делает разное (следующий урок).

Параметричность: тип как теорема

Поразительное следствие — параметричность (теорема Рейнольдса, популяризованная Уодлером как «теоремы задаром»). Раз функция не может заглянуть в тип a, её поведение жёстко ограничено сигнатурой. Сколько тотальных функций имеет тип forall a. a -> a? Ровно одна — тождество: ей неоткуда взять значение типа a, кроме самого аргумента. Тип почти полностью определяет реализацию.

forall a. a -> a            -- только id
forall a. a -> a -> a       -- только две: вернуть 1-й или 2-й аргумент
forall a b. (a, b) -> a     -- только fst (проекция)
forall a. List a -> List a  -- перестановки/выбрасывания, но НЕ выдумывание новых элементов

Демонстрация: считаем «обитателей» полиморфных типов

Переберём, сколько разных тотальных функций можно написать для простого полиморфного типа, обращаясь с a как с непрозрачным. Для a -> a -> a их ровно две.

# функция типа a -> a -> a может ТОЛЬКО вернуть один из двух аргументов
def f_first(x, y):  return x
def f_second(x, y): return y

candidates = [("вернуть 1-й", f_first), ("вернуть 2-й", f_second)]
print("сколько тотальных функций типа a -> a -> a:", len(candidates))
for name, f in candidates:
    print(" ", name, "=>", f("A", "B"))

# для a -> a кандидат ровно один: тождество
def only_id(x): return x
print("функций типа a -> a:", 1, "(только id), id(7) =", only_id(7))

Вывод:

сколько тотальных функций типа a -> a -> a: 2
  вернуть 1-й => A
  вернуть 2-й => B
функций типа a -> a: 1 (только id), id(7) = 7

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

Как работает под капотом

В System F полиморфная функция явно принимает тип как аргумент: id = ΛA. \x:A. x, а применение — id [Int] 5. Компиляторы реализуют это двумя путями: мономорфизацией (Rust, C++ — генерируют отдельную копию под каждый конкретный тип, быстро, но раздувает код) или стиранием/боксингом (Java, Haskell GHC частично — одно представление, передача словарей/указателей, компактно, но с накладными расходами).

Частые ошибки

• Путать параметрический и ad-hoc полиморфизм. Первый одинаков для всех типов; второй (перегрузка) для разных типов делает разное.
• Думать, что полиморфная функция может «осмотреть» тип. В чистом параметрическом полиморфизме — нет; именно поэтому работает параметричность.
• Считать generics только синтаксисом. За ними стоит System F и реальные следствия (теоремы задаром, выбор стратегии компиляции).

Итоги

• Параметрический полиморфизм — одна функция forall a. ... для всех типов.
• Параметричность: непрозрачность a резко ограничивает поведение — тип почти задаёт реализацию.
• forall a. a -> a имеет ровно одного обитателя — тождество.
• Компиляция — мономорфизация (быстро, объёмно) или стирание/боксинг (компактно, с оверхедом).