OCaml
Correspondance de motif

Fonction factorielle à l'aide de la correspondance de motifs

let rec factorial n = match n with
| 0 | 1 -> 1
| n -> n * (factorial (n - 1))

Cette fonction correspond à la fois aux valeurs 0 et 1 et les mappe au cas de base de notre définition récursive. Ensuite, tous les autres numéros correspondent à l'appel récursif de cette fonction.

Evaluation d'expressions booléennes

Nous définissons le type des expressions booléennes dont les atomes sont identifiés par des chaînes comme

type expr =
| Atom of string
| Not of expr
| And of expr * expr
| Or of expr * expr

et peut évaluer ces expressions en utilisant un oracle : string -> bool donnant les valeurs des atomes que nous trouvons comme suit:

let rec eval oracle = function
| Atom(name) -> oracle name
| Not(expr) -> not(eval oracle expr)
| And(expr1, expr2) -> (eval oracle expr1) && (eval oracle expr2)
| Or(expr1, expr2)  -> (eval oracle expr1) || (eval oracle expr2)

Voyez comment la fonction est claire et facile à lire. Grâce à l'utilisation correcte de la correspondance de modèle, un programmeur qui lit cette fonction a besoin de peu de temps pour s'assurer qu'il est correctement implémenté.

Forme normale de négation: correspondance de motif profonde

La correspondance de motif permet de déconstruire des valeurs complexes et n'est nullement limitée au niveau le plus «externe» de la représentation d'une valeur. Pour illustrer cela, nous implémentons la fonction transformant une expression booléenne en une expression booléenne où toutes les négations ne concernent que les atomes, la forme dite négative et un prédicat reconnaissant les expressions sous cette forme:

Nous définissons le type des expressions booléennes dont les atomes sont identifiés par des chaînes comme

type expr =
| Atom of string
| Not of expr
| And of expr * expr
| Or of expr * expr

Définissons d'abord un prédicat reconnaissant les expressions sous forme normale de négation :

let rec is_nnf = function
| (Atom(_) | Not(Atom(_))) -> true
| Not(_) -> false
| (And(expr1, expr2) | Or(expr1, expr2)) -> is_nnf expr1 && is_nnf expr2

Comme vous le voyez, il est possible de faire correspondre les modèles imbriqués comme Not(Atom(_)) . Maintenant, nous implémentons une fonction mappant une expression booléenne à une expression booléenne équivalente sous la forme normale de négation:

let rec nnf = function
| (Atom(_) | Not(Atom(_))) as expr -> expr
| Not(And(expr1, expr2)) -> Or(nnf(Not(expr1)),nnf(Not(expr2)))
| Not(Or(expr1, expr2)) -> And(nnf(Not(expr1)),nnf(Not(expr2)))
| And(expr1, expr2) -> And(nnf expr1, nnf expr2)
| Or(expr1, expr2) -> Or(nnf expr1, nnf expr2)
| Not(Not(expr)) -> nnf expr

Cette seconde fonction fait encore plus appel à des modèles imbriqués. Nous pouvons enfin tester notre code dans le toplevel sur la négation d'une implication:

# let impl a b =
Or(Not(a), b);;
  val impl : expr -> expr -> expr = <fun>
# let expr = Not(impl (Atom "A") (Atom "B"));;
val expr : expr = Not (Or (Not (Atom "A"), Atom "B"))
# nnf expr;;
- : expr = And (Atom "A", Not (Atom "B"))
# is_nnf (nnf expr);;
- : bool = true

Le système de type OCaml est capable de vérifier l'exhaustivité d'une correspondance de modèle. Par exemple, si nous omettons le cas Not(Or(expr1, expr2)) dans la fonction nnf , le compilateur émet un avertissement:

# let rec non_exhaustive_nnf = function
| (Atom(_) | Not(Atom(_))) as expr -> expr
| Not(And(expr1, expr2)) -> Or(nnf(Not(expr1)),nnf(Not(expr2)))
| And(expr1, expr2) -> And(nnf expr1, nnf expr2)
| Or(expr1, expr2) -> Or(nnf expr1, nnf expr2)
| Not(Not(expr)) -> nnf expr;;
          Characters 14-254:
  ..............function
  | (Atom(_) | Not(Atom(_))) as expr -> expr
  | Not(And(expr1, expr2)) -> Or(nnf(Not(expr1)),nnf(Not(expr2)))
  | And(expr1, expr2) -> And(nnf expr1, nnf expr2)
  | Or(expr1, expr2) -> Or(nnf expr1, nnf expr2)
  | Not(Not(expr)) -> nnf expr..
