Cours 1

Il existe plusieurs dialectes du langage Caml. La version officielle pour les concours est Caml light. La version de Caml installée sur les machines virtuelles est OCaml. Cette version diffère un peu de Caml light, en particulier dans le nommage de certaines fonctions usuelles prédéfinies.

Le fichier Caml /opt/camllight.ml définit des alias qui permettent d'utiliser les noms Caml light dans les programmes OCaml. Éxécutez la cellule ci-dessous pour rendre disponible les noms définis dans le fichier camllight.ml.

In [ ]:
#use "/opt/camllight.ml"

Ressources :

Les types CAML de base

Les entiers

Le type int représente les entiers.

In [ ]:
34
Out[ ]:
- : int = 34

Le langage Python permet de représenter n'importe quel entier, du moins dans les limites de la mémoire physique. Ceci se fait au détriment de la vitesse de calcul. Caml a choisi au contraire de s'appuyer directement sur le processeur. Sur une machine 64 bits, les entiers sont codés en complément à deux sur 63 bits. Les entiers représentables sont donc ceux de l'intervalle $[-2^{62}, 2^{62}-1]$ :

In [ ]:
min_int
Out[ ]:
- : int = -4611686018427387904
In [ ]:
max_int
Out[ ]:
- : int = 4611686018427387903
In [ ]:
max_int + 1
Out[ ]:
- : int = -4611686018427387904

Ces noms min_int et max_int sont prédéfinis.

On retrouve cette limite des 64 bits avec la bibliothèque Numpy qui privilégie également l'efficacité du calcul. Un langage de programmation offre au programmeur une machine virtuelle, une abstraction qui lui est propre. Cependant les contraintes de la machine physique ne peuvent pas être totalement ignorées. La conception d'un langage est une affaire de compromis.

In [ ]:
(13 + 4) * -8
Out[ ]:
- : int = -136
In [ ]:
23 / 4
Out[ ]:
- : int = 5
In [ ]:
27 mod 5
Out[ ]:
- : int = 2

Le mot-clé let permet d'associer un nom à une valeur.

In [ ]:
let n = 8
Out[ ]:
val n : int = 8
In [ ]:
let m = n + 6
Out[ ]:
val m : int = 14

Contrairement à Python, au sein d'un même programme Caml il n'y a a priori pas de raison de redéfinir un nom déjà associé à une valeur. Le terme de variable est d'ailleurs inapproprié. Il faut plutôt penser à une définition mathématique. Ce ne serait certainement pas une bonne idée de redéfinir une notation au milieu d'une démonstration mathématique.

Les réels

Les ordinateurs ne connaissent pas le continu. Seuls un nombre fini de réels sont représentables. Il s'agit plus précisément des nombres de la forme

$$v = s\times m\times 2^e$$

où $s$, $m$ et $e$ sont des entiers tels que

avec $\quad s=\pm 1$,$\quad$ $1\leq m\leq 2^{53}-1$ $\quad$ et$\quad$ $-1022\leq e\leq 1023$.

Ces nombres sont qualifiés de flottants (type float). Leur densité est la plus forte au voisinage de 0. Les opérations et fonctions mathématiques sur les réels se traduisent par des calculs approximatifs sur les flottants. Cette façon de représenter les réels n'est pas spécifique à Caml mais au processeur de la machine. Le codage précis sur 64 bits est défini par la norme IEEE 754.

In [ ]:
1e-3
Out[ ]:
- : float = 0.001
In [ ]:
1e308
Out[ ]:
- : float = 1e+308
In [ ]:
2. *. 3.14
Out[ ]:
- : float = 6.28

La norme IEEE 754 prévoit trois flottants spéciaux. Deux d'entre eux représentent $\pm\infty$. Le troisième signifie littéralement Not A Number.

In [ ]:
1e309
Out[ ]:
- : float = infinity
In [ ]:
infinity +. 1.
Out[ ]:
- : float = infinity
In [ ]:
-. infinity *. infinity
Out[ ]:
- : float = neg_infinity
In [ ]:
infinity -. infinity
Out[ ]:
- : float = nan
In [ ]:
nan +. 5.1
Out[ ]:
- : float = nan

Les noms infinity et nan sont prédéfinis.

