Type Inference

As the types we encounter get more complicated, you might ask yourself how OCaml is able to figure them out, given that we didn’t write down any explicit type information. 

OCaml determines the type of an expression using a technique called type inference, by which the type of an expression is inferred from the available type information about the components of that expression.

As an example, let’s walk through the process of inferring the type of sum_if_true:

1. OCaml requires that both branches of an if expression have the same type, so the expression

   if test first then first else 0

   requires that first must be the same type as 0, and so first must be of type int. Similarly, from

   if test second then second else 0

   we can infer that second has type int.

2. test is passed first as an argument. Since first has type int, the input type of test must be int.

3. test first is used as the condition in an if expression, so the return type of test must be bool.

4. The fact that + returns int implies that the return value of sum_if_true must be int.

Together, that nails down the types of all the variables, which determines the overall type of sum_if_true.

Over time, you’ll build a rough intuition for how the OCaml inference engine works, which makes it easier to reason through your programs. You can also make it easier to understand the types of a given expression by adding explicit type annotations. These annotations don’t change the behavior of an OCaml program, but they can serve as useful documentation, as well as catch unintended type changes. They can also be helpful in figuring out why a given piece of code fails to compile.

Here’s an annotated version of sum_if_true:

let sum_if_true (test : int -> bool) (x : int) (y : int) : int =
  (if test x then x else 0)
  + (if test y then y else 0);;
>val sum_if_true : (int -> bool) -> int -> int -> int = <fun>

In the above, we’ve marked every argument to the function with its type, with the final annotation indicating the type of the return value. Such type annotations can be placed on any expression in an OCaml program.

Inferring Generic Types

Sometimes, there isn’t enough information to fully determine the concrete type of a given value. Consider this function.. 

let first_if_true test x y =
  if test x then x else y;;
>val first_if_true : ('a -> bool) -> 'a -> 'a -> 'a = <fun>

first_if_true takes as its arguments a function test, and two values, x and y, where x is to be returned if test x evaluates to true, and y otherwise. So what’s the type of the x argument to first_if_true? There are no obvious clues such as arithmetic operators or literals to narrow it down. That makes it seem like first_if_true would work on values of any type.

Indeed, if we look at the type returned by the toplevel, we see that rather than choose a single concrete type, OCaml has introduced a type variable 'a to express that the type is generic. (You can tell it’s a type variable by the leading single quote mark.) In particular, the type of the test argument is ('a -> bool), which means that test is a one-argument function whose return value is bool and whose argument could be of any type 'a. But, whatever type 'a is, it has to be the same as the type of the other two arguments, x and y, and of the return value of first_if_true. This kind of genericity is called parametric polymorphism because it works by parameterizing the type in question with a type variable. It is very similar to generics in C# and Java.   

Because the type of first_if_true is generic, we can write this:

let long_string s = String.length s > 6;;
>val long_string : string -> bool = <fun>
first_if_true long_string "short" "loooooong";;
>- : string = "loooooong"

As well as this:

let big_number x = x > 3;;
>val big_number : int -> bool = <fun>
first_if_true big_number 4 3;;
>- : int = 4

Both long_string and big_number are functions, and each is passed to first_if_true with two other arguments of the appropriate type (strings in the first example, and integers in the second). But we can’t mix and match two different concrete types for 'a in the same use of first_if_true:

first_if_true big_number "short" "loooooong";;
>Line 1, characters 26-33:
>Error: This expression has type string but an expression was expected of type
>         int

In this example, big_number requires that 'a be instantiated as int, whereas "short" and "loooooong" require that 'a be instantiated as string, and they can’t both be right at the same time.

let add_potato x =
  x + "potato";;
>Line 2, characters 9-17:
>Error: This expression has type string but an expression was expected of type
>         int

let is_a_multiple x y =
  x % y = 0;;
>val is_a_multiple : int -> int -> bool = <fun>
is_a_multiple 8 2;;
>- : bool = true
is_a_multiple 8 0;;
>Exception:
>Invalid_argument "8 % 0 in core_int.ml: modulus should be positive".

Tuples

So far we’ve encountered a handful of basic types like int, float, and string, as well as function types like string -> int. But we haven’t yet talked about any data structures. We’ll start by looking at a particularly simple data structure, the tuple. A tuple is an ordered collection of values that can each be of a different type. You can create a tuple by joining values together with a comma.   

