OCaml
Mönstermatchning

Faktorisk funktion med hjälp av Mönstermatchning

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

Denna funktion matchar både värdena 0 och 1 och kartlägger dem till grundfallet för vår rekursiva definition. Därefter kartlägger alla andra nummer till det rekursiva samtalet för denna funktion.

Utvärdering av booleska uttryck

Vi definierar typen av booleska uttryck vars atomer identifieras av strängar som

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

och kan utvärdera dessa uttryck med hjälp av ett oracle : string -> bool ger värdena på atomerna som vi hittar enligt följande:

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)

Se hur funktionen är tydlig och lättläst. Tack vare korrekt användning av mönstermatchning behöver en programmerare som läser denna funktion lite tid för att säkerställa att den implementeras korrekt.

Negation normalform: djupmatchning

Mönstermatchning gör det möjligt att dekonstruera komplexa värden och det är inte alls begränsat till den "yttre mest" nivån för representationen av ett värde. För att illustrera detta implementerar vi funktionen som omvandlar ett booleskt uttryck till ett booleskt uttryck där alla negationer endast är på atomer, den så kallade negativa normala formen och ett predikat som känner igen uttryck i denna form:

Vi definierar typen av booleska uttryck vars atomer identifieras av strängar som

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

Låt oss först definiera ett predikat som känner igen uttryck i normal negation :

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

Som ni ser är det möjligt att matcha mot kapslade mönster som Not(Atom(_)) . Nu implementerar vi en funktion som kartlägger ett booleskt uttryck till ett ekvivalentt booleskt uttryck i normal negativ form:

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

Den andra funktionen gör ännu mer användning av kapslade mönster. Vi kan äntligen testa vår kod i toppnivån när det gäller att förneka en implikation:

# 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

OCaml-typsystemet kan verifiera utmattningen av ett mönstermatchning. Om vi till exempel utelämnar fallet Not(Or(expr1, expr2)) i nnf funktionen ger kompilatorn en varning:

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

(Denna varning kan behandlas som ett fel med alternativet -w @8 när man påkallar kompilatorn eller tolkaren.)

Denna funktion ger en ökad nivå av säkerhet och korrekthet i program som accepteras av kompilatorn. Den har emellertid andra användningsområden och kan till exempel användas i utforskande programmering. Det är väldigt roligt att skriva en konvertering till en normal form, börja med rå versioner av funktionen som hanterar enkla fall och använda exempel på icke matchade fall från kompilatorn för att förfina behandlingen.

Matchande fält

Mönstermatchning kan användas för att dekonstruera poster. Vi illustrerar detta med en posttyp som representerar platser i en textfil, t.ex. programmets källkod.

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

Ett värde x typ av plats kan dekonstrueras på följande sätt:

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

En liknande syntax kan användas för att definiera funktioner, till exempel en funktion för att skriva ut platser:

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

eller alternativt

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

Mönster som matchar poster behöver inte nämna alla fält i en post. Eftersom funktionen inte använder offset kan vi lämna den ut:

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

När posten definieras i en modul räcker det för att kvalificera det första fältet som förekommer i mönstret:

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

Rekursiv lista bearbetning med mönster matchning

Här demonstrerar vi hur man bearbetar listor rekursivt med hjälp av OCamls mönster-matchande syntax.

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

I detta fall matchar mönstret [] den tomma listan, medan hd::tl matchar alla listor som har minst ett element, och kommer att tilldela det första elementet i listan till hd och resten av listan (kan vara tom) till tl .

Observera att hd::tl är ett mycket allmänt mönster och kommer att matcha alla listor som inte är tomma. Vi kan också skriva mönster som matchar på listor med ett visst antal element:

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

Dessutom stöder OCaml mönstermatchning på själva listorna. Vi kan vara mer specifika om strukturen för element i en lista, och OCaml kommer att sluta sig till rätt funktionstyp:

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

Genom att kombinera dessa mönster kan vi behandla valfri godtycklig komplex lista.

Definiera en funktion med hjälp av mönstermatchning

Nyckelordet function kan användas för att initiera mönstermatchning på det sista argumentet för en funktion. Vi kan till exempel skriva en funktion som heter sum , som beräknar summan av en lista med heltal på detta sätt

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

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