Les entiers et les flottants sont deux types bien distincts en Caml. Les opérations arithmétiques sur les flottants sont notés avec un point pour les distinguer de celles sur les entiers.

In [ ]:
2. *. 3.14
Out[ ]:
- : float = 6.28

Il n'y a pas de nom prédéfini pour le réel $\pi$, plus précisément pour le flottant le plus proche de $\pi$. On peut le définir en utilisant la fonction $\arctan$ :

In [ ]:
let pi = 4. *. atan 1.0
Out[ ]:
val pi : float = 3.14159265358979312

Les fonctions mathématiques prennent en argument des flottants et non des entiers :

In [ ]:
atan 1
Out[ ]:
File "[22]", line 1, characters 5-6:
Error: This expression has type int but an expression was expected of type
         float
Characters 5-6:
  atan 1
       ^

Les conversions d'un type à l'autre doivent être explicites :

In [ ]:
float_of_int 1
Out[ ]:
- : float = 1.
In [ ]:
int_of_float 1.
Out[ ]:
- : int = 1
In [ ]:
atan (float_of_int 1)
Out[ ]:
- : float = 0.785398163397448279

Les booléens

Le type bool comporte les deux valeurs true et false.

In [ ]:
2 + 2 = 4
Out[ ]:
- : bool = true
In [ ]:
let flag = (2 * 2 = 5)
Out[ ]:
val flag : bool = false

Les opérateurs binaires ET et OU sont respectivement && et ||.

In [ ]:
true && false
Out[ ]:
- : bool = false
In [ ]:
true || false
Out[ ]:
- : bool = true
In [ ]:
not (3 < 5)
Out[ ]:
- : bool = false

Les valeurs booléennes interviennent en particulier dans les expressions conditionnelles :

In [ ]:
if 0 <> 0 then 1 + 1 else 2 + 2
Out[ ]:
- : int = 4

Contrairement à Python, la construction if then else est une expression et non pas une instruction. Cela signifie qu'elle possède une valeur. Cette valeur est celle de 1 + 1 ou de 2 + 2 selon que la valeur de 0 <> 0 est true ou false. Le type de cette expression est celui de 1 + 1 et de 2 + 2. Ceci sous-entend que ces deux expressions sont obligatoirement du même type :

In [ ]:
if 126 mod 7 = 0 then 12 else 9.4
Out[ ]:
File "[32]", line 1, characters 30-33:
Error: This expression has type float but an expression was expected of type
         int
Characters 30-33:
  if 126 mod 7 = 0 then 12 else 9.4
                                ^^^
In [ ]:
if 126 mod 7 = 0 then 12
Out[ ]:
File "[33]", line 1, characters 22-24:
Error: This expression has type int but an expression was expected of type
         unit
Characters 22-24:
  if 126 mod 7 = 0 then 12
                        ^^

Les caractères

Qu'est-ce qu'un caractère ?

La réponse moderne est : Un caractère est un élément de l'ensemble des caractères Unicode. Autrement dit l'ensemble des caractères est défini en extension. La liste des caractères est spécifiée par la norme Unicode et comprend plus de $110\,000$ caractères. Chaque caractère est identifié par un nombre appelé point de code.

Comment est représenté un caractère dans une machine ?

Un caractère est représenté par une séquence de un ou plusieurs octets conformément à une règle d'encodage. Il existe plusieurs normes d'encodage. Selon la langue, on privilégiera un encodage qui représente les caractères les plus fréquents sur un seul octet. La norme la plus répandue s'appelle UTF-8. Dans cette norme le é est représenté par les deux octets 195 et 169.

Il existe un jeu de caractères très restreint qui est encodé de la même façon dans toutes les normes d'encodage. Ces caractères sont appelés caractères ASCII. Ils sont encodés sur un seul octet avec le bit de gauche à 0. Il existe donc exactement 128 caractères ASCII en bijection naturelle avec les entiers de 0 à 127. C'est le jeu de caractères historique qui comprend en particulier les lettres non accentuées majuscules (65 à 90) et minuscules (+32 par rapport aux majuscules), les dix chiffres (48 à 57), des signes de ponctuations, le caractère espace (32) et le caractère saut de ligne (10).

