OCaml
Pattern Matching

Funzione fattoriale usando Pattern Matching

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

Questa funzione corrisponde a entrambi i valori 0 e 1 e li associa al caso base della nostra definizione ricorsiva. Quindi tutti gli altri numeri si associano alla chiamata ricorsiva di questa funzione.

Valutazione delle espressioni booleane

Definiamo il tipo di espressioni booleane i cui atomi sono identificati da stringhe come

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

e può valutare queste espressioni usando un oracle : string -> bool fornisce i valori degli atomi che troviamo come segue:

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)

Guarda come la funzione è chiara e facile da leggere. Grazie al corretto utilizzo della corrispondenza dei pattern, un programmatore che legge questa funzione ha bisogno di poco tempo per assicurarsi che sia correttamente implementato.

Forma normale di negazione: corrispondenza profonda del modello

La corrispondenza di modelli consente di decostruire valori complessi e non si limita in alcun modo al livello "più esterno" della rappresentazione di un valore. Per illustrare questo, implementiamo la funzione che trasforma un'espressione booleana in un'espressione booleana in cui tutte le negazioni sono solo sugli atomi, la cosiddetta forma normale di negazione e un predicato che riconosce le espressioni in questa forma:

Definiamo il tipo di espressioni booleane i cui atomi sono identificati da stringhe come

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

Per prima cosa definiamo un predicato che riconosca le espressioni in forma normale di negazione :

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

Come puoi vedere, è possibile confrontarsi con pattern nidificati come Not(Atom(_)) . Ora implementiamo una funzione che associa un'espressione booleana a un'espressione booleana equivalente nella forma normale di negazione:

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

Questa seconda funzione rende ancora più usi i pattern annidati. Finalmente possiamo testare il nostro codice nella parte superiore della negazione di un'implicazione:

# 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

Il sistema di tipo OCaml è in grado di verificare l'esaustività di un pattern matching. Ad esempio, se omettiamo il caso Not(Or(expr1, expr2)) nella funzione nnf , il compilatore emette un avviso:

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

(Questo avviso può essere considerato come un errore con l' -w @8 quando si richiama il compilatore o l'interprete.)

Questa funzione fornisce un maggiore livello di sicurezza e correttezza nei programmi accettati dal compilatore. Ha comunque altri usi e può ad esempio essere utilizzato nella programmazione esplorativa. È molto divertente scrivere una conversione in una forma normale, a partire da versioni approssimative della funzione che gestiscono i casi facili e utilizzando esempi di casi non corrispondenti forniti dal compilatore per perfezionare il trattamento.

Campi del record corrispondenti

La corrispondenza del modello può essere utilizzata per decostruire i record. Illustriamo questo con un tipo di record che rappresenta le posizioni in un file di testo, ad esempio il codice sorgente di un programma.

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

Un valore x di tipo posizione può essere decostruito in questo modo:

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

Una sintassi simile può essere utilizzata per definire le funzioni, ad esempio una funzione per stampare le posizioni:

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

o in alternativa

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

I modelli che corrispondono ai record non devono menzionare tutti i campi di un record. Poiché la funzione non utilizza il campo offset , possiamo lasciarla fuori:

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

Quando il record è definito in un modulo, è sufficiente qualificare il primo campo che si verifica nel modello:

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

Elaborazione lista ricorsiva con abbinamento di modelli

Qui dimostriamo come elaborare gli elenchi in maniera ricorsiva usando la sintassi di corrispondenza dei pattern di OCaml.

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

In questo caso, il modello [] corrisponde all'elenco vuoto, mentre hd::tl corrisponde a qualsiasi elenco che abbia almeno un elemento e assegnerà il primo elemento dell'elenco a hd e il resto dell'elenco (potrebbe essere vuoto) a tl .

Si noti che hd::tl è un modello molto generale e corrisponderà a qualsiasi elenco non vuoto. Possiamo anche scrivere pattern che corrispondono ad elenchi con un numero specifico di elementi:

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

Inoltre, OCaml supporta la corrispondenza del modello sugli elementi degli elenchi stessi. Possiamo essere più specifici sulla struttura degli elementi all'interno di una lista e OCaml dedurrà il tipo di funzione corretto:

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

Combinando insieme questi modelli, possiamo elaborare qualsiasi elenco arbitrariamente complesso.

Definire una funzione usando la corrispondenza del modello

La function parola chiave può essere utilizzata per avviare la corrispondenza del modello sull'ultimo argomento di una funzione. Ad esempio, possiamo scrivere una funzione chiamata sum , che calcola la somma di una lista di interi, in questo modo

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

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