Callcc/Guyslain/Teaching/ProgFonc/TP2015/TD4-2015

Version & licenses
Creative Commons License
  1. {`author "Guyslain Naves"}
  2. {`date "Mars 2015"}
  3. {`windowtitle "Programmation Fonctionnelle, TD5"}
  4. {`frametitle "Programmation Fonctionnelle, TD5 : Listes et types algébriques."}
  5. {`menu "progfonc"}


  6. {section 4 Exercice 1 : Ensembles par des listes}

  7. (Pour ceux qui sont en avance seulement.)

  8. Dans cet exercice, nous cherchons à coder des ensembles mathématiques comme des listes.
  9. Chaque liste devra toujours contenir des éléments distincts deux-à-deux. On vous demande de coder les valeurs suivantes :
  10. {code {`language "caml"} {:
  11. (** l'ensemble vide *)
  12. val empty_set : 'a list

  13. (** [contains elt set] évalue si [set] contient [elt] *)
  14. val contains : 'a -> 'a list -> bool

  15. (** [union set1 set2] est l'ensemble union de [set1] et [set2] *)
  16. val union : 'a list -> 'a list -> 'a list

  17. (** [intersection set1 set2] est l'ensemble intersection de [set1] et [set2] *)
  18. val intersection : 'a list -> 'a list -> 'a list

  19. (** [difference set1 set2] est l'ensemble des éléments de [set1] qui ne sont pas dans [set2] *)
  20. val difference : 'a list -> 'a list -> 'a list

  21. (** [symmetric_difference set1 set2 est l'ensemble des éléments apparaissant
  22. dans [set1] ou [set2], mais pas dans les deux à la fois *)
  23. val symmetric_difference : 'a list -> 'a list -> 'a list

  24. (** [subset set1 set2] évalue si [set1] est un sous-ensemble dans [set2] *)
  25. val subset : 'a list -> 'a list -> bool

  26. :}}


  27. {section 4 Exercice 2 : Nombres binaires sans chiffre '0'}

  28. Nous allons coder les entiers sans le chiffre '0', mais seulement avec les chiffres '1' et '2'. Ainsi, on peut montrer que tout nombre naturel $n$ se décompose en $n = \sum_{i=0}^k \alpha_i 2^i$, pour un certain choix de $\alpha_i \in \{1,2\}$.

  29. Par exemple, $0 = \sum_{i=0}^{-1} 1 \cdot 2^{i}$, et $8 = 2 \cdot 2^0 + 1 \cdot 2^1 + 1 \cdot 2^2$, etc. Étant donné que les bits ont toujours pour valeurs des puissances de 2, on peut considérer, selon la valeur du dernier bit, qu'un entier vaut soit $1$ plus le double d'un entier, soit $2$ plus le double d'un entier, soit $0$.

  30. + Proposer un type algébrique inductif pour les entiers naturels, ainsi codés. (utiliser un cas spécial pour coder l'{emph entier} $0$).
  31. + Écrire une fonction {verb {:succ:}}, qui à $n$ associe $n+1$.
  32. + Coder l'addition de deux entiers.


  33. {section 4 Exercice 3 : Les arbres enracinés}

  34. Nous souhaitons travailler avec des arbres d'arités arbitraires, dont les feuilles sont des entiers. Les nœuds internes ne possèdent pas d'information, sinon la liste de leurs fils.

  35. + Proposer un type pour encoder les arbres enracinés.
  36. + Écrire une fonction prenant deux arbres enracinés, qui les lie avec une nouvelle racine ayant pour fils ces deux arbres.
  37. + Écrire une fonction prenant une liste d'entiers, et qui construit un arbre enraciné dont les feuilles sont les éléments de la liste. L'arbre ainsi construit doit avoir une hauteur de $1$.
  38. + Écrire une fonction qui calcule la somme des feuilles d'un arbre enraciné.
  39. + Enfin, écrire une fonction {verb {:map:}}, qui applique une fonction passée en argument à chaque feuille, et renvoie l'arbre enraciné de même forme avec les images de la fonction en feuilles.

  40. {section 4 Exercice 4 : Le type option}

  41. Le module Pervasive fournit un type bien utile, le type option permettant de coder une valeur optionnelle :
  42. {code {`language "ocaml"} {:
  43. type 'a option =
  44. | None
  45. | Some of 'a
  46. :}}

  47. + {subframe
  48. coder une fonction qui filtre les options d'une liste, pour garder uniquement les valeurs définies :
  49. {code {`language "ocaml"} {:
  50. val option_filter : 'a option list -> 'a list
  51. :}}
  52. }
  53. + {subframe quel est le type de la fonction suivante ?
  54. {code {`language "ocaml"} {:
  55. let (>>=) e f = match e with
  56. | None -> None
  57. | Some v -> f v
  58. :}}
  59. }
  60. + Utiliser {verb {:>>=:}} pour coder une fonction prenant trois arguments de type {verb {:int option:}}, et qui renvoie une option contenant la somme des trois entiers, s'ils sont définis, ou {verb {:None:}} sinon.
  61. + Coder une fonction {verb {:find : ('a -> bool) -> 'a list -> 'a option:}}, qui calcule le premier élément d'une liste vérifiant un prédicat. {verb {:find:}} calcule une option car il se peut qu'aucun élément de la liste ne vérifie le prédicat.