OCaml
La coincidencia de patrones

Función factorial utilizando el patrón de coincidencia

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

Esta función hace coincidir los valores 0 y 1 y los asigna al caso base de nuestra definición recursiva. Luego, todos los otros números se asignan a la llamada recursiva de esta función.

Evaluación de expresiones booleanas.

Definimos el tipo de expresiones booleanas cuyos átomos son identificados por cadenas como

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

y puede evaluar estas expresiones usando un oracle : string -> bool da los valores de los átomos que encontramos como sigue:

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)

Vea cómo la función es clara y fácil de leer. Gracias al uso correcto de la coincidencia de patrones, un programador que lea esta función necesita poco tiempo para asegurarse de que se implementa correctamente.

Negación de forma normal: emparejamiento profundo patrón

La coincidencia de patrones permite deconstruir valores complejos y de ninguna manera se limita al nivel "más externo" de la representación de un valor. Para ilustrar esto, implementamos la función que transforma una expresión booleana en una expresión booleana donde todas las negaciones son solo en los átomos, la llamada forma normal de negación y un predicado que reconoce las expresiones de esta forma:

Definimos el tipo de expresiones booleanas cuyos átomos son identificados por cadenas como

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

Primero definamos un predicado que reconozca expresiones en forma normal de negación :

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

Como ve, es posible hacer coincidencias con patrones anidados como Not(Atom(_)) . Ahora implementamos una función que asigna una expresión booleana a una expresión booleana equivalente en forma normal de negación:

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

Esta segunda función hace aún más usos de patrones anidados. Finalmente podemos probar nuestro código en el nivel superior en la negación de una implicación:

# 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

El sistema de tipo OCaml es capaz de verificar la exhaustividad de una coincidencia de patrones. Por ejemplo, si omitimos el caso Not(Or(expr1, expr2)) en la función nnf , el compilador emite una advertencia:

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

(Esta advertencia se puede tratar como un error con la opción -w @8 cuando se invoca al compilador o al intérprete).

Esta característica proporciona un mayor nivel de seguridad y corrección en los programas que son aceptados por el compilador. Sin embargo, tiene otros usos y puede, por ejemplo, usarse en programación exploratoria. Es muy divertido escribir una conversión a una forma normal, comenzando con versiones básicas de la función que manejan los casos fáciles y utilizando ejemplos de casos no coincidentes proporcionados por el compilador para refinar el tratamiento.

Campos de registro coincidentes

La coincidencia de patrones se puede utilizar para deconstruir registros. Ilustramos esto con un tipo de registro que representa ubicaciones en un archivo de texto, por ejemplo , el código fuente de un programa.

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

Un valor x de tipo de ubicación se puede deconstruir así:

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

Se puede utilizar una sintaxis similar para definir funciones, por ejemplo, una función para imprimir ubicaciones:

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

o alternativamente

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

Los patrones que coinciden con los registros no necesitan mencionar todos los campos de un registro. Como la función no utiliza el campo de offset , podemos omitirla:

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

Cuando el registro se define en un módulo, es suficiente para calificar el primer campo que se produce en el patrón:

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

Procesamiento de listas recursivas con coincidencia de patrones

Aquí mostramos cómo procesar listas recursivamente utilizando la sintaxis de coincidencia de patrones de OCaml.

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

En este caso, el patrón [] coincide con la lista vacía, mientras que hd::tl coincide con cualquier lista que tenga al menos un elemento, y asignará el primer elemento de la lista a hd y el resto de la lista (podría estar vacío) a tl .

Tenga en cuenta que hd::tl es un patrón muy general y coincidirá con cualquier lista que no esté vacía. También podemos escribir patrones que coincidan en listas con un número específico de elementos:

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

Además, OCaml admite la coincidencia de patrones en los elementos de las listas. Podemos ser más específicos sobre la estructura de los elementos dentro de una lista, y OCaml inferirá el tipo de función correcto:

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

Al combinar estos patrones juntos, podemos procesar cualquier lista arbitrariamente compleja.

Definiendo una función usando el patrón de coincidencia.

La function palabra clave se puede utilizar para iniciar la coincidencia de patrones en el último argumento de una función. Por ejemplo, podemos escribir una función llamada sum , que calcula la suma de una lista de enteros, de esta manera

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

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