Programmation Fonctionnelle, TD5

Htmligure
Version & licenses
Creative Commons License

Programmation Fonctionnelle, TD5 : Types algébriques.

Guyslain Naves

Exercice 1 : Le type option

Le module Pervasives fournit un type bien utile, le type option, permettant de représenter une valeur optionnelle :

  1. type 'a option =
  2. | None
  3. | Some of 'a
  1. Créez une fonction qui filtre les options d'une liste, pour garder uniquement les valeurs définies :

    1. val concat_option : 'a option list -> 'a list
  2. Quel est le type de la fonction suivante ?

    1. let (>>=) opt fct = match opt with
    2. | None -> None
    3. | Some thing -> fct thing
  3. Utilisez >>= pour coder une fonction prenant trois arguments de type int option, et qui renvoie une option contenant la somme des trois entiers, s'ils sont définis, ou None sinon.
  4. Écrivez une fonction map : ('elt -> 'im) -> 'elt option -> 'im option. Proposez une version utilisant un filtrage par motif, et une version utilisant uniquement (>>=).
  5. Écrivez une fonction find : ('elt -> bool) -> 'elt list -> 'elt option, qui calcule le premier élément d'une liste vérifiant un prédicat. find calcule une option car il se peut qu'aucun élément de la liste ne vérifie le prédicat.

Exercice 2 : Des automates.

Deux automates.

On souhaite réaliser l'automate de gauche.

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

Exercice 3 : Nombres binaires sans chiffre '0'.

Nous allons représenter 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\}$.

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$.

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

Exercice 4 : Les listes récursivement.

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

  1. (** [last] returns the last element in the list, optionally *)
  2. val last : 'elt list -> 'elt option

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

  7. (** [remove_odd_positions] returns the list of elements in even position,
  8. remove_odd_positions [e0;e1;e2;...;en] = [e0;e2;e4;...]
  9. *)
  10. val remove_odd_positions : 'elt list -> 'elt list

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

  15. (** [list_consecutive_pairs l] returns the list of all pairs of elements
  16. that are consecutive in [l].
  17. list_consecutive_pairs [e0;e1;e2;...] = [(e0,e1);(e1,e2);...]
  18. *)
  19. val list_consecutive_pairs : 'elt list -> ('elt * 'elt) list

  20. (** [list_suffixes list] is the list of all the suffixes of [list].
  21. list_suffixes [e0;e1;e2;e3;...] = [[e0;e1;e2;...];[e1;e2;e3;...];...]
  22. *)
  23. val list_suffixes : 'elt list -> 'elt list list