[t]40ex
UniversitéPierre & Marie Curie
U.F.R d'infomatique
[t]45ex
Maîtrise -- 2000-01
Programmation Objet et Distribution



Tavaux dirigés n° 4






Exercice I Des arbres binaires de recherche, encore ; oui mais en objets impératifs !

On veut définir des structures d'arbres paramétrés ayant les méthodes 
is_void de type unit -> bool qui renvoie true si l'arbre est vide et false sinon.
add de type 'a -> unit qui rajoute un élément àl'arbre selon la discipline des arbres binaires de recherche (on utilisera la relation polymorphe <).
to_list de type unit -> 'a list qui rend la liste des éléments contenus dans l'arbre (de la gauche vers la droite).

Question (I.1) Définir une classe ['a] void pour représenter l'arbre vide. La méthode add échouera toujours.


Question (I.2) Définir une classe ['a] node pour représenter les arbres binaires non vides.


Question (I.3) Construiser une valeur contenant l'arbre suivant :


Question (I.4) (subsidaire) Utiliser les classes d'arbres pour obtenir une fonction de tri de listes.




Exercice II Un exercice simple utilisant le sous typage.


Question (II.1) Définir une classe num qui contient un champ de type int et une méthode d'accés àce champ. Définir une classe print_num héritière de num qui fournit une méthode d'affichage (print).


Question (II.2) Définir une valeur de type num puis une valeur de type print_num et construire une liste contenant ces deux valeurs.


Question (II.3) Définir sans hériter de num une classe var_num qui contient une champ modifiable de type int, une méthode d'accés àce champ et une méthode de modification de la valeur de ce champ.


Question (II.4) Peut-on définir une liste contenant une valeur de type num et une valeur de type var_num ?




Exercice III Classes abstraites et contraintes de type pour listes ordonnées paramétriques.


Question (III.1) Définir une classe abstraite 'a olist telle que : 
class virtual ['a] olist :
  object ('b)
    constraint 'a = < is_le : 'a -> bool; to_string : unit -> string; .. >
    val mutable content : 'a list
    method virtual add : 'a -> unit
    method merge : 'b -> unit
    method to_string : unit -> string
  end
Notez que le type de l'objet est nommé('b). La valeur initiale de content sera une liste vide. La méthode merge est programmée en utilisant la méthode abstraite add.


Question (III.2) Définir, par héritage de 'a olist, la classe 'a inc_list des listes triées par ordre croissant et la classe 'a dec_list des listes triées par ordre décroissant.


Question (III.3) Définir, par héritage de la classe num de la question 1, une classe onum répondant àla contrainte posée sur le paramétre de type de 'a olist. Construire deux listes dl et il contenant les trois premiers entiers ; la première de type 'a dec_list et la seconde de type 'a inc_list.


Question (III.4) Peut-on fusionner les deux listes dl et il en utilisant la méthode merge ?




Exercice IV Méthodes fonctionnelles et type de (self).

On donne la classe abstraite 'a stack : 
class virtual ['a] stack =
 object
  method virtual is_empty : unit -> bool
  method virtual push : 'a -> 'a stack
  method virtual top : 'a
  method virtual pop : 'a stack
 end ;;

Question (IV.1) Définir, par héritage de 'a stack, la classe 'a cons_stack qui prend un paramètre de type 'a et un de type 'a stack.


Question (IV.2) Définir la classe empty_stack.



This document was translated from LATEX by HEVEA.