Semaine 2 – Types sommes (sans paramètre)

photo en CC-By-Nc-Sa par MTSOfan
, par
Types sommes en caml et types inductifs (sans variable de type en paramètre). Comparaison avec les types unions en C.
- (* 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 =
- 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;;
- (* extraction de la partie reelle *)
- let partieReelle = function
- | 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))
- | (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
- 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
- ;;
- 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
- (* 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
- | _ -> ();;
- 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...
- *)
Type somme (non tagué) en C et tag par constante symbolique.
- #include <stdlib.h>
- #include <stdio.h>
- #define ENTIER 0
- #define FLOTTANT 1
- typedef union {
- int entier; // 4 octets
- double flottant; // 8 octets
- } nombre; // 8 octets
- void afficher_nombre(nombre x, int type) {
- if (type == FLOTTANT) {
- } else {
- }
- }
- int main() {
- nombre x;
- x.entier = 5;
- x.flottant = 3.2; // on a écrasé l'entier
- afficher_nombre(x, FLOTTANT);
- afficher_nombre(x, ENTIER);
- return EXIT_SUCCESS;
- }
Exercices : les TODO ci-dessus. Y ajouter les autres fonctions usuelles sur les arbres binaires et comparer avec une implémentation en C.