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.

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 (...)
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]