Programming in OCaml

The Basics

This section covers some basics first, and then gives a structured introduction of programming in OCaml

The Simplest Program

OCaml files are written with a .ml extension. An OCaml file consists of

For example:

open Printf

let message = "Hello world";;
(printf "%s\n" message)

The first line includes the built-in library for printing, which provides functions similar to fprintf and printf from stdlib in C. The next two lines define a constant named message, and then call the printf function with a format string (where %s means “format as string”), and the constant message we defined on the line before.

Put this in a file called hello.ml and run it with:

$ ocaml hello.ml
Hello world

Most of our programs will be more complex than this, and much of the infrastructure for the “main” function will be provided, but it’s useful to see the simplest case first.

Defining and Calling Functions

Here is an example of a function definition in OCaml:

let max (n : int) (m : int) : int =
  if n > m then n else m;;

It uses the keyword let followed by the name of the function (here, max). Next comes the parameter list. Each parameter is enclosed in parentheses, and has the parameter’s name, then a colon, then its type. So n and m are the parameters of max, and they are both type int. The final colon followed by int describes the return type of the function. Then there is an = sign, followed by the function body.

This declaration is similar to the following in C++ or Java:

int max(int n, int m) {
  if(n > m) { return n; }
  else { return m; }
}

One notable difference is that the OCaml function does not have any return statements. We’ll talk about how to think about the “return” value of a function without return statements next. It’s also important to note that the declaration in OCaml ends in ;;. This is a required syntactic convention for all top-level declarations in OCaml.

The syntax for function calls in OCaml is different than you may be used to. Instead of writing

some_function(arg1, arg2, ...)

// for example

max(4, 5)

as we would in C++ or Python, in OCaml we write

(some_function arg1 arg2 ...)

// for example

(max 4 5)

(The surrounding parentheses can be omitted in some cases, but it’s always safe to include them to be clear.)

There is a useful model to think about what happens when we call a function in OCaml. Rather than thinking about a call to max creating a new stack frame, let’s think about what happens if we substitute the provided argument values for the parameters in the body of max, and continue by evaluating the function body. This notion of substitution is “just” a useful model; everything you know about stacks and memory diagrams is still true. But substitution is a very helpful model for reasoning in the style of programming we’ll do.

So, for example, the call to max below takes a step to the substituted form:

   (max 4 5)

=> if 4 > 5 then 4 else 5

Then we can think about how the if expression takes steps. First, it evaluates the conditional part, and based on that value being true or false, it evaluates one or the other branch:

   if 4 > 5 then 4 else 5

=> if false then 4 else 5

=> 5

From this sequence of steps, we say that (max 4 5) evaluates to 5. This gives us a way to think about evaluation that does not require a notion of a return statement.

Recursive Functions

OCaml distinguishes between functions that can contain recursive calls and functions that cannot. We saw the latter kind above in max which simply used the let keyword. We can define a recursive function by using let rec:

let rec factorial (n : int) : int =
  if n <= 1 then 1
  else n * (factorial (n - 1));;

The substitution-based rules are a little more interesting when thinking about evaluating a call to factorial:

  (factorial 3)

=> (if 3 <= 1 then 1 else 3 * (factorial (3 - 1)))

=> (if false then 1 else 3 * (factorial (3 - 1)))

=> (3 * (factorial (3 - 1)))

=> (3 * (factorial 2))

