(** Expressions and immutable variables *)
(* We introduce a new variable with the keyword 'let'
Variables are immutable, and must be initialized *)
let x = 1
let y = 2*x + 1
(* The compiler infers the type of each variable and each expression,
without annotations from the programmer. Basic types include
- int
- float
- bool
- string
- char
Type-inconsistent programs are rejected at compile time. *)
(* Expressions that do not compute an actual value are given the special
type 'unit'. Technically, this type contains a unique value, written '()',
which does not carry any information.
This value can be used in the special form of declaration 'let () ='
to introduce a computation which does not produce a value (but which can
be interesting for its side effects *)
let () = print_string "Hello, world!\n"
(* Conditional expressions contain a condition, and two branches (positive,
and negative) *)
let z = if x > 0 then 1+x else 1-x
(* A conditional expression is an expression, and can be included into bigger
expressions *)
let z = 1 + (if x>0 then x else -x)
(* Counted loop *)
(* In a for loop, we indicate the lower and upper boundaries (included) *)
let () =
for i=0 to 5 do
print_int i
done
(* prints 012345 *)
(** Functions *)
(* A function can be declared similarly to a variable, by adding one
or more parameters. There is no explicit return: the body a the function
is an expression, whose value is implicitly returned *)
let f x = x + 1
(* Multiple arguments are declared one after the other *)
let g x y = x + y
(* Arguments of a function are provided one after the other *)
let a = f 3 (* this gives 3+1 = 4 *)
let b = g 5 6 (* this gives 5+6 = 11 *)
(* Parentheses are used whenever a function argument is not atomic *)
let c = g (f 3) (g 4 5) (* this gives g (3+1) (4+5) = 4+9 = 13 *)
(* The type of a function has the shape 't1 -> t2'
Here 'f' is of type 'int -> int'
The type of a function with multiple arguments is written by chaining
multiple arrows
Here 'g' is of type 'int -> (int -> int)'
The type of 'g' can be understood as 'a function which, after receiving
its first argument, produces a function that waits for the second argument'
*)
(* The notation for function definition above is a syntactic sugar for a
combination of two elements:
- regular declaration of a variable
- definition of an anonymous function *)
let f = fun x -> x+1
let g = fun x -> fun y -> x+y
(* these are exactly the same as the previous def of 'f' and 'g' *)
(* This way of writing function types and function applications allows
partial application: applying a binary function to one argument actually
produces a unary function *)
let h = g 5 (* h is equivalent to 'fun y -> 5+y', of type 'int -> int' *)
let b = h 6 (* the same as the previous definition of b *)
(** Local variables *)
(* A function, or any expression, can contain local variables, introduced
with 'let' and 'in' *)
let f x =
let y = 2*x in
y + 1
(* Any new definition of a variable (local or otherwise) shadows the already
existing variables with the same name *)
let x =
let y = 1 in
let y = 2 in
y (* this 'y' is the second, with value '2' *)
(** Recursive functions *)
(* The keyword 'rec' allows the definition of a recursive function *)
let rec fact n =
if n = 0 then
1
else
n * fact (n-1)
(* Recursive functions may fail (stackoverflow) if there is a huge
number (>100.000) of nested recursive calls, when the stack needs to
store informations for the computations that have to be completed after
each call.
This can be optimized when recursive calls are in tail position, that means
when the recursive call is the last operation performed by the function. *)
(* Here is a tail recursive version of the function fact.
It uses an auxiliary function 'loop' with two parameters:
- 'n' is the same as above
- 'acc' is an 'accumulator', storing the products already computed
Note that local definitions can also be functions (since functions are just
ordinary values) *)
let fact n =
let rec loop n acc =
if n = 0 then
acc
else
loop (n-1) (n*acc)
in
loop n 1
(* This tail-recursive ocaml version behaves exactly the same way as the
C loop below:
int fact(int n) {
int acc = 1;
while (n != 0) {
acc = acc*n;
n--;
}
return acc;
}
The various arguments of the recursive auxiliary function loop correspond
to the variables that are updated in the loop. *)
(** Mutable variables *)
(* A behaviour similar to usual mutable variables can be achieved using
references: mutable memory cells *)
let r = ref 0 (* mutable reference, initialized with 0 *)
(* Reading the value contained by a reference requires a special operator ! *)
(* We write a new value in a reference with the assignment operator := *)
let incr r =
r := !r + 1
(* Once we have mutable state, while loops start making sense *)
let n = ref 10 (* mutable reference, initialized with 10 *)
let () =
while (!n <> 1) do
if !n mod 2 = 0
then n := !n / 2
else n := 3 * !n + 1;
incr r
done
(** Basic data structures *)
(** A. Tuples *)
(* A tuple is written as a sequence of elements separated by , *)
let p = (1, 2)
let t = (1, 2, 3)
(* A tuple can be deconstructed by a let *)
let x, y = p
(* Tuples are always immutable *)
(** B. Records *)
(* A record is similar to the notion of 'struct' in C, it can be
thought of as a tuple whose fields are named *)
type complex = { re: float; im: float }
let i = { re = 0.0; im = 1.0 }
(* Fields are accessed by their name *)
let sq_norm c = c.re *. c.re +. c.im *. c.im
(* Record fields are immutable by default, but can be declared as
'mutable' in the type definition *)
(** C. Arrays *)
(* An array is a fixed-length structure, indexed by integers *)
(* An array can be defined either by giving an explicit sequence of elements,
or by providing a size and a initial element *)
let a = [| 1; 2; 4; 8 |]
let b = Array.make 6 3 (* this is [| 3; 3; 3; 3; 3; 3 |] *)
(* Elements are accessed by their index, starting at index 0 *)
let v = a.(0) + a.(3) (* this is 1 + 8 *)
(* Array elements are mutable *)
let () = a.(1) <- 7 (* now a is [| 1; 7; 4; 8 |] *)
(* The function Array.length gives the length of an array (in constant time) *)
let sum a =
let r = ref 0 in
for i=0 to Array.length a - 1 do
r := !r + a.(i)
done;
!r
(* Definition of a higher-order iterator *)
let array_iter f a =
for i=0 to Array.length a - 1 do
f a.(i)
done
(* Exists in the standard library under the name Array.iter *)
(** D. Lists *)
(* A list is an immutable sequence of elements *)
let l = [1; 2; 4; 8]
(* A list is either the empty list [] or, obtained by adding a head element
in front a list, using the operator :: *)
let l' = 1 :: (2 :: (4 :: (8 :: []))) (* this is equal to l *)
(* Note that the right-association of parentheses is implicit here *)
let l'' = 1 :: 2 :: 4 :: 8 :: [] (* still equal to l *)
(* Functions on lists can be defined by case on the shape of the list *)
let rec length l = match l with
| [] -> 0
| x::l' -> 1 + length l'
(* Tail-recursive variant of the latter *)
let length l =
let rec loop l acc = match l with
| [] -> acc
| x::l' -> loop l' (1+acc)
in
loop l 0
(* Definition of a higher-order iterator *)
let rec list_iter f l = match l with
| [] -> ()
| x::l' -> f x; list_iter f l'
(* Exists in the standard library under the name List.iter *)
(** Implementing an association table *)
(* An association table stores a finite set of key/value pairs.
Main operations are:
- testing the presence of a key
- retrieving the value associated to a given key
- updating the value for a given key, or adding a key/value pair
*)
(** A. Association list *)
(* Simple implementation by a list of pairs *)
(* If keys are strings, and values are integers, our simple structure has the
following type *)
type assoc_list = (string * int) list
(* Tests whether k appears in l *)
let rec assoc_mem k l = match l with
| [] -> false
| (k', _) :: l' -> k=k' || assoc_mem k l'
(* Updates the value of a key (or adds it if not present)
Since lists are immutable, this function does not modify the list;
it returns an updated version instead *)
let rec assoc_update k v l = match l with
| [] -> [(k, v)] (* if the key is not present, add a new pair *)
| (k', v') :: l' ->
if k=k' then (* if the first key is the one we are looking for *)
(k', v) :: l' (* update the value and keep what comes after *)
else (* otherwise *)
(k', v') :: assoc_update k v l' (* keep this pair and look further *)
(* Finds the value associated to a given key *)
let rec assoc_find k l = match l with
| [] -> raise Not_found (* predefined exception *)
| (k', v)::l' -> if k=k' then v else assoc_find k l'
(** B. Hashtable *)
(* A hashtable stores key/value pairs, in an array-like structure
* indexed by the keys.
*
* The implementation is based on an actual array A. Each key K is associated
* to an integer code h(K), called its 'hash'. We consider this hash modulo
* the actual size of the underlying array A to obtain a valid index I of A,
* where we the value can be stored.
* However, several keys K, K', ... may be mapped to the same index I of A.
* Thus, the array A will not contain directly values, but rather lists of
* key/value pairs with equal hash (modulo).
*
* Why this is efficient: assuming the hash function distributes the keys in
* an approximately uniform way throughout the array, and the size of the array
* is comparable to the number of stored pairs, most key/value pairs will be
* contained in lists whose length does not exceed 2.
*)
(* OCaml standard library offers a generic hash function *)
let hash x = Hashtbl.hash x
(* The main part of a hashtable is the array of association lists;
we also store the number of key/value pairs and make both elements mutable
so that we can ensure that the array is always large enough *)
type table = {
mutable contents: assoc_list array;
mutable size: int;
}
(* Test the presence of a key by first computing the index, then delegating
to the function on association lists *)
let mem k t =
let i = hash k mod Array.length t.contents in
assoc_mem k t.contents.(i)
(* Find is similar *)
let find k t =
let i = hash k mod Array.length t.contents in
assoc_find k t.contents.(i)
(* An higher-order iterator applying some function f to all the (K,V) pairs
in the table, built by combining the iterators on arrays and on lists *)
let iter f t =
Array.iter (List.iter f) t.contents
(* Update a table by doubling the size of the underlying array
Start with an empty array, insert all key/value pairs again,
and then replace the old array *)
let extend t =
let new_capacity = 2*Array.length t.contents in
let new_contents = Array.make new_capacity [] in
iter (fun (k, v) ->
let i = hash k mod new_capacity in
new_contents.(i) <- assoc_update k v new_contents.(i)
) t;
t.contents <- new_contents
(* Update an association
If the key is not present, first increase the size and extend the
underlying array if it becomes more than half-filled *)
let update k v t =
let i = hash k mod Array.length t.contents in
if not (assoc_mem k t.contents.(i)) then begin
t.size <- t.size + 1;
if t.size > Array.length t.contents / 2 then extend t
end;
t.contents.(i) <- assoc_update k v t.contents.(i)