let a_tuple = (3,"three");;
>val a_tuple : int * string = (3, "three")
let another_tuple = (3,"four",5.);;
>val another_tuple : int * string * float = (3, "four", 5.)

For the mathematically inclined, * is used in the type t * s because that type corresponds to the set of all pairs containing one value of type t and one of type s. In other words, it’s the Cartesian product of the two types, which is why we use *, the symbol for product.

You can extract the components of a tuple using OCaml’s pattern-matching syntax, as shown below:

let (x,y) = a_tuple;;
>val x : int = 3
>val y : string = "three"

Here, the (x,y) on the left-hand side of the let binding is the pattern. This pattern lets us mint the new variables x and y, each bound to different components of the value being matched. These can now be used in subsequent expressions:

x + String.length y;;
>- : int = 8

Note that the same syntax is used both for constructing and for pattern matching on tuples.

Pattern matching can also show up in function arguments. Here’s a function for computing the distance between two points on the plane, where each point is represented as a pair of floats. The pattern-matching syntax lets us get at the values we need with a minimum of fuss:

let distance (x1,y1) (x2,y2) =
  Float.sqrt ((x1 -. x2) **. 2. +. (y1 -. y2) **. 2.);;
>val distance : float * float -> float * float -> float = <fun>

The **. operator used above is for raising a floating-point number to a power.

This is just a first taste of pattern matching. Pattern matching is a pervasive tool in OCaml, and as you’ll see, it has surprising power.

Lists

Where tuples let you combine a fixed number of items, potentially of different types, lists let you hold any number of items of the same type. Consider the following example: 

let languages = ["OCaml";"Perl";"C"];;
>val languages : string list = ["OCaml"; "Perl"; "C"]

Note that you can’t mix elements of different types in the same list, unlike tuples:

let numbers = [3;"four";5];;
>Line 1, characters 18-24:
>Error: This expression has type string but an expression was expected of type
>         int

List.length languages;;
>- : int = 3

List.map languages ~f:String.length;;
>- : int list = [5; 4; 1]

List.map ~f:String.length languages;;
>- : int list = [5; 4; 1]

"French" :: "Spanish" :: languages;;
>- : string list = ["French"; "Spanish"; "OCaml"; "Perl"; "C"]

languages;;
>- : string list = ["OCaml"; "Perl"; "C"]

["OCaml", "Perl", "C"];;
>- : (string * string * string) list = [("OCaml", "Perl", "C")]

1,2,3;;
>- : int * int * int = (1, 2, 3)

The bracket notation for lists is really just syntactic sugar for ::. Thus, the following declarations are all equivalent. Note that [] is used to represent the empty list and that :: is right-associative:

[1; 2; 3];;
>- : int list = [1; 2; 3]
1 :: (2 :: (3 :: []));;
>- : int list = [1; 2; 3]
1 :: 2 :: 3 :: [];;
>- : int list = [1; 2; 3]

The :: constructor can only be used for adding one element to the front of the list, with the list terminating at [], the empty list. There’s also a list concatenation operator, @, which can concatenate two lists:

[1;2;3] @ [4;5;6];;
>- : int list = [1; 2; 3; 4; 5; 6]

It’s important to remember that, unlike ::, this is not a constant-time operation. Concatenating two lists takes time proportional to the length of the first list.

let my_favorite_language (my_favorite :: the_rest) =
  my_favorite;;
>Lines 1-2, characters 26-16:
>Warning 8 [partial-match]: this pattern-matching is not exhaustive.
>Here is an example of a case that is not matched:
>[]
>val my_favorite_language : 'a list -> 'a = <fun>

my_favorite_language ["English";"Spanish";"French"];;
>- : string = "English"
my_favorite_language [];;
>Exception: Match_failure ("//toplevel//", 1, 26).

let my_favorite_language languages =
  match languages with
  | first :: the_rest -> first
  | [] -> "OCaml" (* A good default! *);;
>val my_favorite_language : string list -> string = <fun>
my_favorite_language ["English";"Spanish";"French"];;
>- : string = "English"
my_favorite_language [];;
>- : string = "OCaml"

let rec sum l =
  match l with
  | [] -> 0                   (* base case *)
  | hd :: tl -> hd + sum tl   (* inductive case *);;
>val sum : int list -> int = <fun>
sum [1;2;3];;
>- : int = 6