Contrairement à Python, du moins dans sa version 3, un programme Caml ne manipule pas des caractères Unicode mais des octets. Le nom char est donc quelque peu trompeur.

Les octets entre 0 et 127 peuvent être représentés par leur caractère ASCII :

In [ ]:
'e'
Out[ ]:
- : char = 'e'

ou bien par leur valeur décimale :

In [ ]:
'\101'
Out[ ]:
- : char = 'e'

Par contre, les octets entre 128 et 255 n'ont pas de caractères associés :

In [ ]:
'\147'
Out[ ]:
- : char = '\147'

Le caractère é n'est pas un caractère ASCII. Par conséquent :

In [ ]:
'é'
Out[ ]:
File "[37]", line 1, characters 0-1:
Error: Syntax error
Characters 0-1:
  'é'
  ^

Le saut de ligne est désigné par :

In [ ]:
'\n'
Out[ ]:
- : char = '\n'

ou bien par

In [ ]:
'\010'
Out[ ]:
- : char = '\n'

Les chaînes de caractères

Une chaîne de caractères, type string, est une suite (finie) d'octets. Ces octets sont contigus dans la mémoire RAM de la machine physique ce qui permet la lecture d'un octet en temps constant c'est-à-dire un temps qui ne dépend pas de la longueur de la chaîne.

In [ ]:
"bonjour"
Out[ ]:
- : string = "bonjour"
In [ ]:
let s = "\097\123\130\110\032\144"
Out[ ]:
val s : string = "a{\130n \144"

La lecture d'un octet se fait en utilisant la syntaxe suivante :

In [ ]:
s.[0]
Out[ ]:
- : char = 'a'
In [ ]:
s.[1]
Out[ ]:
- : char = '{'
In [ ]:
s.[2]
Out[ ]:
- : char = '\130'

Caml n'accorde aucune signification particulière aux octets de la chaîne. Le programmeur peut par exemple décider qu'ils représentent des caractères Unicode encodés en UTF-8.

Voici par exemple le mot élève encodé en UTF-8 :

In [ ]:
"\195\169\108\195\118\101"
Out[ ]:
- : string = "\195\169l\195ve"

La fonction print_string s a pour effet d'envoyer la chaîne d'octets s sur la sortie standard. Dans l'environnement de ce notebook cette sortie interprète les octets comme des caractères encodés en UTF-8 :

In [ ]:
print_string "\195\169\108\195\168\118\101"
élève
Out[ ]:
- : unit = ()

Un programme Caml est lui-même un texte qui est encodé avant d'être transmis à l'interpréteur Caml. Dans l'environnement du notebook, ce texte est encodé en UTF-8. D'où :

In [ ]:
"élève"
Out[ ]:
- : string = "\195\169l\195\168ve"

En assemblant tous les notions qui précèdent on comprend alors que le code ci-dessous produit bien l'effet voulu :

In [ ]:
print_string "élève"
élève
Out[ ]:
- : unit = ()

Mais pour Caml la chaîne "élève" est bien une chaîne de 7 octets et non une chaîne de 5 caractères.

In [ ]:
string_length "élève"
Out[ ]:
- : int = 7
In [ ]:
"élève".[0]
Out[ ]:
- : char = '\195'
In [ ]:
"élève".[1]
Out[ ]:
- : char = '\169'
In [ ]:
"élève".[2]
Out[ ]:
- : char = 'l'

L'opérateur ^ permet de concaténer plusieurs chaînes :

In [ ]:
let salut = "Bonjour" ^ " les " ^ "gars"
Out[ ]:
val salut : string = "Bonjour les gars"

Les chaînes sont comparables selon l'ordre lexicographique :

In [ ]:
"bonjour" < "Salut"
Out[ ]:
- : bool = false

La fonction sub_string permet de créer une sous-chaîne :

In [ ]:
sub_string "Bonjour tout le monde" 8 4
Out[ ]:
- : string = "tout"

Les couples et multiplets

Deux valeurs peuvent être associées entre elles pour construire un couple :

In [ ]:
let cpl = "nuage", 7
Out[ ]:
val cpl : string * int = ("nuage", 7)

Le type de cette valeur est string * int. Les parenthèses sont facultatives tant qu'il n'y a pas d'ambiguité.

