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