sum [1;2;3]
= 1 + sum [2;3]
= 1 + (2 + sum [3])
= 1 + (2 + (3 + sum []))
= 1 + (2 + (3 + 0))
= 1 + (2 + 3)
= 1 + 5
= 6

let rec remove_sequential_duplicates list =
  match list with
  | [] -> []
  | first :: second :: tl ->
    if first = second then
      remove_sequential_duplicates (second :: tl)
    else
      first :: remove_sequential_duplicates (second :: tl);;
>Lines 2-8, characters 5-61:
>Warning 8 [partial-match]: this pattern-matching is not exhaustive.
>Here is an example of a case that is not matched:
>_::[]
>val remove_sequential_duplicates : int list -> int list = <fun>

let rec remove_sequential_duplicates list =
  match list with
  | [] -> []
  | [x] -> [x]
  | first :: second :: tl ->
    if first = second then
      remove_sequential_duplicates (second :: tl)
    else
      first :: remove_sequential_duplicates (second :: tl);;
>val remove_sequential_duplicates : int list -> int list = <fun>
remove_sequential_duplicates [1;1;2;3;3;4;4;1;1;1];;
>- : int list = [1; 2; 3; 4; 1]

Options

Another common data structure in OCaml is the option. An option is used to express that a value might or might not be present. For example:  

let divide x y =
  if y = 0 then None else Some (x / y);;
>val divide : int -> int -> int option = <fun>

The function divide either returns None if the divisor is zero, or Some of the result of the division otherwise. Some and None are constructors that let you build optional values, just as :: and [] let you build lists. You can think of an option as a specialized list that can only have zero or one elements.

To examine the contents of an option, we use pattern matching, as we did with tuples and lists. Let’s see how this plays out in a small example. We’ll write a function that takes a filename, and returns a version of that filename with the file extension (the part after the dot) downcased. We’ll base this on the function String.rsplit2 to split the string based on the rightmost period found in the string. Note that String.rsplit2 has return type (string * string) option, returning None when no character was found to split on.

let downcase_extension filename =
  match String.rsplit2 filename ~on:'.' with
  | None -> filename
  | Some (base,ext) ->
    base ^ "." ^ String.lowercase ext;;
>val downcase_extension : string -> string = <fun>
List.map ~f:downcase_extension
  [ "Hello_World.TXT"; "Hello_World.txt"; "Hello_World" ];;
>- : string list = ["Hello_World.txt"; "Hello_World.txt"; "Hello_World"]

Note that we used the ^ operator for concatenating strings. The concatenation operator is provided as part of the Stdlib module, which is automatically opened in every OCaml program.

Options are important because they are the standard way in OCaml to encode a value that might not be there; there’s no such thing as a NullPointerException in OCaml. This is different from most other languages, including Java and C#, where most if not all data types are nullable, meaning that, whatever their type is, any given value also contains the possibility of being a null value. In such languages, null is lurking everywhere. 

In OCaml, however, missing values are explicit. A value of type string * string always contains two well-defined values of type string. If you want to allow, say, the first of those to be absent, then you need to change the type to string option * string. As we’ll see in Chapter 7, Error Handling, this explicitness allows the compiler to provide a great deal of help in making sure you’re correctly handling the possibility of missing data.

Base and Polymorphic Comparison

One other thing to notice was the fact that we opened Float.O in the definition of is_inside_scene_element. That allowed us to use the simple, un-dotted infix operators, but more importantly it brought the float comparison operators into scope. When using Base, the default comparison operators work only on integers, and you need to explicitly choose other comparison operators when you want them. OCaml also offers a special set of polymorphic comparison operators that can work on almost any type, but those are considered to be problematic, and so are hidden by default by Base. We’ll learn more about polymorphic compare in Chapter 3, Terser and Faster Patterns.

Arrays

Perhaps the simplest mutable data structure in OCaml is the array. Arrays in OCaml are very similar to arrays in other languages like C: indexing starts at 0, and accessing or modifying an array element is a constant-time operation. Arrays are more compact in terms of memory utilization than most other data structures in OCaml, including lists. Here’s an example:   

let numbers = [| 1; 2; 3; 4 |];;
>val numbers : int array = [|1; 2; 3; 4|]
numbers.(2) <- 4;;
>- : unit = ()
numbers;;
>- : int array = [|1; 2; 4; 4|]

