Accueil > Enseignement > Anciens cours (avant 2015-2016) > Programmation fonctionnelle (L3, 2013-2014) > Semaine 2 – Types sommes (sans paramètre)

Semaine 2 – Types sommes (sans paramètre)

mardi 4 février 2014, par Pierre

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 =
  | 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...
*)

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) {
  printf("Nombre = ");
  if (type == FLOTTANT) {
    printf("%lg\n", x.flottant);
  } else {
    printf("%d\n", x.entier);
  }
}
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.

Semaine 2 – Types sommes (sans paramètre)

Portfolio