Programmation Fonctionnelle, TD4

Exercice 1 : Ensembles par des listes

(Pour ceux qui sont en avance seulement.)

Dans cet exercice, nous cherchons à coder des ensembles mathématiques comme des listes. Chaque liste devra toujours contenir des éléments distincts deux-à-deux. On vous demande de coder les valeurs suivantes :

(** l'ensemble vide *)
val empty_set : 'a list
(** [contains elt set] évalue si [set] contient [elt] *)
val contains : 'a -> 'a list -> bool
(** [union setA setB] est l'ensemble union de [setA] et [setB] *)
val union : 'a list -> 'a list -> 'a list
(** [intersection setA setB] est l'ensemble intersection de [setA] et [setB] *)
val intersection : 'a list -> 'a list -> 'a list
(** [difference setA setB] est l'ensemble des éléments de [setA] qui ne sont pas dans [setB] *)
val difference : 'a list -> 'a list -> 'a list
(** [symmetric_difference setA setB est l'ensemble des éléments apparaissant
dans [setA] ou [setB], mais pas dans les deux à la fois *)
val symmetric_difference : 'a list -> 'a list -> 'a list
(** [subset setA setB] évalue si [setA] est un sous-ensemble dans [setB] *)
val subset : 'a list -> 'a list -> bool

Exercice 2 : Nombres binaires sans chiffre '0 '

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

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

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

Exercice 3 : Les arbres enracinés

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.

Proposer un type pour encoder les arbres enracinés.
Écrire une fonction prenant deux arbres enracinés, qui les lie avec une nouvelle racine ayant pour fils ces deux arbres.
É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$.
Écrire une fonction qui calcule la somme des feuilles d'un arbre enraciné.
Enfin, écrire une fonction 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.

Exercice 4 : Le type option

Le module Pervasive fournit un type bien utile, le type option permettant de coder une valeur optionnelle :

type 'a option =
| None
| Some of 'a

coder une fonction qui filtre les options d'une liste, pour garder uniquement les valeurs définies :
1. val option_filter : 'a option list -> 'a list
quel est le type de la fonction suivante ?
1. let (>>=) e f = match e with
2. | None -> None
3. | Some v -> f v
Utiliser >>= 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.
Coder une fonction find : ('a -> bool) -> 'a list -> 'a 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.