In [ ]:
let s, n = cpl
Out[ ]:
val s : string = "nuage"
val n : int = 7

Le code ci-dessus montre qu'il est possible de déconstruire le couple en deux valeurs séparées. On retrouve cette possibilité avec les tuples Python. Mais nous allons voir que Caml va beaucoup plus loin dans ce sens. C'est un aspect essentiel du langage Caml.

Les fonctions fst et snd renvoient respectivement la première et la seconde composante du couple :

In [ ]:
fst cpl
Out[ ]:
- : string = "nuage"
In [ ]:
snd cpl
Out[ ]:
- : int = 7

Les couples sont des types construits à partir de types plus élémentaires. Nous allons voir ci-dessous d'autres façons de construire des types à partir d'autres. Il est possible et souvent souhaitable de donner un nom spécifique à ces nouveaux types afin d'accroitre, pour nous humain, la signification véhiculée par le texte du programme.

In [ ]:
type point = float * float
Out[ ]:
type point = float * float
In [ ]:
let p : point = (5.0, 3.1)
Out[ ]:
val p : point = (5., 3.1)

Ci-dessus on a explicitement indiqué que la valeur p est du type point. Par défaut, Caml aurait inféré le type float * float :

In [ ]:
let q = (5.0, 3.1)
Out[ ]:
val q : float * float = (5., 3.1)

Le nom point n'est qu'un alias qui permet d'apporter plus de lisibilité au programme. Pour Caml il s'agit du même type :

In [ ]:
p = q
Out[ ]:
- : bool = true

Plus généralement, un multiplet de longueur quelconque peut être construit :

In [ ]:
4, p, "koala", 'z'
Out[ ]:
- : int * point * string * char = (4, (5., 3.1), "koala", 'z')

Les fonctions

In [ ]:
let f = function x -> x * x
Out[ ]:
val f : int -> int = <fun>

L'expression ci-dessus est une valeur du type int -> int. Il s'agit d'une fonction qui, à une valeur de type int associe une autre valeur de type int.

Python permet aussi de définir des objets de type function de cette façon :

lambda x : x * x

Mais Caml va beaucoup plus loin dans cette direction. Il va en fait jusqu'au bout de l'idée qui consiste à considérer les fonctions comme de simples valeurs ordinaires ayant leurs propres types. Ce trait est suffisamment marquant pour qualifier le langage Caml de langage fonctionnel.

In [ ]:
let f = function x -> x * x
Out[ ]:
val f : int -> int = <fun>

Caml a la faculté de déterminer lui-même le type exact de la fonction. Ici, l'opérateur * implique nécessairement que x soit un int et donc que f soit du type int -> int.

La principale opération que l'on peut réaliser sur une fonction est de la calculer sur une valeur particulière. Ceci se fait en juxtaposant la valeur fonctionnelle et la valeur sur laquelle on souhaite l'évaluer.

In [ ]:
f 5
Out[ ]:
- : int = 25

Dans une expression, l'opération de calcul d'une fonction a l'ordre de priorité la plus grande :

In [ ]:
f 6 + 1
Out[ ]:
- : int = 37

Les parenthèses sont utiles pour modifier l'ordre de priorité :

In [ ]:
f (6 + 1)
Out[ ]:
- : int = 49

Voici une définition de la fonction sinus cardinal :

In [ ]:
let sinusc = function
  x -> if x = 0. then 1. else (sin x) /. x
;;
  
sinusc 0.5 ;;

sinusc 0. ;;
Out[ ]:
val sinusc : float -> float = <fun>
Out[ ]:
- : float = 0.958851077208406
Out[ ]:
- : float = 1.

Remarquer la présence du double point-virgules. Un programme Caml est une succession de phrases. Les phrases se terminent par deux point-virgules accolés. Ces point-virgules peuvent dans certains cas être omis. C'est par exemple le cas pour la dernière phrase.

Caml propose une syntaxe alternative qui utilise un mécanisme appelé filtrage de motif ou pattern matching en anglais.

In [ ]:
let sinusc = function
  | 0. -> 1.
  | x  -> (sin x) /. x
;;

sinusc 0.5 ;;

sinusc 0. ;;
Out[ ]:
val sinusc : float -> float = <fun>
Out[ ]:
- : float = 0.958851077208406
Out[ ]:
- : float = 1.