The .(i) syntax is used to refer to an element of an array, and the <- syntax is for modification. Because the elements of the array are counted starting at zero, element numbers.(2) is the third element.

The unit type that we see in the preceding code is interesting in that it has only one possible value, written (). This means that a value of type unit doesn’t convey any information, and so is generally used as a placeholder. Thus, we use unit for the return value of an operation like setting a mutable field that communicates by side effect rather than by returning a value. It’s also used as the argument to functions that don’t require an input value. This is similar to the role that void plays in languages like C and Java.

Mutable Record Fields

The array is an important mutable data structure, but it’s not the only one. Records, which are immutable by default, can have some of their fields explicitly declared as mutable. Here’s an example of a mutable data structure for storing a running statistical summary of a collection of numbers.   

type running_sum =
  { mutable sum: float;
    mutable sum_sq: float; (* sum of squares *)
    mutable samples: int;
  }

The fields in running_sum are designed to be easy to extend incrementally, and sufficient to compute means and standard deviations, as shown in the following example.

let mean rsum = rsum.sum /. Float.of_int rsum.samples;;
>val mean : running_sum -> float = <fun>
let stdev rsum =
  Float.sqrt
    (rsum.sum_sq /. Float.of_int rsum.samples -. mean rsum **. 2.);;
>val stdev : running_sum -> float = <fun>

We also need functions to create and update running_sums:

let create () = { sum = 0.; sum_sq = 0.; samples = 0 };;
>val create : unit -> running_sum = <fun>
let update rsum x =
  rsum.samples <- rsum.samples + 1;
  rsum.sum     <- rsum.sum     +. x;
  rsum.sum_sq  <- rsum.sum_sq  +. x *. x;;
>val update : running_sum -> float -> unit = <fun>

create returns a running_sum corresponding to the empty set, and update rsum x changes rsum to reflect the addition of x to its set of samples by updating the number of samples, the sum, and the sum of squares.

Note the use of single semicolons to sequence operations. When we were working purely functionally, this wasn’t necessary, but you start needing it when you’re writing imperative code.

Here’s an example of create and update in action. Note that this code uses List.iter, which calls the function ~f on each element of the provided list:

let rsum = create ();;
>val rsum : running_sum = {sum = 0.; sum_sq = 0.; samples = 0}
List.iter [1.;3.;2.;-7.;4.;5.] ~f:(fun x -> update rsum x);;
>- : unit = ()
mean rsum;;
>- : float = 1.33333333333333326
stdev rsum;;
>- : float = 3.94405318873307698

Warning: the preceding algorithm is numerically naive and has poor precision in the presence of many values that cancel each other out. This Wikipedia article on algorithms for calculating variance provides more details.

Refs

We can create a single mutable value by using a ref. The ref type comes predefined in the standard library, but there’s nothing really special about it. It’s just a record type with a single mutable field called contents:  

let x = { contents = 0 };;
>val x : int ref = {contents = 0}
x.contents <- x.contents + 1;;
>- : unit = ()
x;;
>- : int ref = {contents = 1}

There are a handful of useful functions and operators defined for refs to make them more convenient to work with:

let x = ref 0  (* create a ref, i.e., { contents = 0 } *);;
>val x : int ref = {Base.Ref.contents = 0}
!x             (* get the contents of a ref, i.e., x.contents *);;
>- : int = 0
x := !x + 1    (* assignment, i.e., x.contents <- ... *);;
>- : unit = ()
!x;;
>- : int = 1

There’s nothing magical with these operators either. You can completely reimplement the ref type and all of these operators in just a few lines of code:

type 'a ref = { mutable contents : 'a };;
>type 'a ref = { mutable contents : 'a; }
let ref x = { contents = x };;
>val ref : 'a -> 'a ref = <fun>
let (!) r = r.contents;;
>val ( ! ) : 'a ref -> 'a = <fun>
let (:=) r x = r.contents <- x;;
>val ( := ) : 'a ref -> 'a -> unit = <fun>

The 'a before the ref indicates that the ref type is polymorphic, in the same way that lists are polymorphic, meaning it can contain values of any type. The parentheses around ! and := are needed because these are operators, rather than ordinary functions. 

Even though a ref is just another record type, it’s important because it is the standard way of simulating the traditional mutable variables you’ll find in most languages. For example, we can sum over the elements of a list imperatively by calling List.iter to call a simple function on every element of a list, using a ref to accumulate the results:

