Как сделать объединение множеств между двумя наборами разных (но перекрывающихся) типов сумм

Question

Я реализую алгоритмы генерации первого и следующего набора для компиляторов.

Вот определение типа для элементов первого набора и следующего набора:

type first_set_element =
  | Terminal of terminal
  | Epsilon [@@deriving show, sexp]

type follow_set_element =
  | Terminal of terminal
  | EndSymbol [@@deriving show, sexp]

Как вы можете видеть, «Терминал» является перекрывающим вариантом между этими двумя.

Я хотел бы иметь возможность взять FollowSet и объединиться с FirstSet, затем с MINIL FirstSet Epsilon, так что результат все еще a FollowSet.

Конечно, «простое» решение - написать функцию для преобразования FirstSet в FollowSet, а затем использовать FollowSet.union. В идеале я не смог бы переопределить операции над множествами. Мне любопытно, есть ли что-то в системе типов OCaml или, возможно, лучший дизайн, который решает эту проблему.

Может ли Polymorphi c Варианты быть тем, что я ищу?

Вот как я определяю Наборы:

module FirstSetElement = struct
  type t = first_set_element
  let compare a b = match (a, b) with
    | (Terminal(a), Terminal(b)) -> String.compare a b
    | (Terminal(_), Epsilon) -> 1
    | (Epsilon, Terminal(_)) -> -1
    | (Epsilon, Epsilon) -> 0
  let sexp_of_t t = sexp_of_first_set_element t
  let t_of_sexp t = first_set_element_of_sexp t
end

module FirstSet = Set.Make(FirstSetElement)

module FollowSetElement = struct
  type t = follow_set_element
  let compare a b = match (a, b) with
    | (Terminal(a), Terminal(b)) -> String.compare a b
    | (Terminal(_), EndSymbol) -> 1
    | (EndSymbol, Terminal(_)) -> -1
    | (EndSymbol, EndSymbol) -> 0
  let sexp_of_t t = sexp_of_follow_set_element t
  let t_of_sexp t = follow_set_element_of_sexp t
end

module FollowSet = Set.Make(FollowSetElement)

Answer 1

Да, полиморф c Варианты помогают. Они как раз для такой задачи. Вот простой пример:

type a =
  [ `A
  | `Shared of int ]

type b =
  [ `B
  | `Shared of int ]

let a = [ `A; `Shared 1 ]
(* a :- [> `A | `Shared of int ] list *)

let b = [ `B; `Shared 2 ]
(* b :- [> `B | `Shared of int ] list *)

let c = a @ b
(* c :- [> `A | `B | `Shared of int ] list *)

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