Université Paris 6
Licence d'informatique 		Module de Programmation
Année 1999-2000


Travaux dirigés n° 7





Exercice 1

Soit la fonction définie par : 
let  XX = function
| (0,_) -> 0
| (_,0) -> 5
| (1,x) -> x+50
| (x,1) -> x+35
|  _    -> 3 ;;

1. Typez cette déclaration.
2. Expliquez le calcul de : XX (0,1) ; XX (0,0) ; XX (1,0) ; XX (1,4) ; XX (4,1) ; XX (25,5).
3. Remplacez le filtre _ par (_,_) puis par (x,y) et déroulez le calcul de XX(25,5).
Exercice 2

Soit le type déclaré comme suit :

type arbre = Vid | N of arbre* int * arbre ;;


1. Typez les déclarations suivantes :

let exemple = N ( N(Vid, 5 ,Vid), 7, Vid);;

let foo = function
| Vid -> 0
| N(Vid,_,_) -> 0
| N(N (_, x,_), y, Vid) -> x + y
| N(N (_, x,_), y, N (_, z,_) ) -> x + y + z;;
Exercice 3

Soit le type essai défini comme suit : 
type essai = Vid | N of essai *int * bool ;;

1. Que pouvez-vous dire sur les identificateurs Vid et N introduits par cette définition de type?
2. Donnez deux exemples de valeur de type essai, construites de manières différentes.
3. Effectuez très soigneusement le typage de la fonction déclarée comme suit : 
let foo = function
| Vid -> Vid
| N (_, 0, _) -> Vid
| N (_, 1, b) -> N (Vid, 2, b)
| N(g, n, b) -> N(g, n+1, b)

4. Quelles sont la (ou les) hypothèse(s) à faire sur un environnement Env-Init pour pouvoir y évaluer l'expression foo (N (Vid, 6-10 , 4 = 2))? En supposant ces hypothèses vérifiées, expliquez rapidement le déroulement de l'évaluation de cette expression.
Rappels : une valeur polymorphe est une valeur dont le type contient des variables de types : 'a, 'b, etc... On obtient des valeurs polymorphes lorsqu'à l'issue des résolutions des contraintes engendrées par le processus d'inférence de type, subsistent des variables (de type).

Exercice 4

On a fst : 'a * 'b -> 'a et snd : 'a * 'b -> 'b.
Typez les fonctions définies comme suit : 
 let swap = function x -> (snd x, fst x);;
 let add = function x -> (snd x)+(fst x);;
 let cond_succ = function x -> if (fst x) then (snd x)+1 else (snd x);;
 let app_pair = function x -> function y -> (x (fst y), x (snd y));;
Exercice 5


1. Typez (rapidement) les fonctions déclarées par : 
let rec it = function f -> function a -> function n ->
if n=0 then a else (f (it f a (n-1)));;
it (map (fun x -> x + 3));;
On peut définir l'addition de n à m comme l'opération d'ajouter n fois 1 à m. En utilisant la fonction it, définissez une fonction add qui calcule la somme d'un entier n à un entier m.
2. De même, la multiplication de n par m peut s'écrire comme l'addition de m, n fois à lui-même. En supposant définie la fonction d'addition add, définissez la fonction de multiplication.
3. En utilisant le même principe, définissez la fonction d'exponentiation mn.
4. Écrivez une fonction qui rajoute un caractère devant une chaîne de caractères (cf bibliothèque string). Utilisez alors la fonction it pour définir une fonction mk_string, de type int -> string créant une chaîne de longueur spécifiée par l'argument et ne contenant que le caractère ` ` (par exemple (mk_string 3) vaudra " ").
Exercice 6

Typez la fonction suivante. En déduire la fonction it de l'exercice précédent. 
let rec_schema = function (b,d,f,a,n) ->
  if (b n) then a else f (rec_schema (b,d,f,a,(d n))) ;;
Exercice 7

Les membres d'une université peuvent être : soit des étudiants, soit des administratifs, soit des enseignants-chercheurs. Un étudiant est caractérisé par son nom et son numéro d'inscription. Un administratif est caractérisé par son nom et sa catégorie administrative, qui peut être A, B ou C. Un enseignant-chercheur est caractérisé par son nom et le numéro de l'UFR à laquelle il est rattaché. On souhaite établir un fichier des membres d'une université afin de pouvoir, par exemple, envoyer des courriers bien adaptés à chaque catégorie de personnel.


1. En définissant éventuellement des types intermédiaires, définissez un type univ pour représenter une université.
2. Écrivez une fonction listing qui prend une valeur de type univ en argument et rend la liste des noms de tous les membres de l'université. Quel est son type?
3. Écrivez une fonction separe qui prend une valeur de type univ en argument et rend un triplet dont la première composante est la liste des étudiants de l'université, la seconde la liste des administratifs, la troisième la liste des enseignants-chercheurs. Donnez son type.
Ce document a été traduit de LATEX par HEVEA.