CODEWITHSUNDEEP
ocaml
Tim
Tim

Reputation: 99606

How to understand a type definition?

type 'a tree = Empty | Node of 'a * 'a tree * 'a tree;;

Is it a type definition, where a is a type parameter, and tree is the type name?

In Node of, is Node a built-in type of OCaml? What does of mean?

Thanks.

Upvotes: 2

Views: 683

Answers (2)

Étienne Millon
Étienne Millon

Reputation: 3028

There are several kinds of type definitions:

Definition of a new sum type

From that type definition:

type 'a tree = Empty | Node of 'a * 'a tree * 'a tree;;

Here are roughly the "facts" that the OCaml compiler knows about based on it:

  • tree is a unary type constructor. That means that for any type t, t tree is a type as well (example: int tree).
  • Empty is a 0-ary constructor for 'a tree. That means that Empty has type t tree for any t.
  • Node is a 3-ary constructor. Here this means that if a has type t, b has type t tree, and c has type t tree, then Node (a, b, c)has typet tree(note: that's the samet`)
  • those are the only two ways to have a value of type t tree. That means that you can use pattern matching (match ... with | Empty -> ... | Node (a, b, c) -> ...).

Definition of a type alias

A definition can also be something that looks like:

type t = existing_type

In that case, t is just a new neame for the existing_type.

For example:

type 'a pp = Format.formatter -> 'a -> unit

This means that something that is a int pp has type Format.formatter -> int -> unit.

This is the type of a function that takes a formatter and an integer and returns unit. Such as :

type 'a pp = Format.formatter -> 'a -> unit

module M : sig
  val pp_int : int pp
end = struct
  let pp_int fmt n = Format.fprintf fmt "%d" n
end

Upvotes: 1

badcook
badcook

Reputation: 3739

Yes 'a is a type parameter and tree is a type name (these are usually called variants in OCaml). This is reversed order from most other languages. Node is a constructor (called tag in OCaml) and of is just a keyword in OCaml to specify the types of the constructor arguments. Node is not a built-in type of OCaml (it is not even a type, but rather, as a I said, a constructor).

Hence Node (5, Empty, Node (6, Empty, Empty)) is something of type int tree (something like Tree<Int> in Java).

It may make more sense if you start with a simpler variant.

type shape = Square of int | Rectangle of int * int

Shape and Rectangle are tags (again constructors) that I have just made up that allow me to construct values of type shape (in this case I've chosen to have Shape take only one argument because only length is needed to specify a square, whereas Rectangles need both length and width). Nothing ever has a type of Shape or Rectangle, but things can have a type of shape.

One way to read that line in English is "I have defined a type called shape. A shape is either a Square of a single integer, or a Rectangle of two integers."

Now maybe for some reason I also want to label my shapes.

type 'label labelledshape = LabelledSquare of 'label * int | LabelledRectangle of 'label * int * int

The quote ' distinguishes that label is not a type (such as int), but is rather a variable. This allows me to write something like LabelledSquare ("a label for a square", 5) which is of type string labelledshape

Note that although this allows for polymorphism, these are not what is known as "polymorphic variants" in OCaml. I will not talk about that here, rather I'll just recommend either looking at OCaml documentation or browsing Stack Overflow for more details on that.

Upvotes: 4

Related Questions