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

user_10390454 0
Viewed 67

I am implementing the generate First and Follow set algorithms for compilers.

Here is the type definition for First Set and Follow Set elements:

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

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

As you can see, the "Terminal" is the overlapping variant between the two.

I would like to be able to take a FollowSet and union with a FirstSet, then MINUS FirstSet's Epsilon, such that the result is still a FollowSet.

Of course, the "straightforward" solution is to write a function to convert the FirstSet to a FollowSet, then use FollowSet.union. Ideally, I would be able to NOT reimplement set operations. I am curious if there is something in the OCaml type system or perhaps a better design that addresses this.

Could Polymorphic Variants be what I am looking for?

Here's how I define the Sets:


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)
ocaml
1 Answers

Yes, polymorphic variants help. They are exactly for such task. Here's a simple example:

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

You can read through the manual for more details. The main drawback is you will get more verbose types, as shown above.

user_132481430
Related