=> (3 * (if 2 <= 1 then 1 else 2 * (factorial (2 - 1)))

...

=> (3 * (2 * (factorial (2 - 1))))

...

=> (3 * (2 * 1))

=> 6

Here, we can see the chained multiplications “stack up” during the recursive calls. Writing this in a substitution-based style makes it easy to track where the return values of function calls end up.

Datatypes

This section shows how to create new datatypes in OCaml, and program with them.

Binary Trees with type

Let us start with a binary tree datatype. We know we will need to represent a binary tree node somehow, which has a value and two children. For now, let us say the value has to be a string. In OCaml, we can define such a node using the keyword type:

type btnode =
  | Leaf
  | Node of string * btnode * btnode

Translated into English, this reads:

A binary tree node is either a leaf of the tree, which has no fields, or a node, which has three fields: a string, a binary tree node, and another binary tree node.

This defines what we call constructors for Leaf and Node, which we can use to construct trees. Here are a few examples of trees and their corresponding btnode value:

    "a"       Node("a",
   /   \        Node("b", Leaf, Leaf), Node("c", Leaf, Leaf))
"b"     "c"


    "a"       Node("a",
   /            Node("b", Leaf, Leaf), Leaf)
"b"


    "a"       Node("a",
   /            Node("b",
"b"               Leaf, Node("c", Leaf, Leaf)), Leaf)
   \
    "c"

Each position with no child corresponds to a Leaf, and the others correspond to uses of Node. We call Leaf and Node variants of the btnode type. ( A Leaf is used here where you may have seen NULL or null in a C++ or Java implementation of a binary tree.)

Manipulating Data with match

The next question is how to work with these values. For example, how can we construct an in-order concatenation of the strings in a btnode as we have defined it? That is, how do we fill in this function:

let rec inorder_str (btn : btnode) : string =
  ...

The next feature we need to introduce is match, which allows us to examine which variant of a type a particular value has, and extract the values of its fields. Here are some examples:

let m1 = match Leaf with
  | Leaf -> true
  | Node(s, left, right) -> false;;

(* m1 is true *)

let m2 = match Leaf with
  | Leaf -> 44
  | Node(s, left, right) -> 99;;

(* m2 is 44 *)

let m3 = match Node("a", Leaf, Leaf) with
  | Leaf -> "z"
  | Node(s, left, right) -> s;;

(* m3 is "a" *)

let m4 = match Node("a", Node("b", Leaf, Leaf), Leaf) with
  | Leaf -> "z"
  | Node(s, left, right) ->
    match left with
      | Leaf -> "y"
      | Node(s2, left2, right2) -> s2;;

(* m4 is "b" *)

From these examples, we can see how match must work. It inspects the value after the match keyword, and selects the branch that corresponds to the variant of that value. Then it extracts the fields from the value, and substitutes them for the names given in the branch. Let us use the m4 example to make that concrete:

  match Node("a", Node("b", Leaf, Leaf), Leaf) with
    | Leaf -> "z"
    | Node(s, left, right) ->
      match left with
        | Leaf -> "y"
        | Node(s2, left2, right2) -> s2

(* substitute Node("b", Leaf, Leaf) for left *)

=> match Node("b", Leaf, Leaf) with
     | Leaf -> "y"
     | Node(s2, left2, right2) -> s2

(* substitute "b" for s2 *)

=> "b"

With match available, we can now fill in the body for inorder_str. We can start by writing out a skeleton of the match structure for a btnode, as most functions over btnodes will need to match on the node to decide what to do.

let rec inorder_str (bt : btnode) : string =
  match bt with
    | Leaf -> ...
    | Node(s, left, right) -> ...

Now we can ask what the inorder traversal should yield in the case of a leaf of the tree (or an empty tree altogether). In this case, that ought to be an empty string. So the Leaf case should be filled in with "". How about for Nodes? We know an inorder traversal should have the elements to the left in order, then the current node, then the elements to the right. We can get the elements to either side via a recursive call, and then we just need one more piece of information, which is that ^ is the operator for concatenating strings in OCaml:

let rec inorder_str (bt : btnode) : string =
  match bt with
    | Leaf -> ""
    | Node(s, left, right) ->
      (inorder_str left) ^ s ^ (inorder_str right)

Lists and Parametric Polymorphism

Linked Lists, By Hand

Since we have seen binary trees, it’s natural to think about a similar definition for the nodes of a linked list. One OCaml datatype we could write is:

type llist =
  | Empty
  | Link of string * llist

That is, a list is either Empty (the end of the list), or a Link of a string onto another list. Of course, this would require that we write additional datatype declarations for lists of numbers, lists of booleans, lists of binary trees, and so on, if we needed those shapes of data. The natural solution is to make the datatype generic over the kind of data it uses. OCaml lets us do this by defining datatypes with type variables that can be filled with any type. Type variables are written with a leading ' character:

type 'a llist =
  | Empty
  | Link of 'a * 'a llist

The types of the fields in Link have changed with this addition. The first field can now hold a value of the list’s type, and the second must hold a llist that contains elements of that type as well. That is, this describes a homogeneous linked list, where all elements will have the same type.

Let us say we want to write a function sum that takes a llist of numbers and adds them up. We now need to describe its type in terms of the contents, which will be an int:

let rec sum (l : int llist) : int =
  match l with
    | Empty -> 0
    | Link(first, rest) -> first + (sum rest)

When we construct llists, we do not need to provide any extra type information – OCaml figures it out for us. For example, we can write:

let l1 = Link(1, Empty);;
let l2 = Link("a", Empty);;

Here, l1 will have type int llist, and l2 will have type string llist.

Linked Lists, Built-in

It turns out that our definition of llist above is important enough that a version of it is built into OCaml, just with slightly different names and syntax. The built-in equivalent of Empty is written [], and Link(first, rest) is written first::rest. The syntax [a;b;c] is shorthand for a::b::c::[]. The type of built-in lists is 'a list, which can be specialized for any list contents. For example, we could rewrite sum above as:

let rec sum2 (l : int list) : int =
  match l with
    | [] -> 0
    | first::rest -> first + (sum2 rest)

And we could test it by creating tests with t_int:

(* these would go in the suite list *)
t_int "sum2_empty" (sum2 []) 0;
t_int "sum2_single" (sum2 [5]) 5;
t_int "sum2_longer" (sum2 [3; 4; 5]);
t_int "sum2_longer2" (sum2 (3::4::5::[]));

Note that the last two tests mean the same thing; they are just different ways of writing the same list containing 3, 4, and 5.

Since lists are quite a fundamental structure, we will end up using them frequently; handy functions to use with lists are here.

Tuples

There are many times in programs where we wish to return more than one value. For example, when returning a pair of key and value from a hash-table data structure, when returning an average and its standard deviation, or when representing a two (or three)-dimensional point, to name a few.

OCaml has a built-in way of handling these cases called tuples (many other languages do as well). To create a tuple, we enclose two or more values in parentheses:

let tup = (1, "a", []);;

To access the values in a tuple, we can use a special kind of let binding, where we give names to the positions of a tuple value:

let tup = (1, "a", []);;
let (one, a, empty_list) = tup;
(*
  one is 1
  a is "a"
  empty_list is []
*)

Since pairs—tuples of exactly two elements—are quite common, there are also two built-in functions, fst and snd, that get the first and second component of a two-element tuple, respectively.

The type of a tuple is written with * characters separating the components’ types, and surrounded by parentheses.

let increment_snd (t : (string * int)) : (string * int) =
  (fst t, 1 + (snd t));;

(increment_snd ("a", 5)) (* returns the pair ("a", 6) *)

option

A common way of handling failure is raising exceptions with failwith. This works well when an operation is truly nonsensical. However, it forces programs to use a different class of features— exceptions and exception handlers—to handle failing behaviors. Sometimes, the failure of an operation is a reasonable outcome, and having a way to report a failure, or the absence of an answer, with a normal value rather than an exception is quite useful.

Consider the problem of finding and returning the first element in a list that matches a particular predicate:

let rec find (l : 'a list) (pred : 'a -> bool) : 'a =
  match l with
    | [] -> failwith "Not found"
    | x::xs -> if pred x then x else find xs pred;;

(find [1;2;3] (fun n -> n > 4);; (* raises an error *)
(find [1;2;3] (fun n -> n > 2);; (* returns 3 *)

When the element is not found, we cannot return a value of type 'a, because the algorithm hasn’t found one. It seems we have to throw an error, as there is nothing left for us to do. This certainly limits the utility of find, which now needs a companion contains if is to be useful on lists that are not already known to have a matching element.

It would be convenient if we had a value that represented that there is no appropriate value to return in the empty case. Similarly, it would be useful to have the counterpart, a representation of being able to provide some appropriate value. OCaml provides just such a datatype, called option, which is built-in. If we wrote the definition ourselves, it would look like:

type 'a option =
  | None
  | Some of 'a

That is, an option is either None, which we can use to indicate failure or the lack of an appropriate value, or Some, which contains a single field that is a value of the option’s type. To write find using option, we would write:

let rec find_opt (l : 'a list) (pred : 'a -> bool) : 'a option =
  match l with
    | [] -> None
    | x::xs -> if pred x then Some(x) else find_opt xs pred;;

(find_opt [1;2;3] (fun n -> n > 4);; (* returns None *)
(find_opt [1;2;3] (fun n -> n > 2);; (* returns Some(3) *)

Now a program that calls find, rather than using an exception handler to manage the not found case, can simply match on the option that is returned to decide what to do.

Note that options aren’t always better than exceptions, as sometimes it’s difficult for the caller to know what to do when None is returned. But in many cases, when “failure” is something that the caller can reasonably react to, returning an option is a much more natural choice.