OCaml
Соответствие шаблону

Факториальная функция с использованием сопоставления с образцом

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

Эта функция соответствует значениям 0 и 1 и сопоставляет их с базовым случаем нашего рекурсивного определения. Тогда все остальные числа соответствуют рекурсивному вызову этой функции.

Оценка булевых выражений

Мы определяем тип булевых выражений, атомы которых идентифицируются строками как

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

и может оценивать эти выражения с помощью oracle : string -> bool дающего значения атомов, которые мы находим следующим образом:

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)

Посмотрите, как функция понятна и легко читается. Благодаря правильному использованию сопоставления шаблонов программисту, читающему эту функцию, требуется мало времени для обеспечения правильной реализации.

Отрицательная нормальная форма: глубокое сопоставление

Согласование шаблонов позволяет деконструировать комплексные значения и никоим образом не ограничивается «внешним большинством» уровня представления значения. Чтобы проиллюстрировать это, мы реализуем функцию, преобразующую булево выражение в логическое выражение, где все отрицания относятся только к атомам, так называемая нормальная форма отрицания и выражения, распознающие предикат в этой форме:

Мы определяем тип булевых выражений, атомы которых идентифицируются строками как

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

Сначала определим предикат, распознающий выражения в нормальной форме отрицания :

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

Как видите, можно сопоставлять вложенные шаблоны, такие как Not(Atom(_)) . Теперь мы реализуем функцию, сопоставляющую булево выражение с эквивалентным булевым выражением в нормальной форме отрицания:

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

Эта вторая функция еще больше использует вложенные шаблоны. Наконец, мы можем проверить наш код в верхнем слое на отрицание импликации:

# 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 может проверить полноту соответствия шаблонов. Например, если мы опускаем случай Not(Or(expr1, expr2)) в функции nnf , компилятор выдает предупреждение:

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

(Это предупреждение можно рассматривать как ошибку с параметром -w @8 при вызове компилятора или интерпретатора.)

Эта функция обеспечивает повышенный уровень безопасности и правильности в программах, которые принимаются компилятором. Тем не менее, он имеет другие применения и может, например, использоваться в исследовательском программировании. Очень интересно написать преобразование в обычную форму, начиная с сырых версий функции, которые обрабатывают простые случаи, и используя примеры несогласованных случаев, предоставленных компилятором для уточнения обработки.

Соответствие полей записей

Согласование шаблонов может использоваться для деконструирования записей. Мы иллюстрируем это типом записи, представляющим местоположения в текстовом файле, например, исходный код программы.

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

Значение x местоположения типа может быть деконструировано следующим образом:

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

Аналогичный синтаксис может использоваться для определения функций, например, для функции печати:

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

или альтернативно

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

В записях совпадений шаблонов нет необходимости упоминать все поля записи. Поскольку функция не использует поле offset , мы можем оставить ее:

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

Когда запись определена в модуле, достаточно определить первое поле, имеющее место в шаблоне:

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

Обработка рекурсивного списка с использованием соответствия шаблону

Здесь мы демонстрируем, как обрабатывать списки рекурсивно, используя синтаксис соответствия шаблону OCaml.

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

В этом случае шаблон [] соответствует пустым спискам, а hd::tl соответствует любому списку, который имеет хотя бы один элемент, и назначит первый элемент списка hd и остальную часть списка (может быть пустым) к tl .

Обратите внимание, что hd::tl является очень общим шаблоном и будет соответствовать любому списку, который не является пустым. Мы также можем писать шаблоны, которые соответствуют спискам с определенным количеством элементов:

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

Кроме того, OCaml поддерживает сопоставление образцов по элементам самих списков. Мы можем быть более конкретными в отношении структуры элементов внутри списка, а OCaml выведет правильный тип функции:

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

Объединив эти шаблоны вместе, мы можем обработать любой произвольно сложный список.

Определение функции с использованием соответствия шаблону

Ключевое слово function может быть использована для инициирования шаблонов соответствия на последний аргумент функции. Например, мы можем написать функцию sum , которая вычисляет сумму списка целых чисел, таким образом

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

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