Laurent Le Brun

Le pattern matching (filtrage de motif) est une fonctionnalité classique de ML/Haskell. Curieusement, on ne la retrouve que dans peu d'autres langages.

Pattern matching

Le pattern matching travaille sur des valeurs et cherche à reconnaitre la forme de la valeur d'entrée. On peut voir ça comme un switch en beaucoup plus puissant.

La syntaxe est :

[fsharp]
match <expression> with
 | <motif> -> <expression>
 | <motif> -> <expression>
 | <motif> -> <expression>

Un match renvoie donc une valeur (contrairement au C/C++). Par exemple :

[fsharp]> match true with
 | true -> 4
 | false -> 8;;
val it : int = 4

Ici, on teste la valeur "true" et on essaie de la faire correspondre avec les deux motifs : true et false. Les motifs sont des valeurs constantes, un test d'égalité (entre la valeur et le motif) est fait.

Voici un 2e exemple avec des tuples :

[fsharp]
> let imply v =
  match v with
   | true, true -> true
   | true, false -> false
   | false, true -> true
   | false, false -> true;;
val imply : bool * bool -> bool

La fonction imply prend un argument v de type bool * bool (un couple de booléens). On teste la valeur v selon les différents motifs, comme le ferait une table de vérité. Si l'on ne souhaite pas énumérer tous les cas, il est possible d'utiliser des « jokers » :

[fsharp]
> let imply v =
  match v with
   | true, x -> x
   | false, _ -> true;;
val imply : bool * bool -> bool

Le premier motif se lit : un couple, dont la première valeur est true et la 2e est une valeur quelconque x. Si v peut être mis en correspondance avec ce motif, on renvoie alors la valeur x.

La deuxième motif se lit : un couple, dont la première valeur est true et la 2e est une valeur quelconque (que l'on ne nomme pas). On renvoie alors true.

[fsharp]
> let swap v =
  match v with
   | x, y -> y, x;;
val swap : 'a * 'b -> 'b * 'a

> swap (4, 6);;
val it : int * int = (6, 4)

Dans la fonction swap, le pattern match forcément tous les cas possibles : le type d'entrée est un couple, on échange ses deux valeurs. Si l'on essaie d'appeler swap avec autre chose qu'un couple (valeur simple, triplet ou autre), une erreur se produit (regardez le type de la fonction).

Détection d'erreur

Le pattern matching est quelque chose de relativement sûr, car le compilateur peut vérifier un certain nombre d'erreurs classiques.

[fsharp]
> let foo v =
  match v with
   | x, x -> 42;;

Cela génère une erreur : on essaie de définir deux le même identifiant. Si l'on souhaite définir le motif correspondant à deux valeurs égales, il faut utiliser une garde (voir plus loin).

[fsharp]
> let bar v =
  match v with
   | true, false -> 42
   | false, true -> 21;;

Un avertissement est généré : certaines valeurs ne corespondent à aucun motif (true, true par exemple).

[fsharp]
> let bar v =
  match v with
   | true, x -> 42
   | true, false -> 21
   | _ -> 18;;

Le compilateur signale que la deuxième règle ne sera jamais utilisée : en effet, (true, false) correspond déjà au premier motif. Les motifs sont testés dans l'ordre ; dès qu'il y en a un qui correspond, les suivants ne sont pas testés.

Autres syntaxes

Le mot-clé function sert à introduire une fonction anonyme en faisant du pattern matching sur son argument.

[fsharp]
> let rec fact = function
   | 0 -> 1
   | n -> n * fact (n - 1);;
val fact : int -> int

> fact 5;;
val it : int = 120

Ce mot-clé function est très pratique, il aide à écrire du code concis et clair. On le rencontre assez fréquemment dans les codes.

Si l'on souhaite faire du pattern matching avec un seul motif, il est possible de le faire dans le "let" dans la déclaration.

[fsharp]
let swap (x, y) = y, x

De fait, à chaque fois que l'on déclare une fonction, on effectue une sorte de matching : dans « let succ n = n + 1 », l'argument de la fonction succ sera mis en correspondance avec n.

Si l'on souhaite renvoyer la première valeur d'un couple, il suffit alors d'écrire :

[fsharp]
let fst (x, _) = x    // ces deux fonctions sont déjà
let snd (_, x) = x    // dans la bibliothèque standard

Pattern matching et listes

Le pattern matching permet de décomposer un type selon sa définition. Une liste est définie comme étant soit vide, soit un élément suivi d'une liste. Le filtrage de motif sur une liste suit ce principe :

[fsharp]
> let head = function
 | [] -> 42
 | h :: _ -> h;;
val head : int list -> int

Le premier motif teste si la valeur est une liste vide. Le deuxième teste si la valeur est un élément h, suivi d'une liste quelconque.

La fonction a un type « int list -> int » parce qu'en cas de liste vide, on renvoie un int, 42. Le type de h doit donc être du même type, et par conséquent, toute la liste doit être composée d'entiers. L'inférence de types se base sur de nombreuses déductions (pas toujours évidentes à voir), souvent mieux que si on avait essayé de le faire à la main.

Voici un autre exemple de motif sur des listes :

[fsharp]
> let rec sum = function
 | [] -> 0
 | h :: l -> h + sum l;;
val sum : int list -> int

Par récursion, on définit la somme d'une liste :

• la somme d'une liste vide est 0
• la somme d'une liste commençant par une valeur h est : h + la somme

des éléments restants.

Exercice : écrire la fonction qui calcule le nombre d'éléments d'une liste. Puis, en faire une autre qui renvoie la plus grande valeur de la liste.

Motifs complexes

[fsharp]
> let foo = function
 | [1; 2; 3; 4] -> true
 | _ -> false;;

Le motif doit être une valeur constante, qui ne nécessite aucun calcul. On verra plus tard comment faire des motifs plus élaborés (par exemple avec des expressions rationnelles) qui effectuent des calculs (on appelle cela des active patterns).

[fsharp]
> let foo = function
 | [|1; 2|] -> true
 | _ -> false;;
val foo : int array -> bool

Même principe pour un tableau. Remarque importante : on ne peut pas tester si un tableau commence par une valeur ou s'il possède un élément, puisque cela nécessiterait des calculs (un tableau n'est pas défini de façon récursive comme les listes).