Nous aborderons plus loin le principe général du filtrage de motif qui est une construction syntaxique fondamentale de Caml.

Fonctions de plusieurs variables

Le code ci-dessous définit une fonction qui, à une valeur de type int associe une valeur de type string -> char. Son type est donc int -> (string -> char).

In [ ]:
let getchar = function i -> (function s -> s.[i]) ;;
Out[ ]:
val getchar : int -> string -> char = <fun>

Le type indiqué par Caml est int -> string -> char car le symbole -> est considéré dans cette écriture comme étant associatif à droite.

Les parenthèses que nous avons utilisées peuvent donc être omises :

In [ ]:
let getchar = function i -> (function s -> s.[i]) ;;
Out[ ]:
val getchar : int -> string -> char = <fun>
In [ ]:
getchar 3
Out[ ]:
- : string -> char = <fun>
In [ ]:
(getchar 3) "jupyter"
Out[ ]:
- : char = 'y'

Les parenthèses précédentes ne sont pas nécessaires car le calcul d'une fonction est associatif à gauche

In [ ]:
getchar 3 "jupyter"
Out[ ]:
- : char = 'y'

Ceci nous permet de faire l'observation fondamentale suivante :

La fonction getchar peut être considérée comme une fonction de deux arguments. À un int et à un string elle fait correspondre un char.

La définition ci-dessus de la fonction getchar est un peu lourde. Caml supporte des syntaxes alternatives rigoureusement équivalentes :

In [ ]:
let getchar = fun i s -> s.[i] ;;
Out[ ]:
val getchar : int -> string -> char = <fun>
In [ ]:
let getchar i s = s.[i] ;;
Out[ ]:
val getchar : int -> string -> char = <fun>

Cette dernière forme est à privilégier car c'est la plus lisible. De plus, pour des fonctions non triviales, c'est-à-dire dépassant cinq ou six lignes de code, il convient de documenter clairement la fonction en indiquant :

  • sa spécification dans un commentaire placé avant le code,

  • sa signature, c'est-à-dire le type de ses arguments et le type de la valeur retournée.

In [ ]:
(** Retourne le caractère d'indice i de la chaîne s
*)
let getchar (i : int) (s : string) : char = 
  s.[i] 
;;
Out[ ]:
val getchar : int -> string -> char = <fun>

Forme curryfiée versus non curryfiée

La fonction getcharbis définie ci-dessous est différente de getchar. Elle n'a pas la même signature.

In [ ]:
let getcharbis (i, s) = s.[i]
Out[ ]:
val getcharbis : int * string -> char = <fun>
In [ ]:
getcharbis (3, "jupyter")
Out[ ]:
- : char = 'y'

La fonction getcharbis ne prend pas deux arguments mais un seul qui est de type int * string. Il y a une bijection évidente entre l'ensemble des fonctions de type int -> string -> char et l'ensemble des fonctions de type int * string -> char.

La forme getchar est appelée la forme curryfiée. Elle est préférable à la forme getcharbis. La forme curryfiée permet de définir une fonction partielle à partir d'une fonction plus générale à plusieurs arguments.

In [ ]:
let firstchar = getchar 0
Out[ ]:
val firstchar : string -> char = <fun>
In [ ]:
firstchar "Bonjour"
Out[ ]:
- : char = 'B'

Polymorphisme

In [ ]:
let id x = x
Out[ ]:
val id : 'a -> 'a = <fun>

Le code ci-dessus définit la fonction identité. Clairement, Caml ne peut pas inférer le type précis de cette fonction. Par contre, il détecte que la fonction retourne une valeur du même type que l'argument. Ceci se matérialise par la signature 'a -> 'a. On dit que la fonction id est polymorphe.

In [ ]:
id "boujour"
Out[ ]:
- : string = "boujour"

Nous avons rencontré plus haut les fonctions fst et snd qui retournent respectivement la première et la seconde composantes d'un couple. Ces deux fonctions sont également polymorphes.

In [ ]:
fst
Out[ ]:
- : 'a * 'b -> 'a = <fun>
In [ ]:
snd
Out[ ]:
- : 'a * 'b -> 'b = <fun>

