Types de données et filtrage de motif
Listes chaînées
Comme en Perl, la notion de liste est directement supportée dans le langage OCaml. En OCaml, tous les éléments d'une liste doivent avoir le même type. Une liste s'écrit :
[1; 2; 3]
(Remarquez l'utilisation de points-virgules, et non de virgules).
[]
est la liste vide.
Une liste a une tête (le premier élément) et une queue (les
autres éléments). La tête est un élément, la queue est une liste, donc
dans cet exemple la tête est l'entier 1
alors que la queue est la
liste [2; 3]
.
Une autre façon d'écrire une liste est d'utiliser l'opérateur cons
tête :: queue
. Toutes les expressions suivantes sont donc équivalentes :
[1; 2; 3]
1 :: [2; 3]
1 :: 2 :: [3]
1 :: 2 :: 3 :: []
Pourquoi mentionner l'opérateur cons ? Et bien nous en aurons besoin un peu plus bas, pour faire du filtrage (pattern matching) sur les listes.
Le type d'une liste chaînée
Le type d'une liste chaînée d'entiers est int list
, et plus
généralement le type d'une liste chaînée de toto
s est toto list
.
Cela implique que tous les éléments d'une liste chaînée doivent avoir le
même type; Il existe des types polymorphiques de listes (càd 'a list
),
très utile pour écrire des fonctions manipulant des "listes de n'importe
quoi" de manière générique. (Mais 'a list
ne signifie pas que les
différents éléments d'une liste peuvent avoir des types différents -
vous ne pouvez pas utiliser ce type polymorphique pour construire,
disons, une liste d'entiers et de chaînes. Le sens de cette notation est
que les éléments de la liste peuvent être n'importe quoi, mais tous "du
même type de n'importe quoi").
La fonction length
définie dans le module standard de OCaml List
en
est un bon exemple. Peu importe si une liste contient des entiers, des
chaînes, des objets ou des ratons-laveurs, la fonction List.length
peut être utilisée dessus. Le type de List.length
est donc :
List.length : 'a list -> int
Structures
Le C et le C++ proposent le concept simple de struct
, abbréviation de
structure. En Java on peut utiliser des classes à la place, mais c'est
beaucoup plus laborieux.
Considérons cette simple structure C :
struct paire_dentiers {
int a, b;
};
L'équivalent le plus simple en OCaml sont les n-uplets (tuples),
comme la paire (3, 4)
qui a pour type int * int
. Contrairement aux
listes, les n-uplets peuvent contenir des éléments de types différents,
par exemple (3, "hello", 'x')
qui a pour type int * string * char
.
Une manière légèrement plus complexe de traduire les struct C est d'utiliser un enregistrement (record). Les enregistrements, comme les structs C, permettent de nommer leurs composants. Les composants des n-uplets ne peuvent pas être nommées, et il faut se souvenir de l'ordre dans lequel ils apparaissent. Voici l'enregistrement équivalent au struct C ci-dessus :
# type paire_dentiers = { a : int; b : int };;
type paire_dentiers = { a : int; b : int; }
Ceci définit le type, et voici comment créer effectivement des valeurs de ce type :
# { a=3; b=5 };;
- : paire_dentiers = {a = 3; b = 5}
Remarquez l'utilisation de « : » dans la définition du type et de « = » pour créer des valeurs de ce type.
Voici un exemple d'utilisation des enregistrements, testé avec la boucle interactive :
# type paire_dentiers = { a : int; b : int };;
type paire_dentiers = { a : int; b : int; }
# {a=3; b=5};;
- : paire_dentiers = {a = 3; b = 5}
# {a=3};;
Error: Some record fields are undefined: b
Donc OCaml refuse de laisser certains champs d'un enregistrement non définis.
Variants (unions marquées et énumérations)
Le concept d'"union marquée" n'existe pas vraiment en C, bien qu'il existe dans le compileur gcc. Voici comment on traduit d'habitude une union marquée en C:
struct foo {
int type;
#define TYPE_INT 1
#define TYPE_PAIR_OF_INTS 2
#define TYPE_STRING 3
union {
int i; // Si type == TYPE_INT.
int pair[2]; // Si type == TYPE_PAIR_OF_INTS.
char *str; // Si type == TYPE_STRING.
} u;
};
Je suppose que nous avons tous déjà vu ça, et ce n'est pas beau à voir.
Pour commencer, ce n'est pas sûr : le programmeur peut accidentellement
utiliser, disons, le champ u.i
quand c'est en fait une chaîne qui est
stockée dans la structure. Ensuite, le compilateur ne peut pas
facilement vérifier que tous les types ont été considérés dans les
instructions switch
(on peut utiliser un type enum
pour se prémunir
contre ce problème précis). Le programmeur peut aussi oublier de
modifier le champ type
, ce qui peut procurer des heures de jeu. Pour
finir, c'est lourdingue.
Voici l'équivalent en OCaml, élégant et concis:
# type foo =
| Nothing
| Int of int
| Pair of int * int
| String of string;;
type foo = Nothing | Int of int | Pair of int * int | String of string
Voilà pour la définition du type. Au début de chacune des sections,
séparées par des |
, se trouve un constructeur. On peut les nommer
comme on veut, tant que leur nom commence par une capitale. Si un
constructeur peut être utilisé pour définir une valeur, il est suivi de
of
et d'un type, qui lui commence par une minuscule. Dans l'exemple
ci-dessus, Nothing est utilisé comme une constante, alors que les autres
constructeurs définissent des valeurs.
Pour créer effectivement des valeurs de ce type, on peut écrire:
# Nothing;;
- : foo = Nothing
# Int 3;;
- : foo = Int 3
# Pair (4, 5);;
- : foo = Pair (4, 5)
# String "hello"
(* etc. *);;
- : foo = String "hello"
Toutes ces expressions ont pour type foo
.
Remarquez l'utilisation de of
dans la définition du type, qui ne se
retrouve PAS dans l'écriture des valeurs de ce type.
Par extension, un simple enum
C définit comme
enum sign { positive, zero, negative };
peut être traduit en OCaml par
# type sign = Positive | Zero | Negative;;
type sign = Positive | Zero | Negative
Variants récursifs (utilisés pour les arbres)
Les variants peuvent être récursifs, ce qui est souvent utilisé pour définir des structures de données arborescentes. C'est vraiment là que se révèle l'expressivité des langages fonctionnels :
# type binary_tree = Leaf of int | Tree of binary_tree * binary_tree;;
type binary_tree = Leaf of int | Tree of binary_tree * binary_tree
Voilà quelques arbres binaires. Comme exercice, essayez de les dessiner sur un bout de papier.
# Leaf 3;;
- : binary_tree = Leaf 3
# Tree (Leaf 3, Leaf 4);;
- : binary_tree = Tree (Leaf 3, Leaf 4)
# Tree (Tree (Leaf 3, Leaf 4), Leaf 5);;
- : binary_tree = Tree (Tree (Leaf 3, Leaf 4), Leaf 5)
# Tree (Tree (Leaf 3, Leaf 4), Tree (Tree (Leaf 3, Leaf 4), Leaf 5));;
- : binary_tree =
Tree (Tree (Leaf 3, Leaf 4), Tree (Tree (Leaf 3, Leaf 4), Leaf 5))
Variants paramétrés
L'arbre binaire de la section précédente comporte un entier à chaque feuille, mais comment faire pour décrire la forme de la structure de données, en laissant le choix de ce qui doit être stocké dans chaque feuille pour plus tard ? On peut utiliser un variant paramétré (ou polymorphique), comme ceci :
# type 'a binary_tree =
| Leaf of 'a
| Tree of 'a binary_tree * 'a binary_tree;;
type 'a binary_tree = Leaf of 'a | Tree of 'a binary_tree * 'a binary_tree
C'est le type général. Le type où chaque feuille stocke un entier
s'appelle int binary_tree
. De la même façon, le type où chaque feuille
stocke une chaîne s'appelle string binary_tree
. Pour l'exemple suivant
nous allons taper des valeurs dans la boucle interactive, et laisser le
système d'inférence de types nous donner leurs types :
# Leaf "hello";;
- : string binary_tree = Leaf "hello"
# Leaf 3.0;;
- : float binary_tree = Leaf 3.
Remarquez que le nom des types est à l'envers (arbre binaire de
flottants → float binary_tree). C'est comparable avec le nom des
types pour les listes, i.e. int list
, etc.
En fait ce n'est pas une coïncidence si 'a list
est écrit lui aussi « à
l'envers ». Les types listes ne sont que des types variants paramétrés,
avec une définition légèrement spéciale :
type 'a list = [] | :: of 'a * 'a list (* ceci n'est pas du vrai code OCaml *)
En fait la définition ci-dessus ne compile pas. La définition suivante, très similaire, compile correctement :
# type 'a list = Nil | :: of 'a * 'a list;;
Error: Syntax error
# Nil;;
Error: Unbound constructor Nil
# 1 :: Nil;;
Error: This variant expression is expected to have type int list
The constructor Nil does not belong to type list
# 1 :: 2 :: Nil;;
Error: This variant expression is expected to have type int list
The constructor Nil does not belong to type list
Rappelez vous quand nous avons dit précédemment que les listes pouvaient
être écrites de deux façons, soit sous la forme syntaxiquement édulcorée
[1; 2; 3]
ou sous la forme plus formelle 1 :: 2 :: 3 :: []
. En
regardant la définition de 'a list
ci-dessus, l'origine de la syntaxe
formelle devrait vous paraître plus clairement.
Listes, structures et variants — Résumé
tableau en 3 colonnes avec nom et exemples de définition et de valeur.
list int list [1; 2; 3]
tuple int * string (3, "hello")
record type pair = { a = 3; b = "hello" }
{ a: int; b: string }
variant type foo =
| Int of int Int 3
| Pair of int * string
variant type sign =
| Positive Positive
| Zero Zero
| Negative
parameterized type 'a my_list =
variant | Empty Cons (1, Cons (2, Empty))
| Cons of 'a * 'a my_list
Filtrage (sur les structures de données)
Une "Fonctionnalité Vraiment Cool"(tm) des langages fonctionnels est leur capacité à démonter les structures de données et à effectuer du filtrage (pattern matching) sur les données. Ce n'est pas à proprement parler une propriété "fonctionnelle" - on pourrait très bien imaginer une nouvelle sorte de C qui offrirait ces mêmes services. Mais c'est tout de même une "Fonctionnalité Vraiment Cool".
Commençons par un problème réel : je veux représenter des expressions
mathématiques simples comme n * (x + y)
et effectuer les
multiplications symboliquement pour obtenir n * x + n * y
.
Définissons un type pour ces expressions:
# type expr =
| Plus of expr * expr (* means a + b *)
| Minus of expr * expr (* means a - b *)
| Times of expr * expr (* means a * b *)
| Divide of expr * expr (* means a / b *)
| Value of string (* "x", "y", "n", etc. *);;
type expr =
Plus of expr * expr
| Minus of expr * expr
| Times of expr * expr
| Divide of expr * expr
| Value of string
L'expression n * (x + y)
s'écrirait:
# Times (Value "n", Plus (Value "x", Value "y"));;
- : expr = Times (Value "n", Plus (Value "x", Value "y"))
Ecrivons une fonction qui affiche
Times (Value "n", Plus (Value "x", Value "y"))
comme n * (x + y)
. En
fait, je vais écrire deux fonctions, l'une qui convertit une expression
en une jolie chaîne, et une autre qui l'affiche (comme ça si j'ai envie
d'écrire la même chaîne dans un fichier, je n'aurais pas à réécrire la
fonction en entier juste pour ça).
# let rec to_string e =
match e with
| Plus (left, right) ->
"(" ^ to_string left ^ " + " ^ to_string right ^ ")"
| Minus (left, right) ->
"(" ^ to_string left ^ " - " ^ to_string right ^ ")"
| Times (left, right) ->
"(" ^ to_string left ^ " * " ^ to_string right ^ ")"
| Divide (left, right) ->
"(" ^ to_string left ^ " / " ^ to_string right ^ ")"
| Value v -> v;;
val to_string : expr -> string = <fun>
# let print_expr e =
print_endline (to_string e);;
val print_expr : expr -> unit = <fun>
(NB: L'opérateur ^
sert à concaténer les chaînes.)
Voilà la fonction d'affichage à l'oeuvre:
# print_expr (Times (Value "n", Plus (Value "x", Value "y")));;
(n * (x + y))
- : unit = ()
La forme générale pour le filtrage est:
match valeur with
| motif -> résultat
| motif -> résultat
...
Les motifs dans la colonne de gauche peuvent être simples, comme dans la
fonction to_string
ci-dessus, ou plus complexe et imbriqués. L'exemple
suivant est notre fonction de distribution symbolique de la
multiplication des expressions de la forme n * (x + y)
ou
(x + y) * n
, et pour cela on va utiliser un motif imbriqué :
# let rec multiply_out e =
match e with
| Times (e1, Plus (e2, e3)) ->
Plus (Times (multiply_out e1, multiply_out e2),
Times (multiply_out e1, multiply_out e3))
| Times (Plus (e1, e2), e3) ->
Plus (Times (multiply_out e1, multiply_out e3),
Times (multiply_out e2, multiply_out e3))
| Plus (left, right) ->
Plus (multiply_out left, multiply_out right)
| Minus (left, right) ->
Minus (multiply_out left, multiply_out right)
| Times (left, right) ->
Times (multiply_out left, multiply_out right)
| Divide (left, right) ->
Divide (multiply_out left, multiply_out right)
| Value v -> Value v;;
val multiply_out : expr -> expr = <fun>
La voilà en action:
# print_expr (multiply_out (Times (Value "n", Plus (Value "x", Value "y"))));;
((n * x) + (n * y))
- : unit = ()
Comment est-ce que marche la fonction multiply_out
? L'essentiel se
trouve dans les deux premiers motifs. Le premier est
Times (e1, Plus (e2, e3))
qui filtre les expressions de la forme
e1 * (e2 + e3)
. Regardez la colonne de droite en face de ce motif, et
assurez vous que son contenu équivaut à (e1 * e2) + (e1 * e3)
.
Le second motif fait la même chose pour les expressions de la forme
(e1 + e2) * e3
.
Les autres motifs ne modifient pas la forme de l'expression, mais font
le travail nécessaire d'appeler la fonction multiply_out
récursivement
sur leurs sous-expressions. Cela garantit que toutes les
sous-expressions de l'expression sont correctement transformées. (Si
vous n'étiez concernés que par la transformation de l'expression la plus
externe, tous ces motifs auraient pu être remplacés par une simple règle
e -> e
).
Est-ce que l'on peut effectuer l'opération inverse (càd factoriser au lieu de distribuer) ? Bien sûr ! (Mais c'est un peu plus compliqué...). La version suivante ne marche que pour l'expression la plus externe. Vous pourriez certainement l'améliorer pour gérer tous les niveaux de sous-expressions, et des cas plus complexes :
# let factorize e =
match e with
| Plus (Times (e1, e2), Times (e3, e4)) when e1 = e3 ->
Times (e1, Plus (e2, e4))
| Plus (Times (e1, e2), Times (e3, e4)) when e2 = e4 ->
Times (Plus (e1, e3), e4)
| e -> e;;
val factorize : expr -> expr = <fun>
# factorize (Plus (Times (Value "n", Value "x"),
Times (Value "n", Value "y")));;
- : expr = Times (Value "n", Plus (Value "x", Value "y"))
La fonction de factorisation ci-dessus introduit une paire de nouvelles
fonctionnalités. Vous pouvez ajouter ce qui s'appelle une garde à
chaque motif. Une garde est une condition précédée de when
, et qui
signifie que le filtrage n'est fructueux que si le motif correspond et
la condition après la clause when
est satisfaite.
match valeur with
motif [ when condition ] -> résultat
motif [ when condition ] -> résultat
...
La seconde fonctionalité est l'opérateur =
qui teste l'"égalité
structurelle" de deux expressions. Cela signifie qu'il descend
récursivement dans chacune de deux expressions pour vérifier qu'elles
sont identiques à tous les niveaux.
OCaml est capable de vérifier au moment de la compilation que tous les
cas sont couverts par vos motifs. J'ai modifié la définition du
type expr
précédent pour y ajouter le constructeur Product
:
# type expr = Plus of expr * expr (* means a + b *)
| Minus of expr * expr (* means a - b *)
| Times of expr * expr (* means a * b *)
| Divide of expr * expr (* means a / b *)
| Product of expr list (* means a * b * c * ... *)
| Value of string (* "x", "y", "n", etc. *);;
type expr =
Plus of expr * expr
| Minus of expr * expr
| Times of expr * expr
| Divide of expr * expr
| Product of expr list
| Value of string
J'ai ensuite recompilé la fonction to_string
sans modifications. OCaml
a renvoyé l'avertissement suivant :
# let rec to_string e =
match e with
| Plus (left, right) ->
"(" ^ to_string left ^ " + " ^ to_string right ^ ")"
| Minus (left, right) ->
"(" ^ to_string left ^ " - " ^ to_string right ^ ")"
| Times (left, right) ->
"(" ^ to_string left ^ " * " ^ to_string right ^ ")"
| Divide (left, right) ->
"(" ^ to_string left ^ " / " ^ to_string right ^ ")"
| Value v -> v;;
Warning 8: this pattern-matching is not exhaustive.
Here is an example of a case that is not matched:
Product _
val to_string : expr -> string = <fun>