L06 - Pattern matching
By Laurent Le Brun on Wednesday, November 14 2007, 23:09 - [FR] Cours F# - Permalink
Cette page explique le filtrage par motif. C'est une fonctionnalité extrêmement puissante issue du monde fonctionnel.
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.
Comments
Merci pour les explications, je connaissais le pattern matching mais ce n'était pas aussi clair qu'à présent.