let sum list =
  let sum = ref 0 in
  List.iter list ~f:(fun x -> sum := !sum + x);
  !sum;;
>val sum : int list -> int = <fun>

This isn’t the most idiomatic way to sum up a list, but it shows how you can use a ref in place of a mutable variable.

let z = 7 in
z + z;;
>- : int = 14

z;;
>Line 1, characters 1-2:
>Error: Unbound value z

let x = 7 in
let y = x * x in
x + y;;
>- : int = 56

For and While Loops

OCaml also supports traditional imperative control-flow constructs like for and while loops. Here, for example, is some code for permuting an array that uses a for loop:      

let permute array =
  let length = Array.length array in
  for i = 0 to length - 2 do
    (* pick a j to swap with *)
    let j = i + Random.int (length - i) in
    (* Swap i and j *)
    let tmp = array.(i) in
    array.(i) <- array.(j);
    array.(j) <- tmp
  done;;
>val permute : 'a array -> unit = <fun>

This is our first use of the Random module. Note that Random starts with a fixed seed, but you can call Random.self_init to choose a new seed at random.  

From a syntactic perspective, you should note the keywords that distinguish a for loop: for, to, do, and done.

Here’s an example run of this code:

let ar = Array.init 20 ~f:(fun i -> i);;
>val ar : int array =
>  [|0; 1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16; 17; 18; 19|]
permute ar;;
>- : unit = ()
ar;;
>- : int array =
>[|12; 16; 5; 13; 1; 6; 0; 7; 15; 19; 14; 4; 2; 11; 3; 8; 17; 9; 10; 18|]

OCaml also supports while loops, as shown in the following function for finding the position of the first negative entry in an array. Note that while (like for) is also a keyword:

let find_first_negative_entry array =
  let pos = ref 0 in
  while !pos < Array.length array && array.(!pos) >= 0 do
    pos := !pos + 1
  done;
  if !pos = Array.length array then None else Some !pos;;
>val find_first_negative_entry : int array -> int option = <fun>
find_first_negative_entry [|1;2;0;3|];;
>- : int option = None
find_first_negative_entry [|1;-2;0;3|];;
>- : int option = Some 1

As a side note, the preceding code takes advantage of the fact that &&, OCaml’s “and” operator, short-circuits. In particular, in an expression of the form expr1&&expr2, expr2 will only be evaluated if expr1 evaluated to true. Were it not for that, then the preceding function would result in an out-of-bounds error. Indeed, we can trigger that out-of-bounds error by rewriting the function to avoid the short-circuiting:

let find_first_negative_entry array =
  let pos = ref 0 in
  while
    let pos_is_good = !pos < Array.length array in
    let element_is_non_negative = array.(!pos) >= 0 in
    pos_is_good && element_is_non_negative
  do
    pos := !pos + 1
  done;
  if !pos = Array.length array then None else Some !pos;;
>val find_first_negative_entry : int array -> int option = <fun>
find_first_negative_entry [|1;2;0;3|];;
>Exception: Invalid_argument "index out of bounds".

The or operator, ||, short-circuits in a similar way to &&.

Compiling and Running

We’ll compile our program using dune, a build system that’s designed for use with OCaml projects. First, we need to write a dune-project file to specify the project’s root directory.

(lang dune 2.9)
(name rwo-example)

Then, we need to write a dune file to specify the specific thing being built. Note that a single project will have just one dune-project file, but potentially many sub-directories with different dune files.

In this case, however, we just have one:

(executable
 (name      sum)
 (libraries base stdio))

All we need to specify is the fact that we’re building an executable (rather than a library), the name of the executable, and the name of the libraries we depend on.

We can now invoke dune to build the executable.

dune build sum.exe

The .exe suffix indicates that we’re building a native-code executable, which we’ll discuss more in Chapter 4, Files Modules And Programs. Once the build completes, we can use the resulting program like any command-line utility. We can feed input to sum.exe by typing in a sequence of numbers, one per line, hitting Ctrl-D when we’re done:

$ ./_build/default/sum.exe
1
2
3
94.5
Total: 100.5

More work is needed to make a really usable command-line program, including a proper command-line parsing interface and better error handling, all of which is covered in Chapter 15, Command Line Parsing.