Выбор реализации: функторы и модули как значения

У редактора теперь два режима истории. Для короткой локальной истории ты хочешь одну реализацию стека, для эксперимента другую. Нужно запустить обе в одном процессе, сравнить результаты и не переписывать отмену действий.

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

В предыдущем уроке ты отделил контракт STACK от представления и законов поведения. Теперь передашь реализацию как зависимость, сначала на уровне модулей, затем как обычное значение со скрытым типом.

Два стека поверх одного хранения

Сохрани исполняемые OCaml-блоки по порядку в implementations.ml и запусти ocaml implementations.ml. Программа самостоятельна: копировать файл предыдущего урока не нужно. Два блока с пометкой «не компилируется» оставь вне рабочего файла.

Первый стек кладёт вершину в начало списка. Второй кладёт вершину в конец. У обоих последний добавленный элемент извлекается первым.

(* 1. Общее хранение и два способа смотреть на него. *)
module type STACK = sig
  type 'a t
  val empty : 'a t
  val is_empty : 'a t -> bool
  val push : 'a -> 'a t -> 'a t
  val pop : 'a t -> ('a * 'a t) option
end

module Storage = struct
  type 'a t = 'a list
  let empty = []
  let is_empty = function [] -> true | _ -> false
  let prepend value items = value :: items
  let append value items = items @ [value]
  let take_first = function
    | [] -> None
    | value :: rest -> Some (value, rest)
  let rec take_last = function
    | [] -> None
    | [value] -> Some (value, [])
    | value :: rest ->
        match take_last rest with
        | None -> None
        | Some (last, prefix) -> Some (last, value :: prefix)
end

module HeadStack : STACK = struct
  type 'a t = 'a Storage.t
  let empty = Storage.empty
  let is_empty = Storage.is_empty
  let push = Storage.prepend
  let pop = Storage.take_first
end

module TailStack : STACK = struct
  type 'a t = 'a Storage.t
  let empty = Storage.empty
  let is_empty = Storage.is_empty
  let push = Storage.append
  let pop = Storage.take_last
end

Storage содержит общую механику. HeadStack и TailStack задают два набора операций над ней. Это два способа реализации контракта, а не две копии всего приложения.

У первого push и pop занимают O(1). У второго обе операции занимают O(n) и создают новые части списка; take_last также использует O(n) стека вызовов. Вариант с концом нужен здесь для сравнения семантики, не как рекомендация по хранению больших историй.

Под капотом типы одинаковы. Но аннотации : STACK скрывают это равенство независимо для каждого модуля. Снаружи нельзя взять HeadStack.t и передать в TailStack.pop: одинаковая структура реализации ещё не означает разрешённое смешивание API.

Функтор: клиент, которому ещё не выбрали зависимость

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

(* 2. Клиент параметризован целым модулем. *)
module MakeDrain (S : STACK) = struct
  let of_list values =
    List.fold_left (fun stack value -> S.push value stack) S.empty values

  let to_list stack =
    let rec loop acc current =
      match S.pop current with
      | None -> List.rev acc
      | Some (value, rest) -> loop (value :: acc) rest
    in
    loop [] stack
end

module HeadDrain = MakeDrain (HeadStack)
module TailDrain = MakeDrain (TailStack)

let show values = String.concat "," (List.map string_of_int values)

let () =
  let head = HeadDrain.of_list [10; 20] in
  let tail = TailDrain.of_list [10; 20] in
  Printf.printf "head=%s; tail=%s\n"
    (show (HeadDrain.to_list head))
    (show (TailDrain.to_list tail))

Ожидаемая строка: head=20,10; tail=20,10.

MakeDrain называют функтором модулей. Он получает S с типом STACK и создаёт модуль с алгоритмами, использующими эту зависимость.

Здесь слово «функтор» не означает категориальный Functor с операцией map или fmap. Это разные понятия. В данном уроке речь только о параметризации модулей OCaml.

Проверь путь сборки:

1. STACK описывает, что требуется алгоритму.
2. HeadStack и TailStack задают варианты зависимости.
3. MakeDrain пишет алгоритм без выбора варианта.
4. Две строки применения функтора делают выбор явно.

В теле MakeDrain нет ссылки на Storage. Поэтому оно не может тайком прочитать список или выбрать нужный конец. Правило подстановки работает через контракт, а не через имя файла.

Связь типов никуда не исчезла

В примере у результата функтора нет скрывающей аннотации. Выведенный тип HeadDrain.of_list возвращает HeadStack.t, а HeadDrain.to_list принимает его. Связь с параметром сохранилась.

Если ты явно задашь возвращаемому модулю сигнатуру с абстрактным t, нужную связь надо сохранить через with type, как в предыдущем уроке. Иначе клиент увидит новый непрозрачный тип и не сможет передавать значения между API зависимости и результатом функтора.

Этот пример намеренно не компилируется:

let mixed = TailDrain.to_list (HeadDrain.of_list [10; 20])

Один общий контракт не сообщает, что значения разных реализаций взаимозаменяемы. Он сообщает, что каждая реализация согласует свои операции со своим типом.

Один набор проверок для обеих реализаций

Функтор можно использовать и для проверок контракта. Он не докажет все законы, но позволит не дублировать выбранные случаи:

(* 3. Одни проверки, две зависимости. *)
module CheckStack (S : STACK) = struct
  module D = MakeDrain (S)

  let run () =
    assert (S.is_empty S.empty);
    assert (S.pop S.empty = None);
    let original = D.of_list [1; 2; 3] in
    match S.pop (S.push 99 original) with
    | None -> failwith "push must create a nonempty stack"
    | Some (value, rest) ->
        assert (value = 99);
        assert (D.to_list rest = [3; 2; 1]);
        assert (D.to_list original = [3; 2; 1])
end

module CheckHead = CheckStack (HeadStack)
module CheckTail = CheckStack (TailStack)

let () =
  CheckHead.run ();
  CheckTail.run ();
  print_endline "both contracts: ok"

Ожидаемая строка: both contracts: ok. Эти проверки нужно запускать без отключения assert.

Код проверяет пустое значение, порядок извлечения и сохранение старой версии на конкретной последовательности. Он не сравнивает внутренние списки. Одинаковое поведение на этих входах не отменяет различий в стоимости и не доказывает эквивалентность на всех входах.