This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

# A Hundred Lines of Caml

## Elementary functions

Using the interactive system, let us define the square function and the recursive factorial function. Then, let us apply these functions to sample values:

```        Objective Caml version 3.07+2

let square x = x * x;;
val square : int -> int = <fun>
let rec fact x =
if x <= 1 then 1 else x * fact (x - 1);;
val fact : int -> int = <fun>
fact 5;;
- : int = 120
square 120;;
- : int = 14400
```

## Automatic memory management

All allocation and deallocation operations are fully automatic. For example, let us consider simply linked lists.

Lists are predefined in Caml. The empty list is written `[]`. The constructor that allows prepending an element to a list is written `::` (in infix form).

```let l = 1 :: 2 :: 3 :: [];;
val l : int list = [1; 2; 3]
[1; 2; 3];;
- : int list = [1; 2; 3]
5 :: l;;
- : int list = [5; 1; 2; 3]
```

## Polymorphism: sorting lists

Insertion sort is defined using two recursive functions.

```let rec sort = function
| [] -> []
| x :: l -> insert x (sort l)

and insert elem = function
| [] -> [elem]
| x :: l ->
if elem < x then elem :: x :: l else x :: insert elem l;;
val sort : 'a list -> 'a list = <fun>
val insert : 'a -> 'a list -> 'a list = <fun>
```

Note that the type of the list elements remains unspecified: it is represented by a type variable `'a`. Thus, `sort` can be applied both to a list of integers and to a list of strings.

```sort [2; 1; 0];;
- : int list = [0; 1; 2]
sort ["yes"; "ok"; "sure"; "ya"; "yep"];;
- : string list = ["ok"; "sure"; "ya"; "yep"; "yes"]
```

## Imperative features

Let us encode polynomials as arrays of integer coefficients. Then, to add two polynomials, we first allocate the result array, then fill its slots using two successive `for` loops.

```let add_polynom p1 p2 =
let n1 = Array.length p1
and n2 = Array.length p2 in
let result = Array.create (max n1 n2) 0 in
for i = 0 to n1 - 1 do result.(i) <- p1.(i) done;
for i = 0 to n2 - 1 do result.(i) <- result.(i) + p2.(i) done;
result;;
val add_polynom : int array -> int array -> int array
add_polynom [| 1; 2 |] [| 1; 2; 3 |];;
- : int array = [|2; 4; 3|]
```

Caml offers updatable memory cells, called references: `ref init` returns a new cell with initial contents `init`, `!cell` returns the current contents of `cell`, and `cell := v` writes the value `v` into `cell`.

We may redefine `fact` using a reference cell and a `for` loop:

```let fact n =
let result = ref 1 in
for i = 2 to n do
result := i * !result
done;
!result;;
val fact : int -> int = <fun>
fact 5;;
- : int = 120
```

## Higher-order functions

There is no restriction on functions, which may thus be passed as arguments to other functions. Let us define a function `sigma` that returns the sum of the results of applying a given function `f` to each element of a list:

```let rec sigma f = function
| [] -> 0
| x :: l -> f x + sigma f l;;
val sigma : ('a -> int) -> 'a list -> int = <fun>
```

Anonymous functions may be defined using the `function` construct:

```sigma (function x -> x * x) [1; 2; 3];;
- : int = 14
```

Polymorphism and higher-order functions allow defining function composition in its most general form:

```let compose f g = function x -> f (g x);;
val compose : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b = <fun>
let square_o_fact = compose square fact;;
val square_o_fact : int -> int = <fun>
square_o_fact 5;;
- : int = 14400
```

## The power of functions

The power of functions cannot be better illustrated than by the `power` function:

```let rec power f n =
if n = 0 then function x -> x
else compose f (power f (n - 1));;
val power : ('a -> 'a) -> int -> 'a -> 'a = <fun>
```

The nth derivative of a function can be computed as in mathematics by raising the derivative function to the nth power:

```let derivative dx f = function x -> (f (x +. dx) -. f x) /. dx;;
val derivative : float -> (float -> float) -> float -> float
let sin''' = power (derivative 1e-5) 3 sin;;
val sin''' : float -> float = <fun>
let pi = 4.0 *. atan 1.0 in sin''' pi;;
- : float = 0.999998972517346263
```

## Symbolic computation

Let us consider simple symbolic expressions made up of integers, variables, `let` bindings, and binary operators. Such expressions can be defined as a new data type, as follows:

```type expression =
| Num of int
| Var of string
| Let of string * expression * expression
| Binop of string * expression * expression;;
```

Evaluation of these expressions involves an environment that maps identifiers to values, represented as a list of pairs.

```let rec eval env = function
| Num i -> i
| Var x -> List.assoc x env
| Let (x, e1, in_e2) ->
let val_x = eval env e1 in
eval ((x, val_x) :: env) in_e2
| Binop (op, e1, e2) ->
let v1 = eval env e1 in
let v2 = eval env e2 in
eval_op op v1 v2

and eval_op op v1 v2 =
match op with
| "+" -> v1 + v2
| "-" -> v1 - v2
| "*" -> v1 * v2
| "/" -> v1 / v2
| _ -> failwith ("Unknown operator: " ^ op);;
val eval : (string * int) list -> expression -> int = <fun>
val eval_op : string -> int -> int -> int = <fun>
```

As an example, we evaluate the phrase `let x = 1 in x + x`:

```eval [] (Let ("x", Num 1, Binop ("+", Var "x", Var "x")));;
- : int = 2
```

Pattern matching eases the definition of functions operating on symbolic data, by giving function definitions and type declarations similar shapes. Indeed, note the close resemblance between the definition of the `eval` function and that of the `expression` type.

## Elementary debugging

To conclude, here is the simplest way of spying over functions:

```let rec fib x = if x <= 1 then 1 else fib (x - 1) + fib (x - 2);;
val fib : int -> int = <fun>
#trace fib;;
fib is now traced.
fib 3;;
fib <-- 3
fib <-- 1
fib --> 1
fib <-- 2
fib <-- 0
fib --> 1
fib <-- 1
fib --> 1
fib --> 2
fib --> 3
- : int = 3
```