Ocaml Variant Types

Question

OCaml types have always really confused me no matter what tutorials/manuals I read. I need to define a type, let's say test, that does contains the following forms:

a type ('a, 'b) test that has one of the forms: Empty, T t, N n, Seq [x1...xn]

I know how to do the first 3, but I have absolutely no idea how to define the last form. This is what I have:

type ('nonterm, 'term) test =
   | Empty
   | T of 'term
   | N of 'nonterm
   | ????

For seq, I need to match the instances of subexpressions x1 to xn. If x = 0, then this is empty. Can anybody please help me? Thanks in advance.

Answer 1

Are the subexpressions of Seq also tests? If so, you can use a list:

type ('nonterm, 'term) test =
  | Empty
  | T of 'term
  | N of 'nonterm
  | Seq of ('nonterm, 'term) test list

Lists can, of course, be empty.

Answer 2

This is an answer to your comment to Michael E:

OCaml variants are composed of constructors with optional arguments. In the case of Michael's answer, the constructors are: Empty, T, N and Seq. Empty takes no arguments, T takes a generic type called 'term and N takes a generic type called 'nonterm (I'll get to Seq in a second). The variant has the type ('nonterm, 'term) test. Let's say you want a list of elements of type ('nonterm, 'term) test:

# [Empty; Empty];;
- : ('a, 'b) test list = [Empty; Empty] 

You'll notice that the type is ('a, 'b) test list. (OCaml replaced nonterm with a and term with b, but you don't need to worry about that too much).

Now we can see that | Seq of ('nonterm, 'term) test list is a constructor called Seq that takes a list of elements of type ('nonterm, 'term) test as an argument. Now we can do this:

# Seq [Empty;Empty];;
- : ('a, 'b) test = Seq [Empty; Empty]