Сопоставление с образцом для алгебраических типов данных

Есть несколько альтернатив. Во-первых, вы можете использовать модуль Obj для прямого сравнения представлений (хотя это явно зависит от реализации):

type t = A of int | B of float | C of string

let compare_t a b =
  match (a, b) with
  | A x, A y -> compare x y
  | B x, B y -> compare x y
  | C x, C y -> compare x y
  | _ -> compare (Obj.tag (Obj.repr a)) (Obj.tag (Obj.repr b))

Если вы хотите, чтобы он был более переносимым, вы можете написать (или сгенерировать) функцию, которая дает вам числовой тег. Как оказалось, текущий компилятор OCaml, кажется, ищет это и, по-видимому, способен исключить вызов основной функции.

let tag_of_t = function
  | A _ -> 0
  | B _ -> 1
  | C _ -> 2

let compare_t a b =
  match (a, b) with
  | A x, A y -> compare x y
  | B x, B y -> compare x y
  | C x, C y -> compare x y
  | _ -> compare (tag_of_t a) (tag_of_t b)

Вам все равно придется иметь дело с линейным ростом, но не с квадратичным.

Вы можете использовать ppx_deriving для создания этой функции.

Следующее создаст функцию compare : t -> t -> int, которая делает правильные вещи:

type t = A of int | B of float | C of string [@@deriving ord]

Если вам интересно или вы не можете использовать ppx_deriving, вот сгенерированный код, который использует стратегию, аналогичную решению Реймера.

% utop -require ppx_deriving.std -dsource
utop # type t = A of int | B of float | C of string [@@deriving ord];;
type t = | A of int | B of float | C of string [@@deriving ord]
let rec (compare : t -> t -> Ppx_deriving_runtime.int) =
  ((let open! Ppx_deriving_runtime in
      fun lhs  ->
        fun rhs  ->
          match (lhs, rhs) with
          | (A lhs0,A rhs0) -> Pervasives.compare lhs0 rhs0
          | (B lhs0,B rhs0) -> Pervasives.compare lhs0 rhs0
          | (C lhs0,C rhs0) -> Pervasives.compare lhs0 rhs0
          | _ ->
              let to_int = function
              | A _ -> 0
              | B _ -> 1
              | C _ -> 2
              in
              Pervasives.compare (to_int lhs) (to_int rhs))
  [@ocaml.warning "-A"]) ;;
type t = A of int | B of float | C of string
val compare : t -> t -> int = <fun>

В случае, если вам нужно сравнение только для использования функтора Map.Make, т. е. вас не волнует конкретный порядок, вы можете использовать встроенное сравнение. В частности, это работает для типа, указанного в вашем примере:

let compare t1 t2 = compare t1 t2

Если некоторые, но не все ваши случаи выходят за рамки встроенного сравнения (например, они относятся к типу функции), вы все равно можете обрабатывать оставшиеся случаи с размером кода O(1). Пример:

type t = A of int -> int | B of float | C of string

let compare t1 t2 = match t1,t2 with
| A f1, A f2 -> ...
| A _, _ -> -1
| _, A _ -> 1
| _, _ -> compare t1 t2

Если все это не удается, все еще есть возможность выполнить метапрограммирование (например, через camlp5), чтобы автоматически создать длинное сравнение. Я делал это в прошлом, потому что в противном случае порядок, например.

type three = Zero | One | Two

не указан (Pervasives.compare указывается только как некоторый общий порядок), и я хотел естественный порядок.