Функторы: модули, параметризованные модулями

Поднимаемся на вершину модульной системы OCaml — функторы, которые превращают модули в строительные блоки, параметризуемые другими модулями.

Функтор — это «функция» уровня модулей: она принимает модуль и возвращает новый модуль, построенный на его основе.

Если обычная функция принимает значение и возвращает значение, то функтор принимает модуль и возвращает модуль. Это позволяет писать обобщённые структуры данных, параметризованные не одним типом, а целым набором операций. Именно функторы делают модульную систему OCaml уникально мощной.

Зачем это нужно

Представьте структуру «множество». Чтобы хранить элементы упорядоченно, ей нужна операция сравнения, разная для чисел, строк, своих типов. В OCaml вы параметризуете весь модуль множества модулем сравнения.

Сигнатура параметра

module type ORDERED = sig
  type t
  val compare : t -> t -> int
end

Функтор

module MakeSet (Elt : ORDERED) = struct
  type elt = Elt.t
  type t = elt list      (* упорядоченный список без дублей *)

  let empty = []

  let rec add x = function
    | [] -> [x]
    | y :: rest as s ->
      let c = Elt.compare x y in
      if c = 0 then s                  (* уже есть *)
      else if c < 0 then x :: s        (* вставка перед y *)
      else y :: add x rest

  let mem x s = List.exists (fun y -> Elt.compare x y = 0) s
end

Внутри функтора мы вызываем Elt.compare, не зная, какой именно тип придёт. Параметр Elt — «дырка», которую заполнят при применении.

Применение функтора

module IntOrd = struct
  type t = int
  let compare = compare    (* стандартное сравнение *)
end

module IntSet = MakeSet (IntOrd)

let s = IntSet.add 3 (IntSet.add 1 (IntSet.add 3 IntSet.empty))
(* множество {1; 3}, дубль 3 не добавился *)
let has = IntSet.mem 1 s   (* true *)

Тот же функтор даст StringSet, если передать модуль сравнения строк. Логика написана один раз, а специализируется под любой упорядочиваемый тип. Так в стандартной библиотеке устроены настоящие Map.Make и Set.Make.

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

Функтор — конструкция времени компиляции. Когда вы пишете MakeSet (IntOrd), компилятор подставляет IntOrd на место Elt и порождает специализированный модуль. Применение проверяется по типам: переданный модуль обязан удовлетворять сигнатуре ORDERED. Сравните с дженериками Java: там ограничение задаётся одним интерфейсом, здесь — целой сигнатурой с типами и значениями, что несравнимо выразительнее. Накладных расходов в рантайме нет.

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

• Передать модуль, не удовлетворяющий сигнатуре. Если в IntOrd забыть compare, функтор не применится.
• Считать функтор обычной функцией над значениями. Он работает с модулями на этапе компиляции.
• Изобретать своё вместо Map.Make/Set.Make. Стандартная библиотека уже даёт функторы для словарей и множеств.

Итоги

• Функтор — функция от модуля к модулю; он параметризует структуру данных набором операций.
• Параметр задаётся сигнатурой (ORDERED с типом и compare), применение — MakeSet (IntOrd).
• Так реализованы Map.Make и Set.Make; накладных расходов в рантайме нет.