Callcc/Guyslain/Teaching/ProgFonc/TP2018/TD5

Version & licenses
Creative Commons License
  1. {`author "Guyslain Naves"}
  2. {`date "Janvier 2018"}
  3. {`windowtitle "Programmation Fonctionnelle, TD5"}
  4. {`frametitle "Programmation Fonctionnelle, TD5 : Types algébriques."}
  5. {`menu "progfonc"}
  6. {`leftpicture af://guyslain/images/Teaching/ProgFonc/ReingoldTilford/random_tree_v4_1.svg}

  7. {section 4 Exercice 1 : Le type option}

  8. Le module {verb {:Pervasives:}} fournit un type bien utile, le type
  9. {verb {:option:}}, permettant de représenter une valeur optionnelle :

  10. {code {`language "ocaml"} {:
  11. type 'a option =
  12. | None
  13. | Some of 'a
  14. :}}

  15. + {subframe Créez une fonction qui filtre les options d'une liste,
  16. pour garder uniquement les valeurs définies :
  17. {code {`language "ocaml"} {:
  18. val concat_option : 'a option list -> 'a list
  19. :}}
  20. }
  21. + {subframe Quel est le type de la fonction suivante ?
  22. {code {`language "ocaml"} {:
  23. let (>>=) opt fct = match opt with
  24. | None -> None
  25. | Some thing -> fct thing
  26. :}}
  27. }
  28. + Utilisez {verb {:>>=:}} pour coder une fonction prenant trois
  29. arguments de type {verb {:int option:}}, et qui renvoie une option
  30. contenant la somme des trois entiers, s'ils sont définis, ou {verb
  31. {:None:}} sinon.
  32. + Écrivez une fonction {verb {:map : ('elt -> 'im) -> 'elt option ->
  33. 'im option:}}. Proposez une version utilisant un filtrage par motif, et
  34. une version utilisant uniquement {verb {:(>>=):}}.
  35. + Écrivez une fonction {verb {:find : ('elt -> bool) -> 'elt list ->
  36. 'elt option:}}, qui calcule le premier élément d'une liste vérifiant
  37. un prédicat. {verb {:find:}} calcule une option car il se peut
  38. qu'aucun élément de la liste ne vérifie le prédicat.


  39. {section 4 Exercice 2 : Des automates.}

  40. {figure af://guyslain/images/Teaching/ProgFonc/auto-div-3.png Deux automates.}

  41. On souhaite réaliser l'automate de gauche.

  42. + Proposer un type pour l'alphabet du langage de l'automate de gauche.
  43. + Proposer un type pour les états de cet automate.
  44. + Définir une fonction de transition, prenant un état initial, une
  45. lettre, et retournant l'état d'arrivée.
  46. + Ajouter un prédicat déterminant si un état est final.
  47. + Définir la fonction qui prenant une liste de lettres, détermine si
  48. le mot correspondant est reconnu par l'automate.
  49. + Améliorer cette solution pour réaliser l'automate de droite. C'est
  50. plus difficile car il est non-déterministe. La fonction de transition
  51. doit donc prendre une liste d'états et retourner une liste d'états.



  52. {section 4 Exercice 3 : Nombres binaires sans chiffre '0'.}

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

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

  62. + Proposez un type algébrique inductif pour les entiers naturels,
  63. ainsi encodés (utilisez un cas spécial pour représenter l'{emph entier} $0$).
  64. + Écrivez une fonction {verb {:succ:}}, qui à $n$ associe $n+1$.
  65. + Programmez l'addition de deux entiers sous cette représentation.


  66. {section 4 Exercice 4 : Les listes récursivement.}

  67. Implémentez les fonctions suivantes avec des récursions et du filtrage
  68. par motifs.

  69. {code {`language "ocaml"} {:
  70. (** [last] returns the last element in the list, optionally *)
  71. val last : 'elt list -> 'elt option

  72. (** [cut i list] cuts a list into two parts, its prefix of length [i],
  73. and the suffix of all the elements that remain.
  74. *)
  75. val cut : int -> 'elt list -> 'elt list * 'elt list

  76. (** [remove_odd_positions] returns the list of elements in even position,
  77. remove_odd_positions [e0;e1;e2;...;en] = [e0;e2;e4;...]
  78. *)
  79. val remove_odd_positions : 'elt list -> 'elt list

  80. (** [intersperse] adds an element between any two consecutive elements of the list,
  81. intersperse 1 [2;3;4;1;5] = [2;1;3;1;4;1;1;1;5]
  82. *)
  83. val intersperse : 'elt -> 'elt list -> 'elt list

  84. (** [list_consecutive_pairs l] returns the list of all pairs of elements
  85. that are consecutive in [l].
  86. list_consecutive_pairs [e0;e1;e2;...] = [(e0,e1);(e1,e2);...]
  87. *)
  88. val list_consecutive_pairs : 'elt list -> ('elt * 'elt) list

  89. (** [list_suffixes list] is the list of all the suffixes of [list].
  90. list_suffixes [e0;e1;e2;e3;...] = [[e0;e1;e2;...];[e1;e2;e3;...];...]
  91. *)
  92. val list_suffixes : 'elt list -> 'elt list list
  93. :}}