[fsharp]
> let foo = function
 | [0; x] | [x; 0] -> x
 | _ -> 42;;
val foo : int list -> int

La barre verticale indique l'alternative. Si la liste contient seulement 2 éléments et l'un d'entre eux vaut 0, la fonction l'autre valeur.

[fsharp]
> let foo = function
 | [(2, _) as x] | [_; (4, _) as x] -> x
 | _ -> 0, 0;;
val foo : (int * int) list -> int * int

Le "as" sert à associer un nom au motif précédent. Ici, x est lié au couple qui précède. Quelques exemples pour les valeurs de retour :

[fsharp]
> foo [2, 4];;
val it : int * int = (2, 4)
> foo [3, 5; 4, 1];;
val it : int * int = (4, 1)
> foo [3, 5; 3, 1];;
val it : int * int = (0, 0)
> foo [2, 5; 4, 1; 8, 0];;
val it : int * int = (0, 0)

> let rec prod = function
   | [] -> 1
   | (0, 0) :: l -> prod l
   | ((0, x) | (x, 0)) :: l -> x * prod l
   | (x, y) :: l -> x * y * prod l;;
val prod : (int * int) list -> int

Cette fonction renvoie le produit des éléments d'une liste de couples, en ignorant les 0.

[fsharp]
> prod [1, 2; 3, 4; 0, 3; 5, 0];;
val it : int = 360

Exemple simple pour déclarer plusieurs valeurs en même temps :

[fsharp]
> let x, y = 4, 2;;

> let x, y as z = 4, 2;;

On définit x, y et z en même temps (z est un couple ; x et y, deux entiers).

[fsharp]
> let rec map f = function
   | [] -> []
   | e::l -> (f e) :: map f l;;
val map : ('a -> 'b) -> 'a list -> 'b list

> map ((+) 4) [1..6];;
val it : int list = [5; 6; 7; 8; 9; 10]

La fonction map (appelée List.map dans la bibliothèque) applique une fonction donnée sur chaque élément d'une liste. Elle construit la nouvelle liste (l'ancienne est toujours accessible et n'est pas modifiée).

Si l'on veut ajouter une condition à un motif, il faut utiliser une garde : c'est le mot-clé when.

[fsharp]
> let pair = function
   | n when n % 2 = 0 -> n
   | n -> n + 1;;
val pair : int -> int

Il faut utiliser une garde si l'on souhaite faire du pattern matching par rapport à un identifiant existant. La fonction suivante teste si un élément est présent dans une liste :

[fsharp]
> let rec mem x = function
  | e::l when e = x -> true
  | _::l -> mem x l
  | [] -> false;;

val mem : 'a -> 'a list -> bool

Si des exemples ne sont pas clairs, n'hésitez pas à demander des précisions.