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 타입 시스템은 패턴 매칭의 소모성을 검증 할 수 있습니다. 예를 들어, nnf 함수에서 Not(Or(expr1, expr2)) 대소 문자를 생략하면 컴파일러에서 경고를 표시합니다.

# 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 은 적어도 하나의 요소를 가진리스트와 일치하며,리스트의 첫 번째 요소를 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>