Structures de données persistantes 
Une structure de donnée permet de stocker un ensemble d'éléments et de faire certaines opérations sur ces éléments.
OCaml possède principalement 3 structures persistantes :
- tuple, ou $n$-uplets
- list, les plus utilisées
- string, pour les chaînes de caractères
Intérêts des structures de données persistantes¶
- La mémoire peut être partagée sans risque et sans espace mémoire supplémentaire.
Ainsi, écrirelet x = y, siyest une structure persistante, permet d'utiliser la même case mémoire pourxety. Siyest mutable, alors toute modification deyaffectex(et vice-versa), ce qui n'est en général pas souhaité. Il faudrait alors créer une copie dey, ce qui est coûteux en temps et en mémoire. - Le backtracking (cours ultérieur) est plus simple.
- La programmation concurrente (cours de MPI) est plus simple.
Tuple¶
Un tuple (ou $n$-uplet) est défini comme en mathématiques. Par exemple, un $2$-uplet est un couple (qui réprésente par exemple un point dans le plan $\mathbb{R}^2$ :
let point = (1.75, 2.5) (* un couple de 2 flottants *)
OCaml nous répond que point est de type float*float, ce qui signifie un couple de 2 float.
On peut récupérer les coordonnées d'un $n$-uplet de la façon suivante :
let (a, b) = point (* met la 1ère coordonnée de point dans a et la 2ème dans b *)
Dans le cas d'un couple, on peut aussi récupérer le 1er et 2ème élement avec les fonctions fst et snd :
fst point;;
snd point;;
Exercice
À votre avis, quels sont les types de fst et snd ? Vérifier avec OCaml.
Dans une fonction, on peut aussi décomposer directement le tuple en argument de la fonction :
let mid (x1, y1) (x2, y2) = (* renvoie le milieu des deux points *)
(x1 +. x2) /. 2., (y1 +. y2) /. 2.
val mid : float * float -> float * float -> float * float = <fun>
Les parenthèses sont en fait faculatitives autour d'un tuple : l'instruction précédente est donc équivalente à let a, b = point. De plus, attention à utiliser . et pas , pour des flottants, sinon on obtient un tuple :
3,14 (* Attention : c'est un tuple et non pas un flottant *)
Un $n$-uplets peut contenir des contenir des éléments de types différents :
let t = (1, 2.2, true) (* un triple contenant un entier, un flottant et un booléen *)
Deux tuples sont égaux s'ils sont de même taille et que les composantes sont égales 2 à 2 :
(1, 2) = (1, 2);;
(1, 2) = (1, 3);;
Exercice
On représente un nombre complexe par un couple de flottants (composé de la partie réelle et partie imaginaire).
- Définir $1 - 2i$ sous forme de couple.
- Définir une fonction
conjugue : float*float -> float*floatrenvoyant le conjugué $\bar{z}$ d'un nombre complexe $z$. - Écrire une fonction
addqui prend deux nombres complexes $z_1$ et $z_2$ en arguments et renvoie $z_1 + z_2$. - Écrire une fonction
mulqui multiplie deux nombres complexes en arguments. - Écrire une fonction
divqui divise deux nombres complexes en arguments (on utilisera la multiplication par le conjugué : $\frac{a + ib}{c + id} = \frac{(a + ib)(c - id)}{(c + id)(c - id)} = \frac{ac + bd + i(bc - ad)}{c^2 - d^2}$
Solution
(* 1. *)
let z = (1., -.2.);;
(* 2. *)
let conjugue (a, b) =
(a, -.b);;
conjugue z;;
(* 3. *)
let add z1 z2 =
(fst z1 +. fst z2, snd z1 +. snd z2) in
add z z;; (* z + z = 2 - 4i *)
(* 4. *)
let mul z1 z2 =
let re1, im1 = z1 in (* pour simplifier les calculs *)
let re2, im2 = z2 in
(re1*.re2 -. im1*.im2, re1*.im2 +. re2*.im1) in
mul z z;; (* z*z = (1 - 2i)(1 - 2i) = 1 - 4 - 2i - 2i = -3 - 4i*)
(* 5. *)
let div z1 z2 =
let a, b = z1 in (* pour simplifier les calculs *)
let c, d = z2 in
let denom = c*.c +. d*.d in
((a*.c +. b*.d)/.denom, (b*.c -. a*.d)/.denom) in
div z z;; (* z/z = 1 *)
Une des utilités des tuples et de permettre de renvoyer plusieurs résultats par une fonction (on les renvoie sous forme de tuple).
Listes¶
Une liste se définie avec des crochets ([...]), les éléments étant séparés par des point-virgules (;) :
[1; 7; -1] (* liste composée de 3 entiers *)
OCaml nous indique qu'il s'agit d'une valeur de type int list, c'est à dire liste d'entiers. Voici d'autres exemples de listes :
[3.14; 2.718] (* liste de 2 flottants *)
- : float list = [3.14; 2.718]
[] (* liste vide *)
- : 'a list = []
Par contre, on ne peut pas avoir plusieurs types différents dans la même liste :
[3.14; 2]
L'instruction `e::l` renvoie une liste obtenue à partir de l en ajoutant l'élément e au début :
1::[2; 3] (* ajoute 1 au début de la liste [2; 3] *)
Attention : cons (`::`) renvoie une nouvelle liste, mais ne modifie pas celle à droite. Par exemple :
let l = [1; 2; 3];;
0::l;; (* donne une nouvelle liste *)
l;; (* l n'a pas été modifiée *)
Si on veut ajouter un élément à une liste, il faut donc construire une nouvelle liste :
let l2 = 0::l;; (* l2 est une nouvelle liste obtenue à partir de l en rajoutant 0 *)
Attention On ne peut pas ajouter simplement d'élément à la fin d'une liste (il faudrait parcourir récursivement chaque élément de la liste jusqu'à la fin, ce qui est inefficace).
On peut se servir de :: pour construire une liste élément par élément, avec une fonction récursive :
let rec range n = (* renvoie la liste des entiers de 1 à n (à l'envers) *)
if n = 0 then [] (* cas de base *)
else n::range (n-1);;
range 5
Exercice
Écrire une fonction pairs : int -> int list telle que pairs n renvoie la liste des entiers pairs entre $0$ et $2n$ (inclus).
Solution
let rec pairs n =
if n < 0 then []
else n::pairs (n - 2);;
pairs 6
Pattern matching (filtrage)¶
Pattern matching simple¶
La façon classique de parcourir une liste l en OCaml est d'utiliser un pattern matching, qui consiste à regarder la forme de l :
- soit
lest vide (cas de base) - soit
lcontient un premier élément (la tête), puis le reste de la liste (la queue)
Voici la syntaxe OCaml :
let l = [1; 2; 3]
val l : int list = [1; 2; 3]
match l with
| [] -> 0 (* si l est vide, on renvoie 0 *)
| e::q -> e (* sinon l est de la forme e::q, on renvoie e *)
Comme l est non-vide, on passe dans le 2ème cas du match et on affiche le premier élément de l. Essayez de mettre une liste vide à la place de l dans le match précédent pour voir la différence.
La plupart du temps, on utilise un `match` dans une fonction récursive ayant une liste en argument. Voici par exemple une fonction récursive pour calculer le nombre d'éléments d'une liste :
let rec taille l = match l with
| [] -> 0 (* une liste vide est de taille 0 *)
| e::q -> 1 + taille q;; (* sinon l contient e + tous les éléments de q *)
taille l;; (* vérification *)
Remarque : OCaml nous dit que taille est de type 'a list -> int. 'a signifie "n'importe quel type". Il n'y a donc pas de contrainte sur le type des éléments de la liste l en argument.
Remarque : quand une fonction possède un seul argument qui est une liste, on peut écrire let f = function ... au lieu de let f l = match l with .... Par exemple on peut réécrire la fonction taille précédente :
let rec taille = function (* même chose que let taille l = match l with ... *)
| [] -> 0
| e::q -> 1 + taille q;;
val taille : 'a list -> int = <fun>
Exercice
- Écrire une fonction
somme : int list -> intpour calculer la somme des termes d'une liste. Par exemple,somme [4; 7; 3]doit renvoyer $14$. - Réutiliser la fonction
rangeci-dessus pour calculer la somme des entiers de $1$ à $n$.
Solution
(* 1. *)
let rec somme l = match l with
| [] -> 0
| e::q -> e + somme q;;
somme [4; 7; 3]
(* 2. *)
let somme_gauss n =
somme (range n);;
somme_gauss 4;; (* 4 + 3 + 2 + 1 *)
Exercice
Écrire une fonction maximum permettant de renvoyer le plus grand élément d'une liste d'entiers.
Solution
let rec maximum l = match l with
| [] -> min_int (* par convention, le max d'un ensemble vide est -infini *)
(* c'est pratique pour que n'importe quelle valeur remplace -infini *)
| e::q -> max e (maximum l);; (* en utilisant la fonction max *)
let rec maximum l = match l with
| [] -> min_int
| e::q -> let m = maximum q in (* sans utiliser la fonction max *)
if e > m then e
else m;;
maximum [1; 4; 2; 3]
val maximum : int list -> int = <fun>
val maximum : int list -> int = <fun>
- : int = 4
Pattern matching plus avancé¶
Un pattern matching peut aussi permettre de décomposer sous d'autres formes :
let deuxieme l = match l with (* renvoie le 2ème élément d'une liste *)
| e1::e2::q -> e2;; (* décompose la liste en le 1er élément e1, le 2ème e2 et la liste des autres éléments *)
deuxieme [4; 7; 3]
File "[6]", line 1, characters 17-96: 1 | .................match l with (* renvoie le 2ème élément d'une liste *) 2 | | e1::e2::q -> e2................................................................................................... Warning 8: this pattern-matching is not exhaustive. Here is an example of a case that is not matched: (_::[]|[])
val deuxieme : 'a list -> 'a = <fun>
- : int = 7
Remarque : OCaml nous dit que notre pattern matching ne couvre pas tous les cas. En effet, notre fonction ne dit pas quoi faire dans le cas où l contient 0 ou 1 élément. Il s'agit cependant d'un warning et pas d'une erreur, ce qui veut dire que OCaml exécute quand même l'instruction mais nous prévient d'un problème potentiel.
deuxieme [] (* donne une exception *)
Exception: Match_failure ("[6]", 1, 17).
Called from file "toplevel/toploop.ml", line 208, characters 17-27
Voici comment on peut considérer tous les cas possibles :
exception NotDefined;;
let deuxieme l = match l with (* renvoie le 2ème élément d'une liste *)
| [] -> raise NotDefined (* cas où la liste est vide *)
| [e] -> raise NotDefined (* cas où la liste n'a qu'un élément **)
| e1::e2::q -> e2;; (* cas où la liste a au moins 2 éléments *)
deuxieme [4; 7; 3]
exception NotDefined
val deuxieme : 'a list -> 'a = <fun>
- : int = 7
On peut aussi utiliser underscore (_) dans un match pour signifier "dans tous les cas". Par exemple, on peut regrouper les deux premiers cas de deuxieme :
let deuxieme l = match l with
| e1::e2::q -> e2
| _ -> raise NotDefined (* dans tous les autres cas *)
val deuxieme : 'a list -> 'a = <fun>
Comme un match considère les cas de haut en bas, il faut mettre | _ -> en dernier sinon l'autre cas ne serait jamais exécuté.
Remarque underscore est aussi utilisé lorsque l'on ne souhaite pas nommer une variable (comme en Python) :
let p = (1, 2) in
let x, _ = p in (* récupère seulement x *)
x
- : int = 1
for _=0 to 5 do (* autre exemple : exécuter 6 fois un for sans utiliser de variable*)
()
done
- : unit = ()
Exercice
Écrire une fonction split : 'a list -> 'a list * 'a list pour séparer une liste en deux listes de même taille (à 1 près). Les éléments d'indices pairs seront dans la 1ère liste, les autres dans la 2ème liste.
Solution
let rec split l = match l with
| [] -> [], []
| [e] -> [e], [] (* si la liste n'a qu'un élément e *)
| e1::e2::q -> let q1, q2 = split q in
e1::q1, e2::q2 in
split [1; 2; 3; 4]
- : int list * int list = ([1; 3], [2; 4])
Exercice
Écrire une fonction concat : 'a list -> 'a list -> 'a list renvoyant une liste composée des deux listes en argument, l'une après l'autre.
Solution
let rec concat l1 l2 = match l1 with (* ici il est préférable de faire un match sur l1 seulement *)
| [] -> l2
| e::q -> e::concat q l2 in
concat [1; 2] [3; 4]
- : int list = [1; 2; 3; 4]
Remarque La fonction de l'exercice précédent existe déjà avec l'opérateur @ :
[1; 2; 3] @ [4; 5] (* concatène les deux listes et en renvoie une nouvelle *)
- : int list = [1; 2; 3; 4; 5]
Il est possible de décomposer plusieurs valeurs dans le même match, en les mettant sous forme de tuple :
let rec egal l1 l2 = match l1, l2 with (* teste si l1 = l2 *)
| [], [] -> true
| e::q, [] -> false (* l1 est non vide et l2 est vide *)
| [], e::q -> false (* l1 est vide et l2 est non vide *)
| e1::q1, e2::q2 -> e1 = e2 && egal q1 q2;;
val egal : 'a list -> 'a list -> bool = <fun>
egal [1; 2; 3] [1; 2; 3];;
egal [1; 2; 3] [1; 2];;
- : bool = true
- : bool = false
when¶
when permet de mettre une condition sur un cas d'un pattern matching. Il peut remplacer un if. Par exemple :
let rec positifs l = match l with (* renvoie la liste des éléments positifs de l *)
| [] -> []
| e::q when e > 0 -> e::positifs q (* on rajoute e à la liste de retour s'il est positif *)
| e::q -> positifs q;; (* sinon on ajoute seulement les éléments positifs de q *)
val positifs : int list -> int list = <fun>
Accumulateur de liste¶
Écrivons une fonction récursive rev pour inverser les éléments d'une liste. La méthode classique utilise un accumulateur (qu'on avait déjà utilisé pour calculer les termes de la suite de Fibonacci).
let rec rev acc l = match l with (* acc va servir à construire le résultat (la liste à l'envers) *)
| [] -> acc
| e::q -> rev (e::acc) q;;
rev [] [1; 2; 3] (* test *)
val rev : 'a list -> 'a list -> 'a list = <fun>
- : int list = [3; 2; 1]
Dans l'appel rev [] l, le premier élément x de l est celui qui est ajouté en premier à l'accumulateur et, comme tous les éléments suivants de l sont ajoutés au début de l'accumulateur (donc avant x), x se retrouve à la fin de l'accumulateur quand rev arrive sur le cas de base.
Le premier élément x se retrouve donc en dernier de l'accumulateur : on a bien inversé les éléments de l.