Important Types in OCaml

Lists

In OCaml, a list is a sequence of values of same type and is implemented as singly-linked lists. Here are some important operations for operating lists.

1
2
3
4
5
6
7
8
9
10
11

(* Empty list *) []
(* construct a new list by appending [elem] in front of the [lst] *)
elem :: lst (* this operator is right-associative *)
(* create a list of soe values *)
[e1; e2; e3; ...; en]

(* Pattern Matching on Lists *)
let rec sum l =
  match l with
    | [] -> 0
    | x :: xs -> x + sum xs

Lists in OCaml are immutable, thus “mutating” a list in OCaml is equivalent to creating a new list. The compiler will intervene to make the memory usage efficient.

Moreover, when we have to pattern-match on the last argument, we can use the function syntactic sugar:

1
2
3

let rec sum lst = function (* match lst with *)
  | [] -> 0
  | h :: t -> h + sum t

Variants

A variant is similar to enum in other languages, representing a value that is one of the several options.

1
2

type day = Sun | Mon | Tue | Wed | Thu | Fri | Sat
let d = Tue

If two variants are defined with overlapping constructor names, then it always be the type of later-defined one.

1
2
3

type t1 = C | D
type t2 = D | E
let x = D (* x : t2 = D *)

Algebraic Data Types

variants can also carry data. Grammar is <constructor> of <type/record>, e.g.

1
2
3
4
5

type point = float * float
type shape =
  | Point of point
  | Circle of point * float (* center and radius *)
  | Rect of point * point (* lower-left and upper-right corners *)

We can pattern match on ADTs

1
2
3
4
5
6
7
8
9
10
11
12

let area = function
  | Point _ -> 0.0
  | Circle (_, r) -> Float.pi *. (r ** 2.0)
  | Rect ((x1, y1), (x2, y2)) ->
      let w = x2 -. x1 in
      let h = y2 -. y1 in
      w *. h

let center = function
  | Point p -> p
  | Circle (p, _) -> p
  | Rect ((x1, y1), (x2, y2)) -> ((x2 +. x1) /. 2.0, (y2 +. y1) /. 2.0)

Recursive Variants/Records

Variant types may mention themselves inside their own body. And can be mutually recursive with and keyword.

1
2
3
4

type intlist = Nil | Cons of int * intlist

type node = {value : int; next : mylist}
  and mylist = Nil | Node of node

But there’s constraint on mutually recursive variants: any such mutual recursion must involve at least one variant or record type that the recursion “goes through”.

1
2
3
4

(* This is prohibited *)
type t = u and u = t
(* But this is OK *)
type t = U of u and u = T of t

Records

A record is a composite of other types of data, each of which is named. OCaml records are much like structs in C.

1
2

type ptype = TNormal | TFire | TWater
type mon = {name : string; hp : int; ptype : ptype}

To build a value of a record type, we use {} syntax. To access fields, we use . notation.

1
2

let c = {name = "Charmander"; hp = 39; ptype = TFire};;
c.hp

We can also pattern match on records, if names are not provided, OCaml will by default use field names as bindings

1
2

match c with {name = n; hp = h; ptype = t} -> h
match c with {name; hp; ptype} -> hp

Sometimes, we want to create a new copy of record from some old records, we can use with syntax. After the with syntax, we do not need to bind new values to all fields, only part of fields are required.

1

{e with f1 = e1; ...; fn = en}

Tuples

Just like tuples in other languages. We can pattern match on tuples

1

match (1, 2, 3) with (x, y, z) -> x + y + z

Note that, if a tuple is of type (A, B, C), then its type annotation is A * B * C.

Options

Similar to Maybe in Haskell and Option<T> in Rust.

1
2
3
4

let extract o =
  match o with
  | Some i -> string_of_int i
  | None -> ""

Like list, we call option a type constructor: given a type, it produces a new type; but, it is not itself a type. So for any type t, we can write t option as a type. But option all by itself cannot be used as a type. Values of type t option might contain a value of type t, or they might contain nothing. None has type 'a option because it’s unconstrained what the type is of the thing inside — as there isn’t anything inside.

Type Synonyms

1
2
3
4
5
6
7
8
9
10
11
12

type point = float * float
type vector = float list
type matrix = float list list

(* examples *)
let get_x = fun (x, _) -> x

let p1 : point = (1., 2.)
let p2 : float * float = (1., 3.)

let a = get_x p1
let b = get_x p2

Parameterized Types

1

type 'a mylist = Nil | Cons of 'a * 'a mylist

1
2
3

type ('a, 'b) pair = {first : 'a; second : 'b}
let x = {first = 2; second = "hello"}
(* val x : (int, string) pair = {first = 2; second = "hello"} *)

Anonymous Variants

If sometimes, we just want to define a variant for the return value, e.g.

1
2
3
4
5
6

type fin_or_inf = Finite of int | Infinity

let f = function
  | 0 -> Infinity
  | 1 -> Finite 1
  | n -> Finite (-n)

Instead of always explicit defining such a variant, we can use polymorphic variants. They don’t have a name, no need for declare-before-use, and starts with a backquote. So we can rewrite the above as:

1
2
3
4
5
6

let f = function
  | 0 -> `Infinity
  | 1 -> `Finite 1
  | n -> `Finite (-n)

(* val f : int -> [> `Finite of int | `Infinity ] = <fun> *)

This type says that f either returns `Finite n for some n : int or `Infinity. The square brackets do not denote a list, but rather a set of possible constructors. The > sign means that any code that pattern matches against a value of that type must at least handle the constructors `Finite and `Infinity, and possibly more. For example, we could write:

1
2
3
4

match f 3 with
  | `NegInfinity -> "negative infinity"
  | `Finite n -> "finite"
  | `Infinity -> "infinite"