Précédent Index Suivant

Types cycliques

Objective CAML permet de déclarer des structures de données récursives, c'est à dire des structures pouvant comporter une valeur ayant la même structure. 

 
# type somme_ex1 = Ctor of somme_ex1 ;;
type somme_ex1 = | Ctor of somme_ex1

# type record_ex1 = { champ : record_ex1 } ;;
type record_ex1 = { champ: record_ex1 }


La construction de valeurs de ces types n'est pas immédiate car il est nécessaire de posséder une valeur pour en construire une. La déclaration récursive de valeurs permet de se tirer de cercle vicieux.

# let rec somme_val = Ctor somme_val ;;
val somme_val : somme_ex1 = Ctor (Ctor (Ctor (Ctor (Ctor ...))))

# let rec val_record_1 = { champ = val_record_2 } 
 and     val_record_2 = { champ = val_record_1 } ;;
val val_record_1 : record_ex1 = {champ={champ={champ={champ={champ=...}}}}}
val val_record_2 : record_ex1 = {champ={champ={champ={champ={champ=...}}}}}


Les arbres planaires généraux peuvent se représenter par une structure de données de cette forme.

# type 'a arbre = Sommet of 'a * 'a arbre list ;; 
type 'a arbre = | Sommet of 'a * 'a arbre list
# let hauteur_1 = Sommet (0,[]) ;;
val hauteur_1 : int arbre = Sommet (0, [])
# let hauteur_2 = Sommet (0,[ Sommet (1,[]); Sommet (2,[]); Sommet (3,[]) ]) ;;
val hauteur_2 : int arbre =
  Sommet (0, [Sommet (1, []); Sommet (2, []); Sommet (3, [])])
# let hauteur_3 = Sommet (0,[ hauteur_2; hauteur_1 ]) ;;
val hauteur_3 : int arbre =
  Sommet
   (0,
    [Sommet (0, [Sommet (...); Sommet (...); Sommet (...)]); Sommet (0, [])])

(* idem avec un record *)
# type 'a arbre_rec = { etiquette:'a ; fils:'a arbre_rec list } ;;
type 'a arbre_rec = { etiquette: 'a; fils: 'a arbre_rec list }
# let haut_rec_1 = { etiquette=0; fils=[] } ;;
val haut_rec_1 : int arbre_rec = {etiquette=0; fils=[]}
# let haut_rec_2 = { etiquette=0; fils=[haut_rec_1] } ;;
val haut_rec_2 : int arbre_rec = {etiquette=0; fils=[{etiquette=0; fils=[]}]}


On pourrait se dire qu'il n'est pas utile d'avoir un type énuméré avec un seul constructeur mais, par défaut, Objective CAML n'accepte pas les abréviations de types récursives. 
 
# type 'a arbre = 'a * 'a arbre list ;;
Characters 7-36:
The type abbreviation arbre is cyclic


On peut définir des valeurs ayant cette structure, mais elles n'ont pas le même type. 

# let arbre_1 = (0,[]) ;;
val arbre_1 : int * 'a list = 0, []
# let arbre_2 = (0,[ (1,[]); (2,[]); (3,[]) ]) ;;
val arbre_2 : int * (int * 'a list) list = 0, [1, []; 2, []; 3, []]
# let arbre_3 = (0,[ arbre_2; arbre_1 ]) ;;
val arbre_3 : int * (int * (int * 'a list) list) list =
  0, [0, [...; ...; ...]; 0, []]


De la même manière, Objective CAML n'est pas capable d'inférer un type à une fonction prenant en argument une valeur de cette forme. 

# let max_list = List.fold_left max 0 ;;
val max_list : int list -> int = <fun>

# let rec hauteur = function 
     Sommet (_,[]) -> 1
   | Sommet (_,fils) -> 1 + (max_list (List.map hauteur fils)) ;;
val hauteur : 'a arbre -> int = <fun>


# let rec hauteur2 = function 
     (_,[]) -> 1 
   | (_,fils) -> 1 + (max_list (List.map hauteur2 fils)) ;; 
Characters 97-101:
This expression has type 'a list but is here used with type
  ('b * 'a list) list


Le message d'erreur nous montre que la fonction hauteur2 serait typable si nous avions l'égalité entre les types 'a et 'b * 'a list. C'est justement cette égalité qui nous a été refusée dans la déclaration de l'abréviation de type arbre.

Pourtant, le typage des objets permet de construire des valeurs dont le type est cyclique. Examinons la fonction suivante et tentons de deviner son type. 

# let f x = x#copy = x ;;
Le type de x est une classe qui possède la méthode copy. Le type de cette méthode est le même que celui de x puisque l'on teste leur égalité. En conséquence, si foo est le type de x il est de la forme < copy : foo ; .. >. D'après ce que nous avons vu plus haut, son type étant cyclique, cette fonction devrait être rejetée; et pourtant il n'en est rien. 

# let f x = x#copy = x ;;
val f : (< copy : 'a; .. > as 'a) -> bool = <fun>
Objective CAML accepte cette fonction et dénote la cyclicité du type par le as qui identifie 'a avec un type contenant 'a.

En réalité, les deux problèmes sont exactement les mêmes, mais par défaut, Objective CAML n'accepte ce genre de types que lorsqu'ils concernent des objets. La fonction hauteur est typable si elle produit une cyclicité sur le type d'un objet.

# let rec hauteur a = match a#fils with 
     [] -> 1 
   |  l -> 1 + (max_list (List.map hauteur l)) ;; 
val hauteur : (< fils : 'a list; .. > as 'a) -> int = <fun>


Précédent Index Suivant