OCaml
Patroon matching

Factorale functie met behulp van Pattern Matching

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

Deze functie komt overeen met zowel de waarden 0 als 1 en wijst ze toe aan het basisscenario van onze recursieve definitie. Vervolgens worden alle andere nummers toegewezen aan de recursieve aanroep van deze functie.

Evaluatie van booleaanse uitdrukkingen

We definiëren het type booleaanse uitdrukkingen waarvan de atomen worden geïdentificeerd door strings als

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

en kunnen deze uitdrukkingen evalueren met behulp van een oracle : string -> bool met de waarden van de atomen die we als volgt vinden:

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)

Zie hoe de functie duidelijk en gemakkelijk te lezen is. Dankzij het juiste gebruik van patroonovereenkomst heeft een programmeur die deze functie leest weinig tijd nodig om ervoor te zorgen dat deze correct wordt geïmplementeerd.

Ontkenning normale vorm: diepe patroonovereenkomst

Patroonafstemming maakt het mogelijk om complexe waarden te deconstrueren en het is geenszins beperkt tot het "buitenste" niveau van de weergave van een waarde. Om dit te illustreren, implementeren we de functie die een booleaanse uitdrukking omzet in een booleaanse uitdrukking waarbij alle ontkenningen alleen op atomen voorkomen, de zogenaamde negatie normale vorm en een predikaat dat uitdrukkingen in deze vorm herkent:

We definiëren het type booleaanse uitdrukkingen waarvan de atomen worden geïdentificeerd door strings als

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

Laten we eerst een predikaat definiëren dat uitdrukkingen herkent in de normale vorm van ontkenning :

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

Zoals u ziet, is het mogelijk om te vergelijken met geneste patronen zoals Not(Atom(_)) . Nu implementeren we een functie die een booleaanse uitdrukking toewijst aan een equivalente booleaanse uitdrukking in normale vorm van ontkenning:

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

Deze tweede functie maakt nog meer gebruik van geneste patronen. We kunnen eindelijk onze code op het hoogste niveau testen op de ontkenning van een implicatie:

# 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

Het OCaml-type systeem kan de volledigheid van een patroonovereenkomst verifiëren. Als we bijvoorbeeld het geval Not(Or(expr1, expr2)) weglaten in de functie nnf , geeft de compiler een waarschuwing:

# 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>

(Deze waarschuwing kan worden behandeld als een fout met de optie -w @8 wanneer de compiler of de interpreter wordt aangeroepen.)

Deze functie biedt een verhoogd niveau van veiligheid en correctheid in programma's die door de compiler worden geaccepteerd. Het heeft echter andere toepassingen en kan bijvoorbeeld worden gebruikt in exploratieve programmering. Het is erg leuk om een conversie naar een normale vorm te schrijven, beginnend met ruwe versies van de functie die de eenvoudige gevallen behandelen en voorbeelden van niet-overeenkomende gevallen van de compiler gebruiken om de behandeling te verfijnen.

Overeenkomende recordvelden

Patroonafstemming kan worden gebruikt om records te deconstrueren. We illustreren dit met een recordtype dat locaties in een tekstbestand voorstelt, bijvoorbeeld de broncode van een programma.

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

Een waarde x van het type locatie kan als volgt worden gedeconstrueerd:

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

Een vergelijkbare syntaxis kan worden gebruikt om functies te definiëren, bijvoorbeeld een functie om locaties af te drukken:

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

Of anders

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

Patronen die overeenkomen met records hoeven niet alle velden van een record te vermelden. Omdat de functie het offset veld niet gebruikt, kunnen we het weglaten:

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

Wanneer het record in een module is gedefinieerd, is het voldoende om het eerste veld in het patroon te kwalificeren:

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

Recursieve lijstverwerking met patroonovereenkomst

Hier laten we zien hoe lijsten recursief kunnen worden verwerkt met behulp van OCaml's patroonovereenkomstsyntaxis.

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

In dit geval komt het patroon [] overeen met de lege lijst, terwijl hd::tl overeenkomt met elke lijst die ten minste één element heeft, en zal het eerste element van de lijst aan hd en de rest van de lijst toewijzen (kan leeg zijn) naar tl .

Merk op dat hd::tl een zeer algemeen patroon is en overeenkomt met elke lijst die niet leeg is. We kunnen ook patronen schrijven die overeenkomen met lijsten met een specifiek aantal elementen:

(* 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

Bovendien ondersteunt OCaml het matchen van patronen op de elementen van lijsten zelf. We kunnen specifieker zijn over de structuur van elementen in een lijst en OCaml zal het juiste functietype afleiden:

(* 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> *)

Door deze patronen samen te combineren, kunnen we elke willekeurig complexe lijst verwerken.

Een functie definiëren met behulp van patroonovereenkomst

Het sleutelwoord function kan worden gebruikt voor het in patroon-matching beginnen over het laatste argument van een functie. We kunnen bijvoorbeeld een functie met de naam sum , die op deze manier de som van een lijst met gehele getallen berekent

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

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