# CorrectionExamen2013

## 1 Typage

### Question 1.1

let f1 x y = (x, not y)

val f1 : 'a -> bool -> 'a * bool

let rec f2 a b =
  match a with
  | [] -> not b
  | x::l -> f2 l x

val f2 : bool list -> bool -> bool

let f3 f g h = f g && g h

val f3 : (('a -> bool) -> bool) -> ('a -> bool) -> 'a -> bool

let f4 x y = if x y then [x] else [y]

`f4` n'est pas bien typée. Si c'était bien typé alors on aurait`x` d'un certain type `a -> b` avec `y` de type `a` (appel `x y`). Donc puisque les branches d'un `if` doivent être de même type on doit avoir `a = (a -> b)`, d'où la contradiction.

### Question 1.2

let f x = if x = 0.0 then G("erreur") else D(1.0 /. x)

val f : float -> float t

let g h x = h (D x)

val g : ('a t -> 'b) -> 'a -> 'b

## 2 Évaluation

### Question 2.1

Même question que la [question 6](https://hackmd.io/o6f5yiLdQd-tSC-L7YNObQ#Question-6) dans le TP précédent.

### Question 2.2

La fonction `f` retire `2` à son argument jusqu'à ce qu'il soit négatif puis renvoie une erreur et donc la ligne `b := !b + 4` n'est jamais évaluée. Lorsqu'on évalue l'expression finale, on commence par appliquer `f` sur `a` qui pointe vers `9`. À la fin de l'exécution de `f`, `a` pointe vers `-1` (car c'est la première valeur négative en partant de `9` et en retirant `2` à chaque fois) et l'erreur `Exit` est levée. On passe donc directement au rattrapage de l'erreur et la valeur `-1` est donc renvoyée. De meme, `!a + 20` n'est jamais evaluee.

## 3 Évaluation

### Question 3.1

La fonction `mystere` renvoie `r` qui commence à `0`. Le début de la liste est utilisé pour augmenter la valeur de `r` puis est retiré de la liste et on recommence jusqu'à ce que la liste soit vide. Autrement dit `mystere` calcule la somme des entiers dans la liste donnée en argument. Donc `mystere [4; 1; 5; 3]` renvoie `13`.

On réécrit cette fonction :

let mystere = List.fold_left (+) 0

### Question 3.2

let affiche = List.iter (List.iter print_int)

## 4 Génération d'arbres binaires

### Question 4.1

Les arbres de hauteur strictement plus petite que `2` :

let a1 = E
let a2 = N (E, E)

Les arbres de hauteur `2` :

let a3 = N (N (E, E), E)
let a4 = N (E, N (E, E))
let a5 = N (N (E, E), N (E, E))

### Question 4.2

[ N (E, E);
  N (E, N(N (E, E),E));
  N (N (E, E), E);
  N (N (E, E), N (N (E, E),E)) ]

### Question 4.3

let produit t1 t2 =
  let add_e e1 acc e2 = N (e1, e2) :: acc in
  let add_t t2 acc e1 = List.fold_left (add_e e1) acc t2 in
  List.fold_left (add_t t2) [] t1

ou

let produit l1 l2 = List.fold_left(fun acc e1 ->                                 List.fold_left (fun acc e2 ->                                 N(e1,e2)::acc) acc l2) [] l1

### Question 4.4

On donne la définition des fonctions mathématiques qui renvoient les ensembles considérés en notant $\times$ le produit tel qu'il a été défini à la question précédente.

Pour $height$ :

$$
height (0) = \{E\} \\
height (n+1) = height (n) \times below(n) \,\bigcup \\
below (n) \times height (n) \,\bigcup \\
height (n) \times height (n)
$$

Pour $below$ :
$$
below (0) = empty \\
below (n+1) = below (n) \,\bigcup\, height (n)
$$

### Question 4.5

let rec height n =
  if n = 0 then [E]
  else
    let h = height (n-1) in
    let b = below (n-1) in
    produit h b @ produit b h @ produit h h

and below n =
  if n = 0 then []
  else below (n-1) @ height (n-1)

### Question 4.6

Un appel à `height 3` demande de calculer `height 2` et `below 2`, or `below 2` calcule `height 1` et `height 2` calcule aussi `height 1`.

### Question 4.7

Si on n'a qu'une seule table de hachage qui enregistre, pour un `n` donné, une paire composée de `height n` et de `below n` alors, comme après l'appel d'une des deux fonction on n'a qu'un seul des deux résulats, on ne va pas pouvoir enrichir la table.

### Question 4.8

let tbl_height = Hashtbl.create 17
let tbl_below = Hashtbl.create 17

let rec height n =
  match Hashtbl.find_opt tbl_height n with
  | Some h -> h
  | None -> let res = if n = 0 then [E]
                      else let h1 = height (n-1) in
                           let b = below (n-1) in
                           produit h1 b @ produit b h1 @ produit h1 h1 in
            Hashtbl.add tbl_height n res;
            res

and below n =
  match Hashtbl.find_opt tbl_below n with
  | Some b -> b
  | None -> let res = if n = 0 then []
                      else below (n-1) @ height (n-1) in
            Hashtbl.add tbl_below n res;
            res

Version plus proche de ce qui est dans le cours (sans type option)

let tbl_height = Hashtbl.create 17
let tbl_below = Hashtbl.create 17

let rec height n =
   try Hashtbl.find tbl_height n with
   Not_found -> let res = if n = 0 then [E]
                      else let h1 = height (n-1) in
                           let b = below (n-1) in
                           produit h1 b @ produit b h1 @ produit h1 h1 in
            Hashtbl.add tbl_height n res;
            res

and below n =
  try Hashtbl.find tbl_below n with 
  Not_found -> let res = if n = 0 then []
                      else below (n-1) @ height (n-1) in
            Hashtbl.add tbl_below n res;
            res