OCaml
Dopasowywanie wzorów

Funkcja czynnikowa za pomocą dopasowania wzorca

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

Ta funkcja pasuje zarówno do wartości 0, jak i 1 i odwzorowuje je na podstawowy przypadek naszej definicji rekurencyjnej. Następnie wszystkie inne numery są odwzorowane na wywołanie rekurencyjne tej funkcji.

Ocena wyrażeń boolowskich

Definiujemy typ wyrażeń boolowskich, których atomy są identyfikowane przez łańcuchy jako

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

i może ocenić te wyrażenia za pomocą oracle : string -> bool podając wartości atomów, które znajdziemy w następujący sposób:

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)

Zobacz, jak funkcja jest przejrzysta i łatwa do odczytania. Dzięki prawidłowemu użyciu dopasowania wzorca programista czytający tę funkcję potrzebuje niewiele czasu, aby upewnić się, że jest poprawnie zaimplementowana.

Negacja normalna forma: dokładne dopasowanie wzoru

Dopasowanie wzorca pozwala na zdekonstruowanie złożonych wartości i nie jest w żaden sposób ograniczone do „najbardziej zewnętrznego” poziomu reprezentacji wartości. Aby to zilustrować, implementujemy funkcję przekształcającą wyrażenie boolowskie w wyrażenie boolowskie, w którym wszystkie negacje dotyczą tylko atomów, tak zwaną postać normalną negacji i predykat rozpoznający wyrażenia w tej formie:

Definiujemy typ wyrażeń boolowskich, których atomy są identyfikowane przez łańcuchy jako

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

Najpierw zdefiniujmy predykat rozpoznający wyrażenia w postaci normalnej negacji :

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

Jak widać, możliwe jest dopasowanie do zagnieżdżonych wzorów, takich jak Not(Atom(_)) . Teraz implementujemy funkcję mapującą wyrażenie boolowskie na równoważne wyrażenie boolowskie w postaci normalnej negacji:

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

Ta druga funkcja wykorzystuje jeszcze więcej zagnieżdżonych wzorów. W końcu możemy przetestować nasz kod na najwyższym poziomie na negacji implikacji:

# 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

System typu OCaml jest w stanie zweryfikować kompletność dopasowania wzorca. Na przykład, jeśli nnf przypadek Not(Or(expr1, expr2)) w funkcji nnf , kompilator wyświetli ostrzeżenie:

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

(To ostrzeżenie można traktować jako błąd z opcją -w @8 podczas wywoływania kompilatora lub interpretera).

Ta funkcja zapewnia wyższy poziom bezpieczeństwa i poprawności programów akceptowanych przez kompilator. Ma jednak inne zastosowania i może być na przykład wykorzystywany w programowaniu eksploracyjnym. Bardzo przyjemnie jest napisać konwersję do normalnej postaci, zaczynając od prymitywnych wersji funkcji, które obsługują łatwe przypadki i używając przykładów niedopasowanych przypadków dostarczonych przez kompilator w celu udoskonalenia leczenia.

Pasujące pola rekordów

Dopasowanie wzorca może być użyte do zdekonstruowania rekordów. Ilustrujemy to typem rekordu reprezentującym lokalizacje w pliku tekstowym, np . Kod źródłowy programu.

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

Wartość x lokalizacji typu można zdekonstruować w następujący sposób:

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

Podobną składnię można zastosować do zdefiniowania funkcji, na przykład funkcji do drukowania lokalizacji:

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

lub alternatywnie

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

Wzory pasujące do rekordów nie muszą wymieniać wszystkich pól rekordu. Ponieważ funkcja nie korzysta z pola offset , możemy go pominąć:

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

Gdy rekord jest zdefiniowany w module, wystarczy zakwalifikować pierwsze pole występujące we wzorcu:

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

Przetwarzanie listy rekurencyjnej z dopasowaniem wzorca

Tutaj pokazujemy, jak przetwarzać listy rekurencyjnie przy użyciu składni dopasowywania wzorców OCaml.

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

W takim przypadku wzorzec [] pasuje do pustej listy, podczas gdy hd::tl pasuje do dowolnej listy, która ma co najmniej jeden element, i przypisze pierwszy element listy do hd i reszty listy (może być pusta) do tl .

Zauważ, że hd::tl jest bardzo ogólnym wzorcem i pasuje do każdej listy, która nie jest pusta. Możemy również pisać wzorce pasujące do list z określoną liczbą elementów:

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

Dodatkowo OCaml obsługuje dopasowanie wzorca na samych elementach list. Możemy dokładniej określić strukturę elementów na liście, a OCaml wyliczy poprawny typ funkcji:

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

Łącząc te wzorce razem, możemy przetwarzać dowolnie złożoną listę.

Definiowanie funkcji za pomocą dopasowania wzorca

Słowo kluczowe function może być używana do zainicjowania dopasowywania wzoru na ostatni argument funkcji. Na przykład możemy napisać funkcję o nazwie sum , która w ten sposób oblicza sumę listy liczb całkowitych

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

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