Université Pierre & Marie CURIE
U.F.R d'infomatique
Maîtrise -- 2000-01
Programmation Objet et Distribution



Tavaux dirigés n° 1








Exercice I Mise en jambes.


Question (I.1) Écrire une fonction find de type ('a -> bool) -> 'a array -> int telle que find p t donne le plus petit indice i dans t tel que p t.(i) valle true ou déclanche l'exception Not_found si un tel indice n'existe pas.


Question (I.2) Écrire une fonction find_max de type (pour simplifier) int array -> int qui donne le plus petit indice de l'élément maximal d'un tableau.


Question (I.3) Généralisez la fonction find_max en une fonction find2 de type
('a -> 'a -> bool) -> 'a array -> int.




Exercice II Un tri par arbre.


Question (II.1) Définir un type de données 'a btree représentant les arbres binaires.


Question (II.2) Écrire une fonction ins_btree de type
('a -> 'a -> bool) -> 'a -> 'a btree -> 'a btree qui insére un élément dans un arbre selon la disciple des arbres binaires de recherche en prenant comme relation d'ordre le premier argument.


Question (II.3) Écrire une fonction btree_of_list de type
('a -> 'a -> bool) -> 'a list -> 'a btree qui construit un arbre binaire de recherche à partir des éléments du tableau selon l'ordre donné par le premier argument.


Question (II.4) Écrire la fonction inverse list_of_btree de type 'a btree -> 'a list qui construit la liste des éléments contenus dans l'arbre en effectuant un parcours gauche-droite.


Question (II.5) Déduire de btree_of_list et list_of_btree une fonction de tri.




Exercice III Des modules pour les piles.

La distribution d'Objective Caml fournit un module Stack dont le fichier d'interface stack.mli contient les déclarations suivantes :
type 'a t
exception Empty
val create: unit -> 'a t
val push: 'a -> 'a t -> unit
val pop: 'a t -> 'a
val clear : 'a t -> unit
val length: 'a t -> int
val iter: ('a -> unit) -> 'a t -> unit


Question (III.1) Définir une signature STACK à partir de ces déclarations.


Question (III.2) Pour représenter une pile, on utilisera le type suivant : 
 { mutable sp : int; mutable c : 'a array }
Définir une structure implantant cette signature pour fabriquer un module Stack.

Vous avez deux petits problèmes à résoudre : créer une pile polymorphe et ne pas casser lorsque le tableau est plein.


Question (III.3) Discutons de la façon d'obtenir un module FStack pour les piles de taille fixe. La taille est fixée par la fonction create qui devient de type int -> Stack. On pourra alors déclencher une exception Stack_overflow.




Exercice IV Différentes vue d'un module.


Question (IV.1) En utilisant les fonctions du module List, définissez un module Alist de gestion des listes d'associations.


Question (IV.2) On veut obtenir deux modules de gestion des listes d'associations :
Adm_alist
destiné aux administrateurs des listes. Ils auront la possiblité de consulter et modifier la liste.
User_alist
destiné aux utilisateurs des listes. Ils auront seulement la possibilité de consulter la liste.
Comment faire ?




Exercice V Variation sur les modules : un module de tri.


Question (V.1) Reprendre la fonction de tri de l'exercice 2 pour en faire un module.


Question (V.2) Proposez une solution pour obtenir un module de tri paramétré par une fonction d'ordre et qui utilise le module définit à la question 1



This document was translated from LATEX by HEVEA.