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

この2番目の関数は、ネストされたパターンをさらに使用します。私たちは最終的に、暗黙の否定についてトップレベルでコードをテストすることができます：

# 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型システムは、パターンマッチングの排除性を検証することができます。たとえば、 nnf関数で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;
}

タイプlocationの値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 は少なくとも1つの要素を持つリストと一致し、リストの最初の要素を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を使用して、関数の最後の引数に対してパターンマッチングを開始functionことができます。例えば、 sumという関数を書くことができます。この関数は、整数のリストの合計を計算します。

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

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