Les opérateurs de comparaison sont également polymorphes :

In [ ]:
3 < 5
Out[ ]:
- : bool = true
In [ ]:
"bonjour" < "bonsoir"
Out[ ]:
- : bool = true

À propos, les opérateurs binaires ne sont pas autre chose que des fonctions de deux variables. La différence est très superficielle :

  • leur nom est formé de caractères qui ne sont pas des lettres,

  • ils sont placés entre les deux arguments (position infixe) plutôt qu'avant eux (position prefixe).

Il est possible d'utiliser un opérateur en position prefixe en l'écrivant avec des parenthèses :

In [ ]:
(<)
Out[ ]:
- : 'a -> 'a -> bool = <fun>
In [ ]:
(<) 3 5
Out[ ]:
- : bool = true

Il est également possible de définir de nouveaux opérateurs :

In [ ]:
let (|>) x f = f x ;;
Out[ ]:
val ( |> ) : 'a -> ('a -> 'b) -> 'b = <fun>
In [ ]:
"bonjour" |> string_length |> float_of_int |> sqrt
Out[ ]:
- : float = 2.64575131106459072
In [ ]:
sqrt (float_of_int (string_length "bonjour"))
Out[ ]:
- : float = 2.64575131106459072

Fonctions récursives

Le code ci-dessous définit la fonction factorielle :

In [ ]:
(** Retourne la factorielle de n
*)
let rec fac = function
  | 0 -> 1
  | n -> n * fac (n - 1)
;;
Out[ ]:
val fac : int -> int = <fun>
In [ ]:
fac 5
Out[ ]:
- : int = 120

Cette définition de fac ressemble beaucoup à la seconde définition de sinusc que nous avons donnée plus haut. La différence notable est que la fonction fac apparaît dans sa propre définition. Ceci tient au fait que nous utilisons une définition par récurrence de $n!$ :

$$\begin{cases} 0! = 1 \\ n! = n\times (n-1)! \quad\text{pour } n\gt 0 \end{cases}$$

Le mot-clé rec indique explicitement qu'il s'agit bien d'une définition récursive de fac. Sans ce mot-clé, Caml chercherait à utiliser une valeur fac préexistante pour définir ce nouveau fac.

Si l'on voit cette définition comme une définition mathématique, cela ne pose pas de difficultés particulières. Cependant, les définitions Caml ne sont pas uniquement des définitions mathématiques. Elles ont également comme objectif de décrire les calculs que doit effectuer la machine pour évaluer la fonction. Il nous faudra donc revenir en détail sur la façon dont Caml se débrouille avec cette définition pour mener ses calculs. Mais pour le moment restons au niveau de la définition mathématique.

La construction de types

Les enregistrements

Un type enregistrement est comparable à un multiplet, mais il permet de donner des noms explicites aux différentes composantes du type :

In [ ]:
type complexe = {re : float ; im : float}
Out[ ]:
type complexe = { re : float; im : float; }
In [ ]:
let i = {re = 0.; im = 1.}
Out[ ]:
val i : complexe = {re = 0.; im = 1.}
In [ ]:
i.re
Out[ ]:
- : float = 0.
In [ ]:
i.im
Out[ ]:
- : float = 1.

La code ci-dessous définit deux valeurs z1 et z2 dans une même phrase Caml.

In [ ]:
let z1 = {re = 0.5; im = 0.7}
and z2 = {re = -0.5; im = 0.7}
;;
Out[ ]:
val z1 : complexe = {re = 0.5; im = 0.7}
val z2 : complexe = {re = -0.5; im = 0.7}
In [ ]:
let mult z z' = 
  let x, y = z.re, z.im
  and x', y' = z'.re, z'.im
  in
  {re = x *. x' -. y *. y'; 
  im = x *. y' +. x' *. y}
;;

mult z1 z2
Out[ ]:
val mult : complexe -> complexe -> complexe = <fun>
Out[ ]:
- : complexe = {re = -0.74; im = 0.}

La définition de la fonction mult ci-dessus utilise la construction syntaxique let ... in .... Cette syntaxe permet de définir des noms ayant une portée limitée à l'expression qui suit le mot-clé in.

In [ ]:
let delta = 
  let a = 1. and b = 2. and c = 3. in
  b *. b -. 4. *. a *. c
