# CorrectionExamen2019

## Exo 1 : typage

### Question 1

f1 : int -> int ref -> int

f2 : 'a -> 'a ref -> 'a ref -> unit

f3 : (* int ref versus ref *)

f4 : ('a ref -> bool) -> 'a ref -> unit

## Exo 2 : Tak

### Question 2

let rec tak x y z = 
  if y<z then
    tak (tak (x-1) y  z) (tak (y-1) z x) (tak(z-1) x y)
  else
    z

### Question 3

let table = Hashtbl.create 17

let rec tak x y z =
  if y<z then
    memo_tak (memo_tak (x-1) y  z) 
      (memo_tak (y-1) z x) 
      (memo_tak (z-1) x y)
  else
    z
and memo_tak x y z =
   try Hashtbl.find table (x,y,z)
   with Not_found -> let v = tak x y z in 
                     Hashtbl.add table (x,y,z) v ; v

## Exo 3 : Evaluation

### Question 4

Initialement :

t = [| 0; 1; 2 |]
r = { a = [| t; t |]; b = t }

Après `r.b.(0) <- 10` :

t = [| 10; 1; 2 |]
r = { a = [| t; t |]; b = t }

Après `r.a.(0).(0) <- 4` :

t = [| 4; 1; 2 |]
r = { a = [| t; t |]; b = t }

Après `r.a.(0) <- [|0;0|]` :

s = [| 0 ; 0 |]
t = [| 4; 1; 2 |]
r = { a = [| s; t |]; b = t }

### Question 5

La fonction `mystere` décrémente `x` récursivement jusqu'à arriver `1`puis ajoute, à ce `1`, les anciens `x` qui ont été retenus sous `y`.

(* On commence par retenir y=5 qu'on ajoutera à la toute fin, avant ça on
appelle mystere en décrémentant x. *)
mystere 2 => x:= 2 + !x 
mystere 3 => x:= 3 + !x
mystere 4 => x:= 4 + !x
mystere 5 => x:= 5 + !x

On a `1+2+3+4+5=15` donc `mystere x; !x` où `x` est une référence vers `5` donne `15`.

### Question 6

let f l = List.map (fun x -> incr x; if !x>2 then (ref 10) else x) l
(* La fonction incr incrémente de 1 une référence entière *)

On peut représenter les itérations de `List.map` par les listes successives suivantes :
Début : `[r ; r; r; r]` où `r -> 1` (`r` pointe vers `1`)
Itération 1 : `[r ; r; r; r]` où `r -> 2`
Itération 2 : `[r ; r'; r; r]` où `r -> 3` et `r' -> 10`
Itération 3 : `[r ; r'; r''; r]` où `r -> 4`, `r' -> 10` et `r'' -> 10`
Itération 4 : `[r ; r'; r''; r''']` où `r -> 5`, `r' -> 10`, `r'' -> 10` et `r''' -> 10`
Le résultat est donc une liste contenant 4 références toutes distinctes pointant vers les valeurs `5`, `10`, `10` et `10` respectivement.

## Exo 4 : Radix

### Question 7

1=>1=>N(false,V,N(true,V,V))
4=>100=>N(false,N(false,N(false,N(true,V,V),V),V),V)
5=>101=>N(false,V,N(false,N(false,N(false,V,N(true,V,V),V),V),V),V)
6=>110=>N(false,N(false,V,N(false,V,N(true,V,V))),V)
(* mais il faut les combiner: *)
let a1 = N(false ,  
          N(false, 
            N(false, 
              V, 
              N(true,V,V)
            ), 
            N(false,
              V, 
              N(true,V,V)
            )
          ), 
          N(true, 
            N(false, 
            V, 
            N(true,V,V)
            ),
            V
          ))

En examen, produire le dessin aurait suffit car la question est trop calculatoire.

### Question 8

let rec find x t = match t with
  | V -> false
  | N (b,t0,t1) ->
     if x=0 then b
     else let r = x mod 2 in
          let x2 = x/2 in
          if r = 0 then find x2 t0 
          else find x2 t1

### Question 9

let rec add t x = match t with
  | V -> add (N (false, V, V)) x
  | N (b, t0, t1) ->
      if x = 0 then N (true, t0, t1)
      else let r = x mod 2 in
           let x2 = x/2 in
           if r = 0 then N (b, add t0 x2, t1)
           else N (b, t0, add t1 x2)

### Question 10

let from_list l =
    List.fold_left add V l

### Question 11
La liste l est la représentation en binaire de l'entier en base 10 que l'on veut calculer dans cette question.

let list_to_int l =
  List.fold_left (fun acc b -> 2 * acc + b) 0 l

### Question 12

let to_list t =
  let paths = ref [] in
  let rec tlp p t =
    match t with
    | V -> ()
    | N (b, t0, t1) ->
        if b then paths := p :: !paths;
        tlp (0::p) t0;
        tlp (1::p) t1 in
  tlp [] t;
  List.map list_to_int !paths

### Question 13

let rec union t1 t2 = match t1, t2 with
  | V, t | t, V -> t
  | N (b1, t11, t12), N (b2, t21, t22) ->
      N (b1||b2, union t11 t21, union t12 t22)

Ou, plus concis mais moins efficace :

let union t1 t2 =
  List.fold_left add t1 (to_list t2)