# CorrectionDM2020

## Bonnes pratiques

(** Patterns :
    Dès qu'il y a plus de deux cas, préférer les match aux ifs.
*)

let cards x  = 
  if x=1 then  "heart"
  else if x=2 then  "diamond"
  else if x=3 then  "spade"
  else if print_string "club"
else failwith "Not a card"

(* est à remplacer par : *)
  
  
let cards x  = match x with
  |1  "heart"
  |2 "diamond"
  |3  "spade"
  |4 "club"
  |_ failwith "Not a card"

    

(** Patterns :
 - NE PAS OUBLIER DE CAS, si un cas n'est pas possible il faut renvoyer explicitement
   une erreur (on ne veut pas de warning à la compilation)
 - Variable non utilisée -> _ (underscore) *)

let rec tail = function
  | h::t -> t

(* est à remplacer par : *)

let rec tail = function
  | [] -> assert false
  | _::t -> t

(** Ne pas utiliser ;; -> ne faire que des définitions à la place, même si la valeur
    de cette définition n'est pas conservée (underscore à la place du nom) *)

let _ = print_string "Écrire 50 fois : \"Je n'aime pas les ;;\"\n"


(** Ne pas utiliser List.hd ou List.tl -> préférer un pattern-matching *)
(** Éviter les fonctions fst et snd (surtout lorsqu'on utilise les deux éléments de la
    paire) -> préférer un pattern-matching *)

(* L'addition de paires, composante par composante : *)
let rec sum_pairs l =
  if l = [] then (0, 0)
  else let paire = sum_pairs (List.tl l) in
       (fst (List.hd l) + fst paire, snd (List.hd l) + snd paire)

(* est à remplacer par : *)

let rec sum_pairs l = match l with
  | [] -> (0, 0)
  | (h1, h2)::t -> let st1, st2 = sum_pairs t in
                   (h1 + st1,  h2 + st2)

(** Utiliser les comparaisons structurelles plutôt que physiques :
   == -> =
   != -> <>
 *)

(* Par exemple vous voulez sûrement que la valeur suivante soit true *)

let is_sadly_false = let f = Some 4 in
                     let f' = Some 4 in
                     f == f'

(* est à remplacer par : *)

let is_happily_true = let f = Some 4 in
                      let f' = Some 4 in
                      f = f'

## Exo 1

(* Correction de l'exercice 1 *)
(* C'était un exercice facile : comme vous étiez chez vous, vous pouviez tester le code et donc trouver les erreurs, voire même les lieurs des variables 
en essayant différents renommages. Et en effet, il a été très bien réussi dans l'ensemble! *)


(* Question 1 *)

(* Première façon *)

let f a b = a + b 
 
let ajout_deux g = if g = 0 then f 2 0 else f (2 + 1) (g - 1) 
  

(* Deuxième façon *)

let ajout_deux' g = if g = 0 then f 2 0 else f (2 + 1) g - 1 


(*attention, si les façons de parenthéser sont trop proches 
(on envoie par exemple les mêmes arguments à f dans les deux versions), j'ai retiré un quart de point car je considérais que c'était presque comme me donner une seule manière. *)
  

(* Question 2 *)
(* On ajoute le rec, on met les deux begin/end 
pour les matchs internes, on change le "@" en "::" *)
(* Il y avait en effet une erreur dans le code, elle ne comptait pas comme erreur de syntaxe mais je n'ai pas 
pénalisé ceux qui l'ont compté comme telle tant qu'ils ont corrigé les autres erreurs *)
(* j'acceptais aussi ceux qui ont fait un match sur les deux listes au lieu de corriger le parenthésage *)

let rec somme_derniers l1 l2 = match l1 with
  | [] -> begin match l2 with
      | [] -> 0
      | x2 :: [] -> x2
      | hd2 :: tl2 -> somme_derniers [] tl2
    end 
  | x1 :: [] -> begin match l2 with 
      | [] -> x1
      | x2 :: [] -> x1 + x2 
      | hd2 :: tl2 -> somme_derniers [x1] tl2
    end
  | hd1 :: tl1 -> somme_derniers tl1 l2 

(* Question 3 *)

(* On retire le point (on additione des int et pas des float),
on met le begin / end, on rajoute le "in" de la déclaration locale *)
(* certains ont eu une mauvaise version de la fonction, avec un x en plus dans les arguments de z (erreur d'énoncé), je n'ai pas pénalisé 
ceux qui ont gardé cette version de f et qui ont donc "échappé" à l'erreur entre le "+." et le "+" *)

let x a b = a + b 

let f y z = let v = y + 5 
  in if z > y then begin Printf.printf "%d" z ; z end
  else x v 0
  


(*Question 4 *)



(* occurence de y à la ligne 3 -> déclaration ligne 1 
occurence de y à la ligne 6 -> déclaration ligne 1
occurence de y à la ligne 7 -> déclaration ligne 5
occurence de y à la ligne 8 -> déclaration ligne 5
occurences de y à la ligne 10 -> déclaration ligne 4
     
occurence de z à la ligne 3 -> déclaration ligne 2
occurence de z à la ligne 8 -> déclaration ligne 7
     
occurence de u à la ligne 7 -> déclaration ligne 2
occurence de u à la ligne 10 -> déclaration ligne 9 *)

   
   (* Pour distinguer les déclarations, 
   on peut les renommer avec une variable différente, voir ci-dessous *) 

let y = 5.3 

let u z = z -. y 

let h = let i = y +. 2.5 in 
  let k = u i in i *. k in 
   let u = 2.0 in h +. h +. u 



(* j'ai retiré des points à tous ceux qui avaient compris mais ne respectaient pas la consigne. 
Quand on demande un numéro de ligne, on répond par un numéro de ligne, pas par ce que font les expressions.
Par ailleurs, pour la prochaine fois, les lignes de l'énoncé sont là pour être utilisées, ce n'est pas pratique de devoir s'adapter aux lignes de votre code
qui varient de copies en copies. Pas besoin non plus de me dire "y est lié à la ligne n", quand "n" est la ligne précise où il est défini mais ce n'était pas pénalisant, 
sauf quand c'était pour ajouter quelque chose de faux... *)
           
  
  
         
         

## Exo 2

(* Question 2.1 *)

let f1 (x,y) z =
    let g a b = a < b in
    if z then g x else g y;;
    
(* On observe d'abord que z est un booléen, puisqu'il est utilisé dans la construction "if z then...".
   La fonction g prend deux arguments ; comme on les compare, ils sont de même type (quelconque) noté 'a, et elle renvoie un booléen. Donc g est de type 'a -> 'a -> bool. (On note que 'a peut être n'importe quoi, pas seulement des entiers (ni même des float, strings ou char) : OCaml trouvera toujours un moyen de comparer deux objetss de même type. Pas sûr que le résultat veuille dire quelque chose, mais au niveau du typage ça ne posera pas de problème.)
   Les expressions g x et g y utilisent la curryfication, et sont des fonctions qui prennent un argument de type 'a et renvoie  un booléen. Comme l'argument doit être de même type que x ou y, il faut que x et y soient de même type. On n'a pas d'autre contrainte sur leur type.
   Ainsi, f1 est de type 'a * 'a -> bool -> 'a -> bool.
   On note que x et y ne sont jamais comparés l'un à l'autre : ce qui force l'égalité de leur type, c'est que les expressions g x et g y doivent être de même type. Si on définit une fonction f2 ainsi :
      let f2 (x,y) z =
         let g a = true in
         if z then g x else g y
   comme le type de g x et celui de g y ne dépendent pas des types de x et de y, le type de f2 est 'a * 'b -> bool -> bool car rien ne force x et y à être de même type. *)



(* Question 2.2 *)

let list_sum = List.fold_left ( fun x y -> x + y ) 0;;
(* list_sum renvoie la somme des éléments d'une liste d'entiers ; elle est de type int list -> int *)
let list_or = List.fold_left ( fun x y -> x || y ) false ;;
(* list_or renvoie la disjonction des éléments d'une liste (i.e renvoie true ssi au moins un élément vaut true) ; elle est de type bool list -> bool *)

let a = [];; 
list_sum a ;;
list_or a ;; 

(* Ces lignes sont bien typées : le type de a est 'a list (c'est donc un type polymorphe). Ce type *ne change pas* lors des différents appels, mais il convient à une fonction qui attend une int list ou une bool list. Si vous avez écrit que a prend le type int list, puis le type bool list, c'est faux, sinon on aurait un problème de typage entre la deuxième et la troisième ligne. *)

let a = ref [];;  (*a est de type : '_a list *)
list_sum !a ;; (*!a est de type : int list, donc a est de type adresse d'une liste d'entiers*)
list_or !a ;;

(* Ces lignes ne sont pas bien typées : le type de a est '_a list ref lors de sa déclaration, c'est un type monomorphe qui sera précisé dès que possible (les variables ne peuvent pas être de type polymorphe). Or comme la fonction list_sum attends une int list, cela permet au compilateur d'attribuer à a le type int list ref à partir de la deuxième ligne. Ainsi, à la troisième ligne, la fonction list_or attend un argument de type bool list, et donc la troisième ligne est mal typée. *)



(* Question 2.3 *)

type 'a arbre_binaire =
    Feuille
  | Noeud of'a *'a arbre_binaire *'a arbre_binaire ;;
   
let rec map_arbre a f = match a with
  | Feuille -> Feuille
  | Noeud(v, fg, fd) -> Noeud(f v, map_arbre fg f, map_arbre fd f)
(* type : 'a arbre_binaire -> ('a -> 'b) -> 'b arbre_binaire (attention : rien n'oblige le type sortie de f à être le même que le type de son argument) *)

let rec forall_arbre a p = match a with
  | Feuille -> true
  | Noeud(v, fg, fd) -> p v && forall_arbre fg p && forall_arbre fd p;;
(* type : 'a arbre_binaire -> ('a -> bool) -> bool *)

(* Quelques remarques sur le code : 
   - Attention aux fautes de frappes ! Plusieurs "f" au lieu de "f v" dans la ligne 48, on ne peut pas être sûr si c'est un problème de compréhension ou une typo.
   - Si vous avez bien traité le cas des feuilles, il n'est pas nécessaire de séparer les cas du type "Noeud(v, Feuille, Feuille)", "Noeud(v, fg, Feuille)"... (d'ailleurs, il faut noter que "forall_arbre Feuille p" doit toujours renvoyer true, et on n'applique pas f aux feuilles dans map_arbre car f s'applique à des objets de type 'a et Feuille est un 'a arbre_binaire)
   - Les écritures du type "if p v then ... else false" sont parfaitement équivalentes à l'écriture "p v && ...", y compris en terme de complexité, car l'évaluation des && et des || est paresseuse : ici, si le premier élément est faux, on ne descendra pas plus bas dans l'arbre (aucune des deux écritures n'est considérée comme une erreur).
   - Les formulations du type "p v = true" sont redondantes : il suffit d'écrire "p v"... (et "p v == true" est carrément faux, car "==" correspond à l'égalité des adresses en OCaml, contrairement à Python)
   - Quelques copies contenaient des choses du genre "Noeud(v, fg, fd) -> f v ; map_arbre f fg ; map_arbre f fd" (ou même chose pour forall_arbre). Ce n'est pas correct : vous êtes en train de coder un "iter_arbre"... Les fonctions qui étaient demandées devaient renvoyer un arbre ou un booléen, pas (). Il faut donc mettre vos résultats dans un constructeur du type arbre ou une formule boléenne.
   - Un certain nombre de copies utilisaient des fonctions auxiliaires superflues : si votre fonction auxiliaire a exactement les mêmes arguments que votre fonction de base, pourquoi ne pas coder directement votre fonction de base ? Ici, on ne demandait pas de récursivité terminale et les fonctions auxiliaires ne permettait de toute façon pas de les rendre terminales... *)

## Exo 3

(**EXERCICE 3**)

(**Q1**)
type  valeur = {debut : int; fin : int}
type  arbre = V | Noeud of  valeur * arbre * arbre

let rec mystere t =
  match t with
  (*1*)
  |V -> 0
  (*2*)
  |Noeud (v, V, V) -> mystere V + v.debut
  (*3*)
  |Noeud (v1, V, Noeud (v2,V,V)) ->
    let v1'= {debut = v1.debut; fin = v1.debut} in
    mystere (Noeud (v2 , Noeud (v1',V,V),V))
  (*4*)
  |Noeud (v, Noeud (v',V,V), V) ->
    let v1 = {debut = v.fin; fin = v'.debut} in
    let v2 = {debut = v'.debut; fin = v'.fin} in
    let v3 = {debut = v1.fin; fin = v2.fin} in
    let v4 = {debut = v2.debut; fin = v3.fin} in
    v.debut + mystere (Noeud (v4, V,V))
  (*5*)
  |Noeud (v, a, b) -> v.debut + mystere a + mystere b
  (*6*)
  |Noeud (v, Noeud (v2 ,V,V), Noeud (v3 ,V,V)) -> 0

let  arb = Noeud ({ debut = 1; fin =  -2000}, V, Noeud  ({debut = 400;  fin = 30000} , V, V))


(* Pour cette question, il était attendu une rédaction claire et concise, sans fautes d'orthographe. Le but était de dérouler les étapes de calculs de mystere arb. Les points importants étaient donc de signaler dans quelle branches du pattern matching vous étiez et détailler les calculs des variables locales.

Exemple de rédaction :

Pour simplifier la lecture, les constructeurs Noeud seront abrégés à N et les enregistrements { debut = a; fin = b} à {a;b}.

ETAPE 1)
Comme arb = N ({1;-2000}, V, N({400;30000}, V, V)), nous nous trouvons dans le cas 3 du pattern matching.
mystere déclare tout d'abord une variable locale v1' = {debut = v1.debut; fin = v1.debut}. Dans notre cas, v1' = {1; 1}.
Puis il y a un appel de fonction à mystere (N(v2, N(v1', V, V), V)) ici N({400;30000}, N({1;1}, V, V), V)

ETAPE 2)
Nous nous rentrons dans la branche 4.
mystere déclare 4 variables locales :
   v1 = {debut = v.fin; fin = v'.debut} = {30000;1}
   v2 = {debut = v'.debut; fin = v'.fin} = {1,1}
   v3 = {debut = v1.fin; fin = v2.fin} = {1,1}
   v4 = {debut = v2.debut; fin = v3.fin} = {1;1}

On remarque ici v2, v3 et v4 sont toutes égales à v1'.
La fonction fait ensuite le calcul de v.debut + mystere (N ({1;1};V;V)) = 400 + mystere (N ({1;1};V;V)).

ETAPE 3 : on calcule l'appel de fonction mystere (N ({1;1};V;V)))
Nous rentrons dans la branche 2.
La fonction fait le calcul de mystere V + v.debut = mystere V + 1.

ETAPE 4 : on calcule l'appel de fonction mystere V)
Nous rentrons dans la branche 1 qui renvoie 0.

En mettant bout à bout les calculs, on obtient le résultat de mystere arb suivant :
400 + mystere (N ({1;1};V;V)) =  400 + mystere V + 1 = 400 + 0 + 1 = 401

*)
  

(*Q2

Dans cette question, on attend que vous énonciez ce que calcule la fonction puis que vous démontrez pourquoi la fonction renvoie ce résultat . Il ne s'agit pas seulement de paraphrasez les étapes de la fonction. 
Il était aussi attendu que vous remarquiez que le dernier cas du pattern matching n'était pas utilisé.

(Hypothèse) La fonction mystere calcule la somme des champs debut de l'ensemble des noeuds présents de l'arbre

Vous pouviez faire une récurrence structurelle directement pour prouver cette hypothèse ou simplifier la fonction mystere d'abord puis confirmer votre hypothèse.

Je vous détaille ici le deuxième cas.
Une première étape de simplification est de simplifier les variables locales :
- Pour la branche 4, on remarque que la variable v4 est égale à la variable v'.
v4 = {debut = v2.debut; fin = v3.fin} = {debut = v'.debut; fin = v2.fin} = {debut = v'.debut; fin = v'.fin} = v'
On peut donc simplifier cette branche en : 
  |Noeud (v, Noeud (v',V,V), V) ->
    v.debut + mystere (Noeud (v', V,V))
- Pour la branche 3, comme le champs fin n'est jamais utilisé dans les valeurs renvoyé et au vu de la simplification précédente :
    mystere (Noeud (v2,Noeud (v1',V,V),V)) = mystere (Noeud (v2,Noeud (v1,V,V),V))

On peut aussi dans une deuxième étape de simplification enlever la dernière branche. Elle n'est jamais empruntée car la branche 5 inclue déjà ce cas.

On obtient donc la fonction :
let rec mystere t =
  match t with
  (*1*)
  |V -> 0
  (*2*)
  |Noeud (v, V, V) -> mystere V + v.debut
  (*3*)
  |Noeud (v1, V, Noeud (v2,V,V)) ->
    mystere (Noeud (v2, Noeud (v1,V,V),V))
  (*4*)
  |Noeud (v, Noeud (v',V,V), V) ->
    v.debut + mystere (Noeud (v', V,V))
  (*5*)
  |Noeud (v, a, b) -> v.debut + mystere a + mystere b


On remarque ici que les branches 2, 3 et 4 pourrait être incluses dans la branche 5.
En effet :
- pour Noeud (v, V, V) : a = b = V et
mystere (Noeud (v, V, V)) = mystere V + v.debut = v.debut + mystere V + mystere V =  v.debut + mystere a + mystere b
- pour Noeud (v1, V, Noeud (v2,V,V)) : a = V et b = Noeud (v2,V,V)
mystere (Noeud (v2, Noeud (v1,V,V),V)) = mystere (Noeud (v2, Noeud (v1,V,V),V)) = v2.debut + mystere (Noeud (v1, V,V))
 = v2.debut + mystere (Noeud (v1, V,V)) = v2.debut + mystere V + v1.debut = v1.debut + mystere V + v2.debut
 = v1.debut + mystere (Noeud (v2, V,V)) = v1.debut + mystere V + mystere (Noeud (v2, V,V)) = v1.debut + mystere a + mystere b
- pour Noeud (v, Noeud (v',V,V), V) : a = Noeud (v',V,V) et b = V
mystere (Noeud (v, Noeud (v',V,V), V)) = v.debut + mystere (Noeud (v', V,V)) = v.debut + mystere (Noeud (v', V,V)) + mystere V
 = v.debut + mystere a + mystere b

On peut donc simplifier en 

let rec mystere t =
  match t with
  (*1*)
  |V -> 0
  (*2*)
  |Noeud (v, a, b) -> v.debut + mystere a + mystere b

Maintenant que nous avons simplifier nous pouvons faire une récurrence structurelle pour prouver l'hypothèse :
Récurrence sur la structure de l'arbre donné en argument :
- cas 1 : L'arbre est égal à V :
mystere V = 0 ---- l'hypothèse est vérifiée
- cas 2 : L'arbre est égal à N(val,g,d) :
mystere (N(val,g,d)) = val.debut + mystere g + mystere d
Par hypothèse de récurrence,
 mystere g = somme des champs debut du sous arbre g
 mystere d = somme des champs debut du sous arbre d
mystere (N(val,g,d)) = val.debut + somme des champs debut du sous arbre g + somme des champs debut du sous arbre d
 = somme des champs debut de l'arbre
L'hypothèse est vérifiée pour ce cas.

Conclusion : La fonction mystere calcule la somme des champs debut de l'ensemble des noeuds présents de l'arbre
*)

## Exo 4

type grid = int list list

(* Question 4.1 *)

let g_example = [[-2; 0; 1; 4];
                 [7; 2; -3; -4];
                 [6; -1; 3; 5]]


(* Question 4.2 *)


let is_empty = function
  | [] -> true
  | _ -> false

(* Question 4.3 *)

let height l =
  List.length (List.hd l)

(* Question 4.4 *)

let wf_grid_exn g =
  if is_empty g then failwith "Empty grid"
  else let h = height g in
       if h = 0 || List.exists (fun l -> List.length l <> h) g
       then failwith "Badly-formed grid"

(* Question 4.5 *)

let grid_map f g =
  List.map (List.map f) g

(* Question 4.6 *)

(* On obtient 17 au maximun en prenant 4 dans la première colonne
   puis en prenant 7 dans la deuxième colonne et enfin en prenant
   6 dans la dernière colonne. Ce chemin est valide parce que 7 se
   situe sur la ligne en-dessous de celle du 3 et que le 6 se situe
   sur la même ligne que le 7. Ce chemin est maximal, car il visite
   le maximum de chaque colonne *)

(* Question 4.7 *)

let rotate_up = function
  | [] -> assert false
  | h::t -> t @ [h]

(* Question 4.8 *)

let rec firsts_last = function
  | [] -> assert false
  | [x] -> [], x
  | h::t -> let firsts, last = firsts_last t in
            h::firsts, last

(* Question 4.9 *)

let rotate_down l =
  let firsts, last = firsts_last l in
  last::firsts

(* Question 4.10 *)

let sums_2 l1 l2 =
  let l1l2updown = List.combine (List.combine (List.combine
                     l1 l2) (rotate_up l2)) (rotate_down l2) in
  List.map (fun (((n1, n2), u2), d2) ->
      let v = max n2 (max u2 d2) in
      n1 + v)
    l1l2updown

(* Question 4.11 *)

let sums g =
  let firsts, last = firsts_last g in
  List.fold_right sums_2 firsts last

let _ = sums g_example

(* Question 4.12 *)

type path = int list

(* Un chemin donne la liste des indices de ligne des cases en commençant par la
   première colonne, la ligne du haut étant la ligne d'indice 0. Par exemple, le
   chemin trouvé à la question 6 est représenté par la liste [3; 0; 0] *)

let max_path (v1, p1) (v2, p2) = if v1 > v2 then v1, p1 else v2, p2

let sums_2_path l1 l2 =
  let l1l2updown = List.combine (List.combine (List.combine
                     l1 l2) (rotate_up l2)) (rotate_down l2) in
  List.mapi (fun i (((n1, n2), u2), d2) ->
      let v, p = max_path n2 (max_path u2 d2) in
      n1 + v, i::p)
    l1l2updown

let sums_path g =
  let firsts, last = firsts_last g in
  let last = List.mapi (fun i e -> e, [i]) last in
  List.fold_right sums_2_path firsts last

let solve g =
  let firsts, last = firsts_last (sums_path g) in
  let _, path = List.fold_left max_path last firsts in
  path

(***************************************************)
(*                   TESTS                         *)
(***************************************************)

let g2 : grid =  [[0; 1; 0; 8; 1];
                  [2; 6; 7;  0; 3];
                  [10; 5; 5; 0; 2]]

open Format

let pp_list fmt pre =
  let plist = pp_print_list ~pp_sep:(fun fmt () -> fprintf fmt "; ") pre in
  fprintf fmt "[%a]" plist

let pp_print_int_list fmt = pp_list fmt pp_print_int

let pp_print_int_llist fmt = pp_list fmt pp_print_int_list

let _ = let r = height g_example in
        printf "@[<v 3>3: height g_example:@ \
                value:    %d@ \
                expected: 4@ \
                correct: %b@ @ @]@."
          r (r = 4)

let _ = let r = wf_grid_exn g_example in
        printf "@[<v 3>4: wf_grid_exn g_example:@ \
                outputs unit?: %b@ @ @]@."
          (r = ())

(*  Printf.printf "\n   Badly formed should follow: ";
    wf_grid_exn [[2;4;5] ; [2 ; 4; 5] ; [1 ; 2]] *)
(* let  _ = Printf.printf "   Empty grid should follow: ";
   wf_grid_exn [] ; Printf.print "\n\n" *)

let _ = let r = rotate_up g_example in
        printf "@[<v 3>7: rotate_up g_example:@ \
                value:    %a@ \
                expected: [[7; 2; -3; -4]; [6; -1; 3; 5]; [-2; 0; 1; 4]]@ \
                correct: %b@ @ @]@."
          pp_print_int_llist r
          (r = [[7; 2; -3; -4]; [6; -1; 3; 5]; [-2; 0; 1; 4]])

let _ = let r1 ,r2 = firsts_last g_example in
        printf  "@[<v 3>8: firsts_last g_example:@ \
                 value:    (%a, %a)@ \
                 expected: ([[-2; 0; 1; 4]; [7; 2; -3; -4]], [6; -1; 3; 5])@ \
                 correct: %b@ @ @]@."
        pp_print_int_llist r1
        pp_print_int_list r2
        ((r1, r2) = ([[-2; 0; 1; 4]; [7; 2; -3; -4]], [6; -1; 3; 5]))

let _ = let r = rotate_down g_example in
        printf  "@[<v 3>9: rotate_down g_example:@ \
                 value:    %a@ \
                 expected: [[6; -1; 3; 5]; [-2; 0; 1; 4]; [7; 2; -3; -4]]@ \
                 correct: %b@ @ @]@."
          pp_print_int_llist r
          (r = [[6; -1; 3; 5]; [-2; 0; 1; 4]; [7; 2; -3; -4]])

let _ = let l1 = [2; 4; -5; 0] in
        let l2 = [5; -1; 9; 10] in
        let r = sums_2 l1 l2 in
        printf  "@[<v 4>10: sums_2 %a %a@ \
                 value:    %a@ \
                 expected: [12; 13; 5; 10]@ \
                 correct: %b@ @ @]@."
        pp_print_int_list l1
        pp_print_int_list l2
        pp_print_int_list r
        (r = [12; 13; 5; 10])

let _ = let sg = sums g_example in
        printf "@[<v 4>11: sums g_example:@ \
                value:    %a@ \
                expected: [11; 13; 9; 17]@ \
                correct: %b@ @ @]@."
          pp_print_int_list sg
          (sg = [11; 13; 9; 17])

let _ = let pg = solve g_example in
        printf "@[<v 4>12: solve g_example:@ \
                value:    %a@ \
                expected: [3; 0; 0]@ \
                correct: %b@ @ @]@."
          pp_print_int_list pg
          (pg = [3; 0; 0])


 let _ = let pg = solve g2 in
        printf "@[<v 4>solve g2:@ \
                value:    %a@ \
                expected: [3; 4; 0]@ \
                correct: %b@ @ @]@."
         pp_print_int_list pg
         (pg = [3; 4; 0])

## Exo 5

Exemple de copie:

let rec fibo = function
  | 0 -> 0
  | 1 -> 1
  | n when n < 0 -> failwith "fibo: argument must be nonnegative"
  | n -> fibo (n-1) + fibo (n-2)

let count = ref 0

let rec fibocount n =
  count := !count +1;
  match n with
  | 0 -> 0
  | 1 -> 1
  | n when n < 0 -> failwith "fibo: argument must be nonnegative"
  | n -> fibocount (n-1) + fibocount (n-2)

(*
Si on note C(n) la valeur de `count` apres l'appel `fibocount n`,
on remarque C(n+2) = C(n+1) + C(n) + 1. On peut d'ailleurs le prouver
en remarquant que cela correspond a la somme de
- l'appel actuel `fibocount (n+2)`
- les C(n+1) appels recursifs causes par `fibocount (n+2-1)`
- les C(n) appels recursifs causes par `fibocount (n+2-2)`
Puisque C(0) = C(1) = 1, on remarque que C(n) > fibo(n) pour tout n.
Or, au voisinage de l'infini, fibo(n) ~ phi^n.
Donc le nombre d'appel recursif de `fibo n` est (au moins) exponentiel en `n`.
*)

let f = Array.make 1024 (-1);;

let rec memofibocount n =
  count := !count + 1;
  match n with
  | 0 -> 0
  | 1 -> 1
  | n when n < 0 -> failwith "fibo: argument must be nonnegative"
  | n -> fibocheck (n-1) + fibocheck (n-2)
and fibocheck i =
  if f.(i) = -1 then f.(i) <- memofibocount i;
  f.(i)

(*
Si on note C(n) la valeur de `count` apres l'appel `memofibocount n`,
on remarque C(n) = n+1. En effet avec cette version, on ne calcule jamais deux
fois le meme terme de la suite, puisque tout terme calcule est immediatement
memorise.
*)

(* Pour les tests depuis l'interpreteur *)
let reinit () =
  count := 0;
  for i = 0 to 1023 do
    f.(i) <- -1
  done