Semaine 2 – Types sommes (sans paramètre)

(* cours 2 : les types sommes (sans paramètre) *)
 
(* Définir des jours de la semaine *)
type jour =
  | Lundi
  | Mardi
  | Mercredi
  | Jeudi
  | Vendredi
  | Samedi
  | Dimanche;;
 
(* est-ce un jour travaillé ? *)
let travail = function
  | Samedi -> false
  | Dimanche -> false
  | _ -> true;;
 
travail Mardi;;
 
(* Définir des nombres très généralement *)
type nombre =
  | Entier of int
  | Flottant of float
  | Complexe of float * float;;
 
let x = Entier 3;;
let y = Flottant 1.2;;
let z = Complexe (-0.2, 1.0);;
 
let estEntier = function
  | Entier _ -> true
  | _ -> false;;
 
let estComplexe = function
  | Complexe _ -> true
  | _ -> false;;
 
estEntier x;;
estEntier y;;
estEntier z;;
 
estComplexe x;;
estComplexe y;;
estComplexe z;;
 
3 + 4;;
3. +. 4.;;
let z = 1;;
(float) z +. 4.;;
 
(* extraction de la partie reelle *)
let partieReelle = function
  | Entier x -> (float) x
  | Flottant y -> y
  | Complexe (x, y) -> x;;
 
z;;
partieReelle z;;
 
(* TODO extraction de la partie imaginaire *)
 
(* addition des nombres *)
let addition = function
  | (Entier x, Entier y) -> Entier (x + y)
  | (Flottant x, Flottant y) -> Flottant (x +. y)
  | (Complexe(x,y), Complexe(l,m)) -> Complexe((x+.l),(y+.m))
  | (Entier x, Flottant y) -> Flottant ((float) x +. y)
  | (Flottant y, Entier x) -> Flottant ((float) x +. y)
  | (Complexe(x,y) , z) -> Complexe ( (x +. partieReelle z),y)
  | (z,Complexe(x,y) ) -> Complexe( (x+. partieReelle z),y)
;;
 
addition (x, y);;
addition (x, z);;
addition (z, z);;
 
(* un type somme récursif: celui des listes d'entiers *)
type listeEntier =
  | Vide
  | Cons of int * listeEntier;;
 
exception ListeVide;;
let teteLE = function
  | Vide -> raise ListeVide
  | Cons(x,l) -> x
;;
 
let maliste = (Cons(4,Cons(5,Cons(6,Vide))));;
 
teteLE maliste;;
 
let queueLE = function
  | Vide -> raise ListeVide
  | Cons(x,l) -> l
;;
 
queueLE maliste;;
 
let rec concatenerLE = function
  | (l, Vide) -> l
  | (Vide, l) -> l
  | (Cons(x,l), m) -> Cons(x,concatenerLE (l,m))
;;
 
let maliste2 = Cons(12,Cons(14,Vide));;
 
concatenerLE (maliste,maliste2);;
 
let rec maxLE = function
  | Vide -> raise ListeVide
  | Cons(x, Vide) -> x
  | Cons(x,l) -> max x (maxLE l)
;;
 
maxLE maliste;;
maxLE (concatenerLE (maliste,maliste2));;
 
let rec cardinalLE = function
  | Vide -> 0
  | Cons(x,l) -> 1 + cardinalLE l
;;
 
cardinalLE maliste;;
 
let rec mapLE = function
  | (f,Vide) -> Vide
  | (f,Cons(tete,queue)) -> Cons( f(tete), mapLE(f, queue));;
 
mapLE ((function x -> x + 100), maliste);;
 
(* Un type des arbres binaires d'entiers *)
type arbreBin =
  | Feuille
  | Noeud of arbreBin * int * arbreBin;;
 
(* exemples d'arbres *)
let monarbre0 = Noeud (Feuille, 3, Feuille);;
let monarbre1 = Noeud (monarbre0, 4, monarbre0);;
let moyenarbre =
  Noeud (Noeud (Feuille, 50, Noeud (Feuille, 32, Feuille)), 10,
         Noeud (Noeud (Feuille, 34, Feuille), 20, Noeud (Feuille, 29, Feuille)));;
let grandarbre =
  Noeud (Noeud (Noeud (Feuille, 10, Noeud (Feuille, 20, Noeud (Feuille, 30, Feuille))), 40, Feuille), 50,
         Noeud (Feuille, 60,
                Noeud (Noeud (Feuille, 70, Noeud (Feuille, 80, Feuille))
                      , 90, Feuille)));;
 
(* TODO faire un autre exemple d'arbre *)
 
 
(* nombre d'entiers dans l'arbre *)
let rec cardinalAB = function
  | Feuille -> 0
  | Noeud (gauche, x, droite) -> cardinalAB(gauche) + 1 + cardinalAB(droite);;
 
cardinalAB grandarbre;;
 
(* somme des entiers dans l'arbre *)
let rec sommeAB = function
  | Feuille -> 0
  | Noeud (gauche, x, droite) -> sommeAB(gauche) + x + sommeAB(droite);;
 
sommeAB grandarbre;;
 
(* parcoursInfixeAB *)
 
(* exemple:
Si l'arbre est moyenarbre
10 -- 20 -- 29
 |    |
 |    34
 |
50 -- 32
Son parcours infixe est la liste:
[50; 32; 10; 34; 20; 29]
*)
 
let rec parcoursInfixeAB = function
  | Feuille->Vide
  | Noeud (gauche,x,droit) ->
     concatenerLE(parcoursInfixeAB(gauche),
                  Cons (x, parcoursInfixeAB(droit)));;
 
parcoursInfixeAB moyenarbre;;
 
 
(* TODO le plus grand entier de l'arbre *)
let rec maxAB = function
  | _ -> 0;;
 
(* TODO hauteur de l'arbre *)
 
(* TODO map sur les arbres *)
 
mapAB (function x -> x + 1) moyenarbre;;
 
(* TODO affichage simple des arbres binaires *)
let rec afficherABligne = function
  | Feuille -> print_string "."
  | _ -> ();;
 
afficherABligne moyenarbre;;
(* ((., 50, (., 32, .)), 10, ((., 34, .), 20, (., 29, .))) *)
 
(* TODO si l'arbre binaire a la propriété d'être un arbre de recherche, contient-il l'entier n ?*)
let rec rechercherAB n = function
  | Feuille -> false
  | _ -> false;;
 
rechercherAB 20 grandarbre;; (* true *)
rechercherAB 57 grandarbre;; (* false *)
 
(* TODO insertion d'un entier dans un arbre binaire de recherche *)
 
(* TODO suppression d'un entier dans un arbre binaire de recherche *)
 
(* TODO difficile faire un affichage plus joli des arbres binaires *)
 
(* Exemple.
Si l'arbre est:
Noeud (Feuille, 12, Noeud (Noeud (Feuille, 50, Noeud (Feuille, 32, Feuille)), 10,Noeud
(Noeud (Feuille, 34, Feuille), 20,Noeud (Feuille, 29, Feuille))))
 
Son affichage sera:
12 -- 10 -- 20 -- 29
       |    |
       |    34
       |
      50 -- 32
 *)
 
(*
Suggestions :
1) utiliser une fonction afficher_indentation pour
indenter les lignes. Par exemple:
afficher_indentation [false; true; true; false; true; false; false];
print_int 12;
print_string "\n"
;;
affichera:
                 |           |     |          12
2) définir un affichage prenant en entrée une liste de booléens et un arbre...
*)