Semaine 2 – Types sommes (sans paramètre)

photo en CC-By-Nc-Sa par MTSOfan

, par Pierre

Types sommes en caml et types inductifs (sans variable de type en paramètre). Comparaison avec les types unions en C.

  1. (* cours 2 : les types sommes (sans paramètre) *)
  2.  
  3. (* Définir des jours de la semaine *)
  4. type jour =
  5.   | Lundi
  6.   | Mardi
  7.   | Mercredi
  8.   | Jeudi
  9.   | Vendredi
  10.   | Samedi
  11.   | Dimanche;;
  12.  
  13. (* est-ce un jour travaillé ? *)
  14. let travail = function
  15.   | Samedi -> false
  16.   | Dimanche -> false
  17.   | _ -> true;;
  18.  
  19. travail Mardi;;
  20.  
  21. (* Définir des nombres très généralement *)
  22. type nombre =
  23.   | Entier of int
  24.   | Flottant of float
  25.   | Complexe of float * float;;
  26.  
  27. let x = Entier 3;;
  28. let y = Flottant 1.2;;
  29. let z = Complexe (-0.2, 1.0);;
  30.  
  31. let estEntier = function
  32.   | Entier _ -> true
  33.   | _ -> false;;
  34.  
  35. let estComplexe = function
  36.   | Complexe _ -> true
  37.   | _ -> false;;
  38.  
  39. estEntier x;;
  40. estEntier y;;
  41. estEntier z;;
  42.  
  43. estComplexe x;;
  44. estComplexe y;;
  45. estComplexe z;;
  46.  
  47. 3 + 4;;
  48. 3. +. 4.;;
  49. let z = 1;;
  50. (float) z +. 4.;;
  51.  
  52. (* extraction de la partie reelle *)
  53. let partieReelle = function
  54.   | Entier x -> (float) x
  55.   | Flottant y -> y
  56.   | Complexe (x, y) -> x;;
  57.  
  58. z;;
  59. partieReelle z;;
  60.  
  61. (* TODO extraction de la partie imaginaire *)
  62.  
  63. (* addition des nombres *)
  64. let addition = function
  65.   | (Entier x, Entier y) -> Entier (x + y)
  66.   | (Flottant x, Flottant y) -> Flottant (x +. y)
  67.   | (Complexe(x,y), Complexe(l,m)) -> Complexe((x+.l),(y+.m))
  68.   | (Entier x, Flottant y) -> Flottant ((float) x +. y)
  69.   | (Flottant y, Entier x) -> Flottant ((float) x +. y)
  70.   | (Complexe(x,y) , z) -> Complexe ( (x +. partieReelle z),y)
  71.   | (z,Complexe(x,y) ) -> Complexe( (x+. partieReelle z),y)
  72. ;;
  73.  
  74. addition (x, y);;
  75. addition (x, z);;
  76. addition (z, z);;
  77.  
  78. (* un type somme récursif: celui des listes d'entiers *)
  79. type listeEntier =
  80.   | Vide
  81.   | Cons of int * listeEntier;;
  82.  
  83. exception ListeVide;;
  84. let teteLE = function
  85.   | Vide -> raise ListeVide
  86.   | Cons(x,l) -> x
  87. ;;
  88.  
  89. let maliste = (Cons(4,Cons(5,Cons(6,Vide))));;
  90.  
  91. teteLE maliste;;
  92.  
  93. let queueLE = function
  94.   | Vide -> raise ListeVide
  95.   | Cons(x,l) -> l
  96. ;;
  97.  
  98. queueLE maliste;;
  99.  
  100. let rec concatenerLE = function
  101.   | (l, Vide) -> l
  102.   | (Vide, l) -> l
  103.   | (Cons(x,l), m) -> Cons(x,concatenerLE (l,m))
  104. ;;
  105.  
  106. let maliste2 = Cons(12,Cons(14,Vide));;
  107.  
  108. concatenerLE (maliste,maliste2);;
  109.  
  110. let rec maxLE = function
  111.   | Vide -> raise ListeVide
  112.   | Cons(x, Vide) -> x
  113.   | Cons(x,l) -> max x (maxLE l)
  114. ;;
  115.  
  116. maxLE maliste;;
  117. maxLE (concatenerLE (maliste,maliste2));;
  118.  
  119. let rec cardinalLE = function
  120.   | Vide -> 0
  121.   | Cons(x,l) -> 1 + cardinalLE l
  122. ;;
  123.  
  124. cardinalLE maliste;;
  125.  
  126. let rec mapLE = function
  127.   | (f,Vide) -> Vide
  128.   | (f,Cons(tete,queue)) -> Cons( f(tete), mapLE(f, queue));;
  129.  
  130. mapLE ((function x -> x + 100), maliste);;
  131.  
  132. (* Un type des arbres binaires d'entiers *)
  133. type arbreBin =
  134.   | Feuille
  135.   | Noeud of arbreBin * int * arbreBin;;
  136.  
  137. (* exemples d'arbres *)
  138. let monarbre0 = Noeud (Feuille, 3, Feuille);;
  139. let monarbre1 = Noeud (monarbre0, 4, monarbre0);;
  140. let moyenarbre =
  141.   Noeud (Noeud (Feuille, 50, Noeud (Feuille, 32, Feuille)), 10,
  142.          Noeud (Noeud (Feuille, 34, Feuille), 20, Noeud (Feuille, 29, Feuille)));;
  143. let grandarbre =
  144.   Noeud (Noeud (Noeud (Feuille, 10, Noeud (Feuille, 20, Noeud (Feuille, 30, Feuille))), 40, Feuille), 50,
  145.          Noeud (Feuille, 60,
  146.                 Noeud (Noeud (Feuille, 70, Noeud (Feuille, 80, Feuille))
  147.                       , 90, Feuille)));;
  148.  
  149. (* TODO faire un autre exemple d'arbre *)
  150.  
  151.  
  152. (* nombre d'entiers dans l'arbre *)
  153. let rec cardinalAB = function
  154.   | Feuille -> 0
  155.   | Noeud (gauche, x, droite) -> cardinalAB(gauche) + 1 + cardinalAB(droite);;
  156.  
  157. cardinalAB grandarbre;;
  158.  
  159. (* somme des entiers dans l'arbre *)
  160. let rec sommeAB = function
  161.   | Feuille -> 0
  162.   | Noeud (gauche, x, droite) -> sommeAB(gauche) + x + sommeAB(droite);;
  163.  
  164. sommeAB grandarbre;;
  165.  
  166. (* parcoursInfixeAB *)
  167.  
  168. (* exemple:
  169. Si l'arbre est moyenarbre
  170. 10 -- 20 -- 29
  171.  |    |
  172.  |    34
  173.  |
  174. 50 -- 32
  175. Son parcours infixe est la liste:
  176. [50; 32; 10; 34; 20; 29]
  177. *)
  178.  
  179. let rec parcoursInfixeAB = function
  180.   | Feuille->Vide
  181.   | Noeud (gauche,x,droit) ->
  182.      concatenerLE(parcoursInfixeAB(gauche),
  183.                   Cons (x, parcoursInfixeAB(droit)));;
  184.  
  185. parcoursInfixeAB moyenarbre;;
  186.  
  187.  
  188. (* TODO le plus grand entier de l'arbre *)
  189. let rec maxAB = function
  190.   | _ -> 0;;
  191.  
  192. (* TODO hauteur de l'arbre *)
  193.  
  194. (* TODO map sur les arbres *)
  195.  
  196. mapAB (function x -> x + 1) moyenarbre;;
  197.  
  198. (* TODO affichage simple des arbres binaires *)
  199. let rec afficherABligne = function
  200.   | Feuille -> print_string "."
  201.   | _ -> ();;
  202.  
  203. afficherABligne moyenarbre;;
  204. (* ((., 50, (., 32, .)), 10, ((., 34, .), 20, (., 29, .))) *)
  205.  
  206. (* TODO si l'arbre binaire a la propriété d'être un arbre de recherche, contient-il l'entier n ?*)
  207. let rec rechercherAB n = function
  208.   | Feuille -> false
  209.   | _ -> false;;
  210.  
  211. rechercherAB 20 grandarbre;; (* true *)
  212. rechercherAB 57 grandarbre;; (* false *)
  213.  
  214. (* TODO insertion d'un entier dans un arbre binaire de recherche *)
  215.  
  216. (* TODO suppression d'un entier dans un arbre binaire de recherche *)
  217.  
  218. (* TODO difficile faire un affichage plus joli des arbres binaires *)
  219.  
  220. (* Exemple.
  221. Si l'arbre est:
  222. Noeud (Feuille, 12, Noeud (Noeud (Feuille, 50, Noeud (Feuille, 32, Feuille)), 10,Noeud
  223. (Noeud (Feuille, 34, Feuille), 20,Noeud (Feuille, 29, Feuille))))
  224.  
  225. Son affichage sera:
  226. 12 -- 10 -- 20 -- 29
  227.        |    |
  228.        |    34
  229.        |
  230.       50 -- 32
  231.  *)
  232.  
  233. (*
  234. Suggestions :
  235. 1) utiliser une fonction afficher_indentation pour
  236. indenter les lignes. Par exemple:
  237. afficher_indentation [false; true; true; false; true; false; false];
  238. print_int 12;
  239. print_string "\n"
  240. ;;
  241. affichera:
  242.                  |           |     |          12
  243. 2) définir un affichage prenant en entrée une liste de booléens et un arbre...
  244. *)

Télécharger

Type somme (non tagué) en C et tag par constante symbolique.

  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. #define ENTIER 0
  4. #define FLOTTANT 1
  5. typedef union {
  6.   int entier; // 4 octets
  7.   double flottant; // 8 octets
  8. } nombre; // 8 octets
  9.  
  10. void afficher_nombre(nombre x, int type) {
  11.   printf("Nombre = ");
  12.   if (type == FLOTTANT) {
  13.     printf("%lg\n", x.flottant);
  14.   } else {
  15.     printf("%d\n", x.entier);
  16.   }
  17. }
  18. int main() {
  19.   nombre x;
  20.   x.entier = 5;
  21.   x.flottant = 3.2; // on a écrasé l'entier
  22.   afficher_nombre(x, FLOTTANT);
  23.   afficher_nombre(x, ENTIER);
  24.   return EXIT_SUCCESS;
  25. }

Télécharger

Exercices : les TODO ci-dessus. Y ajouter les autres fonctions usuelles sur les arbres binaires et comparer avec une implémentation en C.

Recherche

Enseignement

Administration

Curriculum Vitæ [pdf]
Comment me contacter

Autres réalisations (logiciels, etc.)

Thymio, Python et Asebamedulla
des QCM en ligne grâce à org-mode (et jQuery, et MathJax), org-mode [org, html, css]

Café

Enseigner la programmation
Revenu et logement, Je livre ici quelques éléments de comparaison concernant mon niveau de vie, pour couper court à quelques idées reçues, et un condensé de nombreuses (...)
Revenu et travail d’un enseignant-chercheur, Cet article complète l'article Revenu et logement, en détaillant un peu le budget de mon ménage, mon parcours d'enseignant-chercheur en terme de (...)
Paris 13 Villetaneuse, pas encore la vélorution !
Cybersyn (el systemo synco), Au café, mardi 5 avril 2011, j'ai bien vu que, mis à part Antoine Allombert, personne ne connaissait l'histoire de l'extraordinaire projet chilien (...) [jpg, jpg, png]

Divers

Affiche CiE 2016
Augmenter l’espace de stockage d’un hote GNU/Linux (VirtualBox etc.)
AperoTIC sur les réseaux sociaux
ADULLACT, Pour être un peu moins seul à défendre l'usage et le développement de logiciels libres dans mon travail (et autour), j'ai adhéré à l'ADULLACT en tant (...)
Hacker l’éducation (Open bidouille camp 2 // Fac lab de Gennevilliers)
Expo : et l’Homme… créa le robot
MathJax
Onglets dans un rapport $\LaTeX$ [gz, png, pdf, gz]
Logo LIPN et accessoires [svg, svg, png, tex, pdf, tif, zip, png, eps, svg]
Ventilo pour ibook (retrouvé) [jpg]