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

Понимаем, как одна функция может работать с любым типом данных благодаря переменным типа и почему это безопасно.

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

Мы уже встречали типы вроде 'a -> 'a и 'a list. Переменная 'a («альфа») означает «любой тип». Функции с такими типами называют полиморфными: написаны один раз, применимы к спискам чисел, строк, фигур. Это та же идея, что generics в Java/C#, но выведенная автоматически.

Полиморфные функции

let swap (a, b) = (b, a)
(* 'a * 'b -> 'b * 'a *)

let rec length = function
  | [] -> 0
  | _ :: t -> 1 + length t
(* 'a list -> int *)

length не смотрит на сами элементы (использует _), поэтому их тип остаётся 'a. Это источник полиморфизма — функция не накладывает ограничений.

Принцип параметричности

У параметрического полиморфизма есть глубокое свойство: функция типа 'a -> 'a обязана вернуть свой аргумент. Она не может «заглянуть внутрь» 'a, модифицировать его или создать значение этого типа из воздуха. Поэтому по одному типу можно угадать поведение: 'a list -> 'a list — это, скорее всего, перестановка/отбор, а не изменение элементов. Это свойство называют параметричностью.

Полиморфные структуры данных

type 'a tree =
  | Leaf
  | Node of 'a * 'a tree * 'a tree

let rec size = function
  | Leaf -> 0
  | Node (_, l, r) -> 1 + size l + size r
(* size : 'a tree -> int *)

'a tree — дерево с узлами любого типа. Один тип, бесконечно много применений.

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

В отличие от C++, где vector<int> и vector<string> порождают разный машинный код (мономорфизация), OCaml использует единообразное представление: значения всех типов в рантайме — это либо помеченное целое, либо указатель на блок одинакового формата. Поэтому полиморфная функция компилируется один раз и работает со всеми типами без дублирования. Плата — «упаковка» некоторых значений, но выигрыш — компактный код и быстрая компиляция.

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

• Считать 'a чем-то вроде Object с приведением в рантайме. Нет: тип фиксируется на этапе компиляции в каждой точке вызова.
• Ждать перегрузку по типу. Полиморфизм параметрический, а не ad-hoc.
• Сравнить 'a конкретным оператором, ломая полиморфизм. Например, + сразу зафиксирует тип как int.

Итоги

• Переменная типа 'a означает «любой тип»; функции с ней полиморфны и пишутся один раз.
• Параметричность: по полиморфному типу часто можно предсказать поведение функции.
• OCaml компилирует полиморфный код один раз благодаря единообразному представлению значений.