## 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+2letsquare x = x * x;;valsquare : int -> int = <fun>letrecfact x =ifx <= 1then1elsex * fact (x - 1);;valfact : 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).

letl = 1 :: 2 :: 3 :: [];;vall : 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.

letrecsort =function| [] -> [] | x :: l -> insert x (sort l)andinsert elem =function| [] -> [elem] | x :: l ->ifelem < xthenelem :: x :: lelsex :: insert elem l;;valsort : 'a list -> 'a list = <fun>valinsert : '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

loops.
**for**

letadd_polynom p1 p2 =letn1 = Array.length p1andn2 = Array.length p2inletresult = Array.create (max n1 n2) 0infori = 0ton1 - 1doresult.(i) <- p1.(i) done;fori = 0ton2 - 1doresult.(i) <- result.(i) + p2.(i) done; result;;valadd_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

loop:
**for**

letfact n =letresult = ref 1infori = 2tondoresult := i * !result done; !result;;valfact : 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:

letrecsigma f =function| [] -> 0 | x :: l -> f x + sigma f l;;valsigma : ('a -> int) -> 'a list -> int = <fun>

Anonymous functions may be defined using the

construct:
**function**

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

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

letcompose f g =functionx -> f (g x);;valcompose : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b = <fun>letsquare_o_fact = compose square fact;;valsquare_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:

letrecpower f n =ifn = 0thenfunctionx -> xelsecompose f (power f (n - 1));;valpower : ('a -> 'a) -> int -> 'a -> 'a = <fun>

The n^{th} derivative of a function can be computed as in
mathematics by raising the derivative function to the n^{th} power:

letderivative dx f =functionx -> (f (x +. dx) -. f x) /. dx;;valderivative : float -> (float -> float) -> float -> floatletsin''' = power (derivative 1e-5) 3 sin;;valsin''' : float -> float = <fun>letpi = 4.0 *. atan 1.0insin''' pi;; - : float = 0.999998972517346263

## Symbolic computation

Let us consider simple symbolic expressions made up of integers, variables,

bindings, and binary operators. Such expressions can be defined
as a new data type, as follows:
**let**

typeexpression = | Numofint | Varofstring | Letofstring * expression * expression | Binopofstring * expression * expression;;

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

letreceval env =function| Num i -> i | Var x -> List.assoc x env | Let (x, e1, in_e2) ->letval_x = eval env e1ineval ((x, val_x) :: env) in_e2 | Binop (op, e1, e2) ->letv1 = eval env e1inletv2 = eval env e2ineval_op op v1 v2andeval_op op v1 v2 =matchopwith| "+" -> v1 + v2 | "-" -> v1 - v2 | "*" -> v1 * v2 | "/" -> v1 / v2 | _ -> failwith ("Unknown operator: " ^ op);;valeval : (string * int) list -> expression -> int = <fun>valeval_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:

letrecfib x =ifx <= 1then1elsefib (x - 1) + fib (x - 2);;valfib : 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