Skip to content

Lecture 2.3: More Types with ADTs; Recursion

Checked arithmetic

In OCaml (like other languages), the type of integer division is int -> int -> int. If we pass 0 as the second argument, we get an exception: 

utop # 3 / 0;;
Exception: Division_by_zero.

One way to avoid throwing an exception is to write a checked version that refuses to run if the second argument is zero:

type int_option =
  | IntOp of int
  | IntOpEmpty

let div_option (n : int) (d : int) : int_option =
  if d = 0 then IntOpEmpty else (IntOp (n / d))

Of course, this is the built-in ocaml type option: 

let divide_checked (i : int) (j : int) : int option = 
    if j = 0 then None else Some (i / j)

Recursion with Lists

Basic lists in OCaml are created by using the following syntax: 

utop # [1; 2; 3];;
- : int list = [1; 2; 3]

Note a few things:

  1. Lists are separated by ;, rather than , as in other languages.
  2. Given a type t (e.g., int), the type of lists of t is t list.
  3. Lists can only hold a single type of value, so [1; "hi"] is ill-typed.

Given a list, you can add an element to the front by using the cons operator: 

utop # let x = [1; 2; 3];;
- : int list = [1; 2; 3]

utop # 0 :: x;;
- : int list = [0; 1; 2; 3]
Lists in OCaml are either empty, written [], or a cons of two elements: x :: xs.

Let's make our own, custom list and write some recursive functions: 

type int_list =
  | Empty                       (*    [] *)
  | Cons of int * int_list;;    (* x::xs *)

let intlist0 = Empty;;
let intlist1 = Cons (2 , (Cons (1, Empty)));;
let intlist2 = Cons (3 , (Cons (2 , (Cons (1, Empty)))));;

Given a list, we can destruct it via pattern matching: 

let rec sum (xs : int_list) : int = 
    match xs with
    | Empty -> 0
    | Cons(x, xs') -> x + sum xs'

More examples 
let rec len (xs : int_list) : int = 
match xs with 
| Empty -> 0
| Cons(_x, xs') -> 1 + sum xs' (* We use variables with underscores if we don't use the result. *)

let rec add1 (xs : int_list) : int_list = 
match xs with 
| Empty -> Empty
| Cons(x, xs') -> Cons((1 + x), add1 xs')

let rec mul2 (xs : int_list) : int_list = 
match xs with 
| Empty -> Empty
| Cons(x, xs') -> Cons((2 * x), add1 xs')

(* Generalizing add1 and mul2, by applying an arbitrary function to each element. *)
let rec map (f : int -> int) (xs : int_list) : int_list = 
match xs with 
| Empty -> Empty
| Cons(x, xs') -> Cons((f x), map f xs')

(* We can recover add1 and mul2 by instantiating the function. *)
let add1 = map (fun (x : int) -> x + 1)
let mul2 = map (fun (x : int) -> x * 2)

(* Generalizing sum, by using an arbitrary function with an accumulator. *)
let rec fold (f : int -> int -> int) (acc : int) (xs : int_list) : int = 
match xs with 
| Empty -> acc
| Cons(x, xs') -> 
    let acc' = f acc x in 
    fold f acc' xs'

(* sum is then given by instantiating the function and the initial value of the accumulator. *)
let sum = fold (fun (acc : int) (x : int) -> acc + x) 0
let mul = fold (fun (acc : int) (x : int) -> acc * x) 1

let max_nonneg = fold (fun (acc : int) (x : int) -> if acc <= x then x else acc) 0
(* TODO: What if we got the accumulator wrong for mul? What if it was 0? *)

let rec append (xs : int_list) (ys : int_list) : int_list = 
match xs with 
| Empty -> ys
| Cons(x, xs') -> Cons(x, append xs' ys)

let rec reverse (xs : int_list) : int_list = 
match xs with 
| Empty -> Empty (* Reverse of empty is empty *)
| x::xs -> append (reverse xs) (Cons (x, Empty)) (* Reverse the tail; append x at the end of it *)

Recursing on Binary trees

Let's look at an implementation of a binary tree type in OCaml, where the leaves are integers:

type bintree = | Leaf of int | Branch of bintree * bintree

This defines an algebraic data type, or ADT, which has a number of constructors --- here, Leaf and Branch --- which each have arguments: Leaf has one argument of type int, while Branch has two arguments of type bintree.

Note

While bintree has two arguments of type bintree, you should, in this case, not think of this as one argument of the pair type bintree * bintree.

Let's look at a few binary trees, and how they can be represented in OCaml.

    .
   / \
  2   7

This would be written Branch (Leaf 2, Leaf 7). 

    .
   / \
  .   42
 / \
0  -1

This would be written Branch (Branch (Leaf 0, Leaf (-1)), Leaf 42).

Why trees?

(Binary) trees are used all over in computer science. Here, we will think of them as data structures (supporting efficient implementations of maps and sets); later on in this class, we will use trees to represent the syntax of a simple programming language.