Out[ ]:
val delta : float = -8.

Les types sommes

Si les valeurs booléennes n'étaient pas prédéfinies en Caml, on pourrait les définir de cette façon :

In [ ]:
type boolean = True | False ;;
Out[ ]:
type boolean = True | False

Le type boolean est défini comme la réunion disjointe de deux ensembles réduits aux singletons {True} et {False}.

Voici une façon de représenter un jeu de cartes :

In [ ]:
type couleur = Pique | Coeur | Carreau | Trefle
and carte =
  | As of couleur
  | Roi of couleur
  | Dame of couleur
  | Valet of couleur
  | Numero of int * couleur
;;
Out[ ]:
type couleur = Pique | Coeur | Carreau | Trefle
and carte =
    As of couleur
  | Roi of couleur
  | Dame of couleur
  | Valet of couleur
  | Numero of int * couleur

Définissons maintenant des valeurs de type carte :

In [ ]:
let c1 = Dame Coeur
and c2 = Numero (9, Pique)
Out[ ]:
val c1 : carte = Dame Coeur
val c2 : carte = Numero (9, Pique)

On peut comparer deux valeurs de même type :

In [ ]:
c1 = c2
Out[ ]:
- : bool = false

Mais si les valeurs sont de types différents, la comparaison n'a pas de sens et provoque une erreur :

In [ ]:
c2 = (9, Pique)
Out[ ]:
File "[111]", line 1, characters 5-15:
Error: This expression has type 'a * 'b
       but an expression was expected of type carte
Characters 5-15:
  c2 = (9, Pique)
       ^^^^^^^^^^

Pique, Coeur, Carreau et Trefle sont des constructeurs constants. Le constructeur Dame peut se voir comme une fonction de type couleur -> carte. De même, le constructeur Numéro est du type int * couleur -> carte.

Les constructeurs débutent par une lettre capitale ce qui les distinguent des noms courants définis avec let.

In [ ]:
let est_figure = function
  | As _    -> true
  | Roi _   -> true
  | Dame _  -> true
  | Valet _ -> true
  | _       -> false
;;

est_figure c1 ;;

est_figure c2 ;;
Out[ ]:
val est_figure : carte -> bool = <fun>
Out[ ]:
- : bool = true
Out[ ]:
- : bool = false

Le code ci-dessus utilise à nouveau le filtrage de motif. Il est possible et plus explicite d'écrire le code de la façon suivante :

In [ ]:
(** Indique si la carte c est une figure
*)
let est_figure (c : carte) : bool =
  match c with
  | As _    -> true
  | Roi _   -> true
  | Dame _  -> true
  | Valet _ -> true
  | _       -> false
;;
Out[ ]:
val est_figure : carte -> bool = <fun>
  • Le code des lignes 4 à 9 est une expression.

  • Le type de cette expression est le type des expressions situées à droite des flèches, donc ici bool.

  • Caml évalue tout d'abord l'expression entre les mots-clés match et with. Il cherche alors à déconstruire la valeur de cette expression pour l'accorder à l'un des motifs situés à gauche des flèches.

  • Les motifs sont testés dans l'ordre. Le premier qui s'accorde est sélectionné et l'expression prend la valeur située à droite de la flèche.

  • Le filtrage doit être exhaustif : pour toute valeur de type carte il doit exister un motif qui s'accorde avec cette valeur.

  • Le _ signifie n'importe qu'elle valeur. Le dernier motif sera donc nécessairement sélectionné si aucun autre motif ne l'a été auparavant.

Voici un autre exemple de filtrage de motif :

In [ ]:
let max = function
  | (x, y) when x > y -> x
  | (x, y)            -> y
;;
Out[ ]:
val max : 'a * 'a -> 'a = <fun>

Si un nom courant (en minuscules) apparaît dans un motif alors ce nom s'accorde avec n'importe quelle expression, tout comme _. La différence est que ce nom peut ensuite être utilisé dans l'expression à droite de la flèche.

Le premier motif du code ci-dessus comporte par ailleurs une garde, c'est-à-dire une condition introduite par le mot-clé when. Pour que le motif soit sélectionné il faut de plus que la condition x > y soit vraie.