Structures de données
Un article de Mangue.org, l'encyclopéde libre.
Caml nous permet, lorsque nous le souhaitons, de définir nos propres types de données. Ceux-ci pourront être utilisés dans des programmes plus complexes afin de coder des informations différentes des simples entiers ou nombres réels.
| Sommaire |
Les enregistrements
Nous allons partir sur un cas concret pour commencer. Dans un de nos programmes, nous avons besoin de représenter des nombres complexes. Jusqu'à présent vous n'auriez eu d'autre choix que d'utiliser un n-uplet de type float * float. Ceci répondrai parfaitement à la question biensûr puisque nous aurions une partie réelle et une partie imaginaire, mais ça prèterait très rapidement à confusion dans des programmes plus importants.
Imaginez que dans le même programme nous manipulions des points sur un plan graphique symbolisés par une abscisse et une ordonnée (donc encore un n-uplet de type float * float)
Avec les enregistrements chaque valeur appartient à un champ nommé, il n'y a donc plus de risque de confusion. De plus il sera désormais possible d'affecter ou de lire des valeurs dans un ordre quelconque sur un enregistrement.
| Danger |
| Cependant deux types enregistrements différents ne peuvent pas avoir de champ de même nom, sans quoi celà provoquerait une erreur pour le Caml comme le démontre le dernier exemple... |
# type complex = {Re: float; Im: float} ;;
Type complex defined.
# let i = {Im = 1.0; Re = 0.0}
and zéro = {Re = 0.0; Im = 0.0} ;;
i : complex = {Re = 0.0; Im = 1.0}
zéro : complex = {Re = 0.0; Im = 0.0}
# let sqrt2sur2 = atan 1.0
in
{Re = sqrt2sur2; Im = sqrt2sur2} ;;
- : complex = {Re = 0.785398163397; Im = 0.785398163397}
# type point = {X : float; Im : float} ;;
Type point defined.
# {X = 0.0; Im = -. 1.0} ;;
- : point = {X = 0.0; Im = -1.0}
# i ;;
- : complex = {Re = 0.0; Im = 1.0}
# let nb_cplx = { Im = 4.0; Re = -. 5.2} ;;
Toplevel input:
> let nb_cplx = { Im = 4.0; Re = -. 5.2} ;;
> ^^^^^^^^^^^^^^^^^^^^^^^^
The label Re does not belong to the type point.
Il convient donc de choisir des noms de champs précis mais uniques. Sans quoi vous seriez rapidement confronté à ce genre d'erreur.
Lors d'une affectation , Caml vérifie qu'une valeur est bien affectée à chaque champ de l'enregistrement. Si ce n'est pas le cas ou si l'un des types ne correspond pas alors uen erreur est générée.
Voyons maintenant (toujous au travers d'exemples) comment accéder aux valeurs des enregistrements.
# type livre = {Auteur:string;Titre:string} ;;
Type livre defined.
# let CycleDeDune = {Auteur="Frank HERBERT";Titre="Cycle de Dune"}
and SeigneurDesAnneaux = {Titre="Le Seigneur des Anneaux";Auteur="J.R.R. TOLKIEN"} ;;
CycleDeDune : livre = {Auteur = "Frank HERBERT"; Titre = "Cycle de Dune"}
SeigneurDesAnneaux : livre =
{Auteur = "J.R.R. TOLKIEN"; Titre = "Le Seigneur des Anneaux"}
# CycleDeDune.Titre ;;
- : string = "Cycle de Dune"
# SeigneurDesAnneaux ;;
- : livre = {Auteur = "J.R.R. TOLKIEN"; Titre = "Le Seigneur des Anneaux"}
#SeigneurDesAnneaux.Auteur ^ " et " ^ CycleDeDune.Auteur ^ " sont géniaux !!!!" ;;
- : string = "J.R.R. TOLKIEN et Frank HERBERT sont géniaux !!!!"
# let auteur_et_titre ouvrage =
ouvrage.Auteur ^ " a écrit " ^ ouvrage.Titre ;;
auteur_et_titre : livre -> string = <fun>
# auteur_et_titre SeigneurDesAnneaux ;;
- : string = "J.R.R. TOLKIEN a écrit Le Seigneur des Anneaux"
| Remarque |
| Il est possible d'utiliser les opérateurs de comparaison sur les enregistrements mais seules l'égalité et son contraire ont un sens. |
Fonctions définies sur les enregistrements
Vous en avez déjà u premier exemple avec la fonction auteur_et_titre ci-dessus. D'une manière générale dès que vous savez comment accéder aux valeurs d'un type de données vous savez écrire une fonction qui l'exploite.
On peut aussi utiliser des filtres avec les enregistrements et nous n'allons pas nous en priver puisque ceci améliore grandement la lisibilité de nos codes sources.
Nous allons reprendre notre type complex et implémenter toutes les fonctions nécessaires aux calculs sur ces nombres un peu particuliers.
# type complex = { Re:float; Im:float} ;;
Type complex defined.
# let i = { Im = 1.0; Re = 0.0}
and zéro = {Re = 0.0; Im = 0.0}
and cpl1 = {Re = 1.0; Im = -. 2.0}
and cpl2 = {Im = -. 1e-3; Re = 2.5e4} ;;
i : complex = {Re = 0.0; Im = 1.0}
zéro : complex = {Re = 0.0; Im = 0.0}
cpl1 : complex = {Re = 1.0; Im = -2.0}
cpl2 : complex = {Re = 25000.0; Im = -0.001}
#(* première version: sans filtre *)
let somme_cplx c1 c2 =
{ Re= c1.Re +. c2.Re; Im = c1.Im +. c2.Im} ;;
somme_cplx : complex -> complex -> complex = <fun>
#(* deuxième version: avec filtre *)
let somme_cplx {Re=r1;Im=i1} {Re=r2;Im=i2} =
{ Re = r1 +. r2; Im = i1 +. i2} ;;
somme_cplx : complex -> complex -> complex = <fun>
# somme_cplx i zéro ;;
- : complex = {Re = 0.0; Im = 1.0}
Le principe est le même pour toutes les fonctions de base sur les nombres complexes. Je vous demande donc en tant qu'exercice (corrigé en dehors des cours) d'écrire les fonctions module_cplx, argument_cplx, différence_cplx, produit_cplx, quotient_cplx et conjugué_cplx. Si vous ne connaissez pas très bien ces fonctiosn et la manière dont elles agissent sur les nombres complexes consultez un cours de mathématiques.
Jouez le jeu c'est un aussi un bon exercice pour vous entrainer à résoudre un maximum de problèmes. D'ailleurs les problèmes mathématiques sont de loin les plus simples à résoudre, surtou en Caml. Nous construiront bientôt des programmes plus ludiques rassurez vous :-)
Enregistrements et polymorphisme
Nous souhaitons disposer d'un type de donneés nous permettant de stocker deux valeurs du même type de base. une paire (n-uplet) ne suffit pas puisqu'il n'y a aucun type nommé et une liste est trop hermétique pour ce que nous voulons faire, de plus rien ne nous empècherait d'ajouter des valeurs.
Il est possible avec les enregistrements de définir des types polymorphes, un peu comme 'a list, nous allons définir 'a paire, un enregistrement polymorphe destiné à coder deux valeurs du même type, voici comment procéder :
# type ('a) paire = {Gauche: 'a; Droite: 'a} ;;
Type paire defined.
# {Gauche=0; Droite=1} ;;
- : int paire = {Gauche = 0; Droite = 1}
# {Gauche=snd; Droite=fst} ;;
- : ('a * 'a -> 'a) paire = {Gauche = <fun>; Droite = <fun>}
Vous devez donc déclarer que le type sera polymorphe avant de le définir. Il est aussi possible de faire intervenir plusieurs champs polymorphes dans un enregistrement, comme dans l'exemple suivant :
# type ('a,'b) couple = {Gauche:'a;Droite:'b} ;;
Type couple defined.
# {Gauche=1;Droite=4} ;;
- : (int, int) couple = {Gauche = 1; Droite = 4}
# { Gauche = false; Droite= 0} ;;
- : (bool, int) couple = {Gauche = false; Droite = 0}
# { Gauche = hd; Droite= tl} ;;
- : ('a list -> 'a, 'b list -> 'b list) couple =
{Gauche = <fun>; Droite = <fun>}
Champs mutables dans les enregistrements
Avec les type enregistrements que nous avons vu jusqu'à présent, il n'était pas possible de éfinir autre chose que des constantes. Nous allons aller plus loin maintenant avec les champs mutable.
Ces champs, qualifiés de "mutables" (ou modifiables), ont la particularité de permettre à l'utilisateur de changer les valeurs qu'ils contiennent.
C'est la première fois, à l'exception des chaînes de caractères, que nous rencontrons un type de données dont il est possible de modifier la valeur. Pour celà nous allons prendre un exemple concret, celui d'un compte en banque que nous allons coder dans un enregistrement à deux champs seulement, l'identifiant (ou numéro) de ce compte et le solde de ce compte.
C'est le solde du compte que nous ferrons varirer aucours de notre programme. C'est donc lui que nous allons définir comme mutable. L'accès aux valeurs se fait comme pour un enregistrement normal. Quant à la modification du solde, nous devrons utiliser l'opérateur <- comme dans l'exemple suivant :
# type compte = {id:int; mutable solde: float} ;;
Type compte defined.
# let compte_de_martin = {id = 1; solde = 1e3}
and compte_de_dupond = {id = 2; solde = 1.2e3} ;;
compte_de_martin : compte = {id = 1; solde = 1000.0}
compte_de_dupond : compte = {id = 2; solde = 1200.0}
# compte_de_martin.id ;;
- : int = 1
# compte_de_martin.solde ;;
- : float = 1000.0
# compte_de_martin.solde <- compte_de_martin.solde +. 500.0 ;;
- : unit = ()
# compte_de_martin ;;
- : compte = {id = 1; solde = 1500.0}
# compte_de_dupond.id <- 3 ;;
Toplevel input:
> compte_de_dupond.id <- 3 ;;
> ^^^^^^^^^^^^^^^^^^^^^^^^
The label id is not mutable.
C'est une opération qui agit sur un contenu en mémoire, elle ne fournit donc rien de plus qu'un résultat de type unit.
En guise d'exercice je vous demanderai d'écrire une fonction créditer qui permet de créditer (ou de débiter) une certaine somme sur un compte passé en argument. La correction est toujours accessible dans la [corrections.htm page des corrections] :-)
Les types sommes
Nous voulons maintenant coder en Caml un jeu de cartes (belotte par exemple). Chaque carte est composé d'une couleur et d'une valeur... On pourrait penser utiliser des entiers mais la lisibilité du code source en souffrirait à tel point que si vous le relisiez vous même quelques semaines plus tard vous auriez du mal !
Il est possible de définir un type par énumération des différentes valeurs qu'il contiendra. La définition de tels types est des plus simples, il suffit de séparer les différentes formes qu'il peut prendre par des | comme dans cet exemple où nous définissons un type CouleurPixel pour représenter la couleur de vos pixels à l'écran.
# type CouleurPixel = | Red (* couleur primaire en informatique *) | Green (* couleur primaire *) | Blue (* couleur primaire *) | CodeCouleur of int ;; Type CouleurPixel defined. # let rouge = Red and vert = Green and bleu = Blue and jaune = CodeCouleur ((255 * 256 + 255) * 256 + 0) ;; rouge : CouleurPixel = Red vert : CouleurPixel = Green bleu : CouleurPixel = Blue jaune : CouleurPixel = CodeCouleur 16776960
Nous avons défini un type CouleurPixel qui peut prendre différentes valeurs, à savoir Red, Green, Blue ou une valeur qu'on construit à partir d'une valeur entière.
D'une manière générale les types sommes sont construits par énumération des différentes formes qu'ils peuvent prendre, que ce soient des constantes ou des constructeurs de valeurs.
Voici comment définir un type rationnel permettant de coder en mémoire les nombres rationnels sous leurs trois écritures possibles. Nous nous chargerons ensuite d'écrire les fonctions permettant d'assurer les opérations simples sur ce type ainsi que les convertions vers les types de base.
# type fact = {Numérateur: int; Dénominateur: int} ;;
Type fact defined.
# type rationnel =
| Entier of int
| Fraction of fact
| Décimal of float ;;
Type rationnel defined.
# let demi = Décimal (0.5)
and zéro = Entier (0)
and (ax,bx) = (Fraction {Numérateur=3;Dénominateur=4}, Entier 5)
and moitié = Fraction {Numérateur=1;Dénominateur=2} ;;
demi : rationnel = Décimal 0.5
zéro : rationnel = Entier 0
ax : rationnel = Fraction {Numérateur = 3; Dénominateur = 4}
bx : rationnel = Entier 5
moitié : rationnel = Fraction {Numérateur = 1; Dénominateur = 2}
# ax ;;
- : rationnel = Fraction {Numérateur = 3; Dénominateur = 4}
# moitié = demi ;;
- : bool = false
Fonctions sur les types sommes
Le types sommes sont définis en énumérant les différentes formes que les valeurs qu'ils codent peuvent prendre. Ils se prêtent donc naturellement au filtrage
# let int_of_rationnel = fun
| (Entier x) -> x
| (Fraction {Numérateur = a;Dénominateur = b}) -> a / b (* perte de précision *)
| (Décimal x) -> int_of_float(x) (* perte de précision *) ;;
int_of_rationnel : rationnel -> int = <fun>
# let fact_of_rationnel = fun
| (Entier x) -> {Numérateur=x;Dénominateur=1}
|(Fraction x) -> x
|(Décimal x) ->
let rec aux (coeff) =
if (x *. float_of_int(coeff) <> float_of_int ( int_of_float(x *. float_of_int(coeff))))
(* partie décimale non nulle *)
then aux (coeff * 10)
else {Numérateur = int_of_float(x *. float_of_int(coeff)); Dénominateur = coeff}
in aux 1 ;;
fact_of_rationnel : rationnel -> fract = <fun>
# let float_of_rationnel = fun
| (Entier x) -> float_of_int (x)
| (Fraction {Numérateur = a;Dénominateur = b}) -> (float_of_int (a)) /. (float_of_int (b))
| (Décimal x) -> x ;;
float_of_rationnel : rationnel -> float = <fun>
| Danger |
| Attention à ne pas oublier les parenthèses lorsque vous définissez des fonctions de cette manière. Sans quoi le compilateur vous signalerez des erreurs sur vos filtres. C'est une cause fréquente d'erreur. |
En tant qu'exercice, toujours corrigé en dehors de ce cours, je vous demanderai d'écrire vous même les fonctions pour les opérations arithmétiques simples (somme, différence, produit, quotient). Pensez à utiliser les fonctions ci-dessus ça vous fera certainement gagner pas mal de temps.
Polymorphisme sur les types sommes
Les enregistrements ne sont pas les seuls à supporter le polymorphisme. Vous pourrez jouïr des mêmes avantages avec les types sommes. Comme dans cet exemple où nous définissons un type ayant une forme simple et une forme pondérée...
# type 'a élément = | Simple of 'a | Pondéré of 'a * int ;; Type élément defined. # let note1 = Simple 14.0 ;; note1 : float élément = Simple 14.0 # let note2 = Pondéré (12.0, 3) ;; note2 : float élément = Pondéré (12.0, 3) # let liste_notes = [note1;note2] ;; liste_notes : float élément list = [Simple 14.0; Pondéré (12.0, 3)]
| Réponse |
| Vous l'avez deviné, l'intérêt de ce programme est de pouvoir calculer rapidement des moyennes pondérées ou non. A vous décrire les fonctions adéquates. |
Les grades (extensions des filtres)
Dans les nombreux programmes que nous avons écrit vous constatez que les filtres permettent d'optimiser le code, tant par sa lisiblité que par son efficacité puisqu'ils permettent de rassembler de nombreuses conditions en un seul test.
Pourtant il arrivera parfois que les filtres ne suffisent plus, que nous ayons besoin de tester une valeur en particulier ; et ceci est fréquent avec les types sommes.
Nous allons définir deux types permettant de manipuler des cartes à jouer (jeu de belotte). Pour celà nous avons besoin de deux caractéristiques: la couleur et la valeur de la carte.
Nous allons ensuite écrire une fonction nous renvoyant la valeur de la carte passé en argument suivant qu'il s'agisse de la couleur d'atout ou non...
# type couleur =
| Pique
| Coeur
| Trèfle
| Carreau ;;
Type couleur defined.
# type valeur =
| Sept | Huit | Neuf
| Dix
| Valet
| Dame
| Roi
| As ;;
Type valeur defined.
# type carte = {Valeur: valeur; Couleur: couleur} ;;
Type carte defined.
# let couleur_atout = Pique ;;
couleur_atout : couleur = Pique
# let valeur_carte = fun
| {Valeur=As;_} -> 11
| {Valeur=Roi;_} -> 4
| {Valeur=Dame;_} -> 3
| {Valeur=Valet;Couleur=c} when c = couleur_atout -> 20
| {Valeur=Valet;_} -> 2
| {Valeur=Neuf;Couleur=c} when c = couleur_atout -> 14
| {Valeur=Dix;_} -> 10
| _ -> 0 ;;
valeur_carte : carte -> int = <fun>
# valeur_carte {Valeur=Neuf;Couleur=Pique};;
- : int = 14
# valeur_carte {Valeur=Valet;Couleur=Coeur} ;;
- : int = 2
Le comportement est le même que dans les filtres dits classique à ceci près que le cas n'est sélectionné que lorsque la condition qui suit le when est vraie.
Dans ce programme vous voyez que notre fonction fait intervenir la valeur d'une constante, or vous savez que cette valeur sera toujours Pique quelles que soient les instructions qui suivent. Nous verrons bientôt comment contourner ce problème avec les références.
