如何在两组不同（但重叠）的总和类型之间进行联合

Question

我正在为编译器实现 generate First and Follow set algorithms。

这是 First Set 和 Follow Set 元素的类型定义：

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

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

如您所见，"Terminal" 是两者之间的重叠变体。

我希望能够采用 FollowSet 并与 FirstSet 合并，然后减去 FirstSet 的 Epsilon，这样结果仍然是 FollowSet。

当然，"straightforward"的解决办法是写一个函数将FirstSet转换为FollowSet，然后使用FollowSet.union。理想情况下，我将能够不重新实现集合操作。我很好奇 OCaml 类型系统中是否有什么东西或者可能有更好的设计来解决这个问题。

Polymorphic Variants 会是我要找的吗？

以下是我定义集合的方式：


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

是的，多态变体有帮助。他们正是为了这样的任务。这是一个简单的例子：

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 *)

您可以通读手册了解更多详情。主要缺点是你会得到更冗长的类型，如上所示。

如何在两组不同（但重叠）的总和类型之间进行联合

How to do a set union between two sets of different (but overlapping) sum types

ocaml