(** 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. *)
let z = 1.
let t = 2. *. z +. 1.
        

(* 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 of 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)

let _ = assert (fact 5 = 120)
(* 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_opt n =
  let rec loop n acc =
    if n = 0 then
      acc
    else
      loop (n-1) (n*acc)
  in
  loop n 1
let _ = assert (fact 100 = fact_opt 100)
 
(* 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 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)