OCaml
Musterabgleich

Fakultät mit Pattern Matching

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

Diese Funktion stimmt mit den Werten 0 und 1 überein und ordnet sie dem Basisfall unserer rekursiven Definition zu. Alle anderen Nummern entsprechen dann dem rekursiven Aufruf dieser Funktion.

Auswertung boolescher Ausdrücke

Wir definieren den Typ boolescher Ausdrücke, deren Atome durch Strings als gekennzeichnet sind

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

und kann diese Ausdrücke mit einem oracle : string -> bool auswerten oracle : string -> bool wobei die Werte der Atome wie folgt angegeben werden:

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)

Sehen Sie, wie die Funktion klar und gut lesbar ist. Dank der korrekten Verwendung von Pattern-Matching benötigt ein Programmierer, der diese Funktion liest, wenig Zeit, um sicherzustellen, dass er korrekt implementiert wird.

Negation Normalform: Deep Pattern Matching

Pattern Matching erlaubt die Dekonstruktion komplexer Werte und ist keinesfalls auf die äußerste Ebene der Darstellung eines Wertes beschränkt. Um dies zu veranschaulichen, implementieren wir die Funktion, die einen booleschen Ausdruck in einen booleschen Ausdruck umwandelt, bei dem sich alle Negationen nur auf Atome beziehen, die sogenannte Negationsnormalform und ein Prädikat, das Ausdrücke in dieser Form erkennt:

Wir definieren den Typ boolescher Ausdrücke, deren Atome durch Strings als gekennzeichnet sind

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

Definieren wir zunächst ein Prädikat, das Ausdrücke in Negationsnormalform erkennt:

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

Wie Sie sehen, ist es möglich, mit verschachtelten Mustern wie Not(Atom(_)) . Jetzt implementieren wir eine Funktion, die einen booleschen Ausdruck in einem äquivalenten booleschen Ausdruck in negativer Normalform darstellt:

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

Diese zweite Funktion nutzt verschachtelte Muster noch mehr. Endlich können wir unseren Code in der obersten Ebene auf die Negation einer Implikation testen:

# 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

Das OCaml-Typsystem kann die Vollständigkeit einer Musterübereinstimmung überprüfen. Wenn wir beispielsweise den Fall Not(Or(expr1, expr2)) in der Funktion nnf , gibt der Compiler eine Warnung aus:

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

(Diese Warnung kann beim Aufrufen des Compilers oder des Interpreters mit der Option -w @8 als Fehler behandelt werden.)

Diese Funktion bietet eine erhöhte Sicherheit und Korrektheit in Programmen, die vom Compiler akzeptiert werden. Es hat jedoch andere Verwendungszwecke und kann beispielsweise bei der explorativen Programmierung verwendet werden. Es ist sehr lustig, eine Konvertierung in eine normale Form zu schreiben, angefangen mit einfachen Versionen der Funktion, die die einfachen Fälle behandelt, und anhand von Beispielen nicht übereinstimmender Fälle, die vom Compiler bereitgestellt werden, um die Behandlung zu verfeinern.

Passende Datensatzfelder

Mit Pattern Matching können Sie Datensätze dekonstruieren. Wir veranschaulichen dies mit einem Datensatztyp, der Positionen in einer Textdatei darstellt, z. B. den Quellcode eines Programms.

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

Ein Wert x des Typs location kann folgendermaßen dekonstruiert werden:

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

Eine ähnliche Syntax kann zum Definieren von Funktionen verwendet werden, z. B. eine Funktion zum Drucken von Positionen:

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

oder alternativ

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

Muster, die mit Datensätzen übereinstimmen, müssen nicht alle Felder eines Datensatzes erwähnen. Da die Funktion das offset Feld nicht verwendet, können wir es weglassen:

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

Wenn der Datensatz in einem Modul definiert ist, reicht es aus, das erste im Muster vorkommende Feld zu qualifizieren:

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

Rekursive Listenverarbeitung mit Mustervergleich

Hier zeigen wir Ihnen, wie Sie Listen rekursiv mit der Pattern-Matching-Syntax von OCaml verarbeiten.

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

In diesem Fall stimmt das Muster [] mit der leeren Liste überein, während hd::tl mit einer Liste mit mindestens einem Element übereinstimmt und das erste Element der Liste hd und dem Rest der Liste hd (kann leer sein). zu tl .

Beachten Sie, dass hd::tl ein sehr allgemeines Muster ist und mit jeder Liste übereinstimmt, die nicht leer ist. Wir können auch Muster schreiben, die auf Listen mit einer bestimmten Anzahl von Elementen passen:

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

Darüber hinaus unterstützt OCaml die Mustererkennung für die Elemente der Listen selbst. Wir können uns genauer auf die Struktur von Elementen innerhalb einer Liste beziehen, und OCaml wird auf den korrekten Funktionstyp schließen:

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

Durch die Kombination dieser Muster können wir eine beliebig komplexe Liste verarbeiten.

Definieren einer Funktion mithilfe des Mustervergleichs

Das Schlüsselwort - function kann verwendet werden , Pattern-Matching auf dem letzten Argument einer Funktion zu initiieren. Zum Beispiel können wir eine Funktion namens sum schreiben, die auf diese Weise die Summe einer Liste von ganzen Zahlen berechnet

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

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