CODEWITHSUNDEEP
ocaml
user1252446
user1252446

Reputation:

OCaml syntax: what does type 'a t mean?

This is about type definition in OCaml, I find the following syntax puzzling: 

type 'a t

What does it mean in plain English?

Upvotes: 5

Views: 1941

Answers (2)

ivg
ivg

Reputation: 35280

Since OP has an experience in C++ language, I think the following explanation might be useful. A type declaration of the form:

type 'a t

is close to the C++

template <typename a> class t;

For example, 'a list is a generic list, and 'a is a type of an element. For concise, we use a single ', instead of template <typename _> construct. In the OCaml parlance, we use term "parametric polymorphism", instead of "generic programming". And instead of a word template, we say a type constructor. The latter has an interesting consequence. Like in C++ a template instantiation creates a new instances of types, in OCaml concertizing a type variable of a polymorphic type creates a new type, e.g., int list, float list (c.f., list<int>, float<list>). So, one can view type constructor 'a list as an unary function on a type level, it accepts a type, and creates a type. It is possible to have nary type constructors, e.g., type ('key, 'value) hashtbl is a binary type constructor, that creates a type for a given key and value pair. Moreover, we can see a non parametric types as a nullary type constructors, so int constructs the type int.

P.S. F# language, a descendant of OCaml, allows to write in both forms: int t and t<int>

P.P.S. To prevent a possible confusion, I would like to state, that although templates and parametric types are trying to solve the same problems, they still have a few differences. Templates are typed after the instantiation, parametric types before. So parametric type 'a t is defined for all 'a. If you want to create a type where a type variable is not universally quantified, you can use another mechanism - functors. They are also very close to templates, but they accept a type plus type requirements, a concept in C++ parlance. The concepts are reified in module types in OCaml, and thus a functor is actually a function on a module level, as it accepts a module and produces a module.

Upvotes: 7

PatJ
PatJ

Reputation: 6140

This a parametric type declaration.

A type declaration allows you to declare a new datatype:

type my_type = int * string

let x : my_type = (42,"Sorry for the inconvenience")

Sometimes however, you want a type to be parametric, meaning it takes another type as argument:

type 'a container = 'a * string * 'a

let x : int container = (0, "hello", 1)
let y : string container = ("stack", "over", "flow")

Now in that case, there is no equal after your type declaration. The meaning of that depends whether if it is in a module's structure (like, on top of a .ml file) or in a signature (e.g. in a .mli)

If it is in a structure, it declares a type with no value inside. Which is as useful as an empty set (sometimes it is, but not much). However, if it is in a signature, it means "there exists a parametric definition somewhere, but it is not visible from here".

Suppose there are those two files a.ml and a.mli:

(* a.ml *)
type 'a t = Nil | Cons of 'a * 'a t

let empty = Nil
let add x l = Cons (x,l)

(* and so on... *)

(* a.mli *)

type 'a t

val empty : 'a t
val add : 'a -> 'a t -> 'at

(* and so on... *)

If in the rest of your program you want to manipulate the A.t type, you'll be able to do so only through the empty and add and other defined functions, but not through directly using Nil and Cons.

Upvotes: 6

Related Questions