Introduction to Objective OCaml

March 2, 2024

Variables and Functions

In ML, variables are names for values. Variable bindings are bind with the keyword $let$ .

$let identifier = expression$

Definitions using $let$ can also be nested using the $in$ form.

$let identifier = {expression}_{1} in {expression}_{2}$

The expression ${expression}_{2}$ is called the body of the $let$ The variable named $identifier$ is defined as the value of ${expression}_{1}$ within the body. The $identifier$ is defined only in the body ${expression}_{2}$ and not ${expression}_{1}$ . A $let$ with a body is an expression; the value of a $let$ expression is the value of the body.

Functions are defined with the keyword $Fun$

$fun v_{1} v_{2} \dots v_{n} \to e x p r e s s i o n$

Higher order functions

Fold right

The map function allows us to modify each item in a list individually, while the filter function enables us to selectively retain or discard each item based on a criterion. However, both functions operate on elements independently. What if our goal it to aggregate all the elements if a list together?

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

let concat = function 
  | [] -> ""
  | (h::t) -> h ^ concat t

For an empty list, a distinct base value is returned: 0 for summing and an empty string (““) for concatenation.
In the case of a non-empty list, a different operation is employed to merge the head of the list with the outcome of the recursive call: addition (+) for summing and concatenation (^) for joining strings.

let rec sum' init = function 
  | [] -> init
  | (h::t) -> h + sum' init t

let sum = sum' 0

let rec concat' init = function 
  | [] -> init
  | (h::t) -> h ^ concat' init t

let concat = concat' ""

Exercise 3.3:

We write a function $sum$ that, given two integers bounds n and m and a function f, computes a summation. $sum n m f = \sum_{i = 1}^{m} f (i)$

let sum n m f = 
    if n > m then
        0
    else
        f n + sum (n + 1) m f

Exercise 3.4:

Euclid’s algorithm computes the greatest common divisor (GCD) of two integers.

$\begin{aligned} gcd (n, k) = \\ while m \neq 0 \\ if n > m \\ n \leftarrow n - m \\ else \\ m \leftarrow m - n \\ return n \end{aligned}$

(* Method 1 *)
let rec gcd n m =
  if m = 0 then n
  else if n > m then gcd (n - m) m
  else gcd n (m - n);;

(* Method 2 *)
let rec gcd n m =
  if m = 0 then n
  else gcd m (n mod m)

Exercise 3.6:

(* A dictionary is represented as a function from a string to an int *)
type dictionary = string -> int

(* The empty dictionary function that returns 0 for any key *)
let empty : dictonary = fun _ -> 0

(* Function to add key-value pair to a dictiioanry *)
let add d k v = fun k' -> if k' = k then v else d k'

(* Function to find the value associated with a key in a dictionary *)
let find d k : int = d k

Basic pattern matches

One of the most potent capabilities of ML is its utilization of pattern matching for defining computations via case analysis. The syntax for pattern matching is expressed through a match expression, which is outlined as follows.

natch expression with 
  | pattern1 -> expression1
  | pattern2 -> expression2
  .
  .
  .
  | pattern_n -> expression_n