Warning 8: this pattern-matching is not exhaustive.
Here is an example of a case that is not matched:
Not (Or (_, _))
val non_exhaustive_nnf : expr -> expr = <fun>

(Cet avertissement peut être traité comme une erreur avec l'option -w @8 lors de l'appel du compilateur ou de l'interpréteur.)

Cette fonctionnalité offre un niveau de sécurité et d'exactitude accru dans les programmes acceptés par le compilateur. Il a cependant d'autres utilisations et peut par exemple être utilisé dans la programmation exploratoire. Il est très amusant d'écrire une conversion dans une forme normale, en commençant par les versions brutes de la fonction qui traitent les cas simples et en utilisant des exemples de cas non correspondants fournis par le compilateur pour affiner le traitement.

Champs d'enregistrement correspondants

La correspondance de motif peut être utilisée pour déconstruire des enregistrements. Nous illustrons ceci avec un type d'enregistrement représentant des emplacements dans un fichier texte, par exemple le code source d'un programme.

type location = {
  filename : string;
  line: int;
  column: int;
  offset: int;
}

Une valeur x de type location peut être déconstruite comme ceci:

let { filename; line; column; offset; } = x

Une syntaxe similaire peut être utilisée pour définir des fonctions, par exemple une fonction pour imprimer des emplacements:

let print_location { filename; line; column; offset; } =
  Printf.printf "%s: %d: %d" filename line column

Ou bien

let print_location = function { filename; line; column; offset; } ->
  Printf.printf "%s: %d: %d" filename line column

Les modèles correspondant à des enregistrements n'ont pas besoin de mentionner tous les champs d'un enregistrement. Étant donné que la fonction n'utilise pas le champ de offset , nous pouvons le laisser de côté:

let print_location { filename; line; column; } =
  Printf.printf "%s: %d: %d" filename line column

Lorsque l'enregistrement est défini dans un module, il suffit de qualifier le premier champ apparaissant dans le motif:

module Location =
struct
  type t = {
      filename : string;
      line: int;
      column: int;
      offset: int;
    }
end

let print_location { Location.filename; line; column; } =
  Printf.printf "%s: %d: %d" filename line column

Traitement de liste récursif avec correspondance de modèle

Nous démontrons ici comment traiter les listes de manière récursive en utilisant la syntaxe de correspondance de modèle d'OCaml.

let rec map f lst =
  match lst with
  | [] -> []
  | hd::tl -> (f hd)::(map f tl)

Dans ce cas, le motif [] correspond à la liste vide, alors que hd::tl correspond à toute liste comportant au moins un élément, et assignera le premier élément de la liste à hd et le reste de la liste (pourrait être vide) à tl .

Notez que hd::tl est un pattern très général et correspondra à toute liste non vide. Nous pouvons également écrire des modèles qui correspondent aux listes avec un nombre spécifique d'éléments:

(* Return the last element of a list. Fails if the list is empty. *)
let rec last lst =
  match lst with
  | [] -> failwith "Empty list"
  | [x] -> x (* Equivalent to x::[], [x] matches a list with only one element *)
  | hd::tl -> last tl

(* The second to last element of a list. *)
let rec second_to_last lst =
  match lst with
  | [] -> failwith "Empty list"
  | x::[] -> failwith "Singleton list"
  | fst::snd::[] -> snd
  | hd::tl -> second_to_last tl

De plus, OCaml prend en charge la correspondance de modèle sur les éléments des listes elles-mêmes. Nous pouvons être plus précis sur la structure des éléments dans une liste, et OCaml en déduira le type de fonction correct:

(* Assuming a list of tuples, return a list with first element of each tuple. *)
let rec first_elements lst =
  match lst with
  | [] -> []
  | (a, b)::tl -> a::(first_elements tl)
(* val first_elements : ('a * 'b) list -> 'a list = <fun> *)

En combinant ces modèles, nous pouvons traiter toute liste arbitrairement complexe.

Définition d'une fonction à l'aide de la correspondance de modèle

La function mot-clé peut être utilisée pour initier une correspondance de modèle sur le dernier argument d'une fonction. Par exemple, on peut écrire une fonction appelée sum , qui calcule la somme d'une liste d'entiers, de cette façon

let rec sum = function
  | [] -> 0
  | h::t -> h + sum t
;;

val sum : int list -> int = <fun>