패턴 매칭

3. 기본 패턴

패턴 매칭에서 가장 간단한 패턴은 명시적인 값 또는 변수이다. 예를 들어, 하스켈 구문으로 작성된 간단한 함수 정의를 살펴보자. (함수 매개변수는 괄호로 묶지 않고 공백으로 구분하며, `=`는 할당이 아니라 정의이다.)

```haskell

f 0 = 1

```

위 코드에서 `0`은 단일 값 패턴이다. `f`에 인수 `0`이 주어지면 패턴이 일치하고 함수는 `1`을 반환한다. 다른 인수가 있으면 일치하지 않으므로 함수가 실패한다. 구문은 함수 정의에서 대체 패턴을 지원하므로, 더 일반적인 인수를 사용하도록 정의를 확장할 수 있다.

```haskell

f n = n * f (n-1)

```

여기서 첫 번째 `n`은 단일 변수 패턴으로, 모든 인수와 일치하며 이름 `n`에 바인딩되어 정의의 나머지 부분에서 사용된다. 하스켈(최소한 Hope와는 달리)에서는 패턴이 순서대로 시도되므로 입력이 `0`인 경우 첫 번째 정의가 여전히 적용되지만, 다른 인수의 경우 함수는 인수인 `n`을 사용하여 `n * f (n-1)`을 반환한다.

와일드카드 패턴(종종 `_`로 작성)도 간단하다. 변수 이름과 마찬가지로 모든 값과 일치하지만 값을 어떤 이름에도 바인딩하지 않는다. 간단한 문자열 일치 상황에서 와일드카드 일치를 위한 알고리즘은 여러 재귀적 및 비재귀적 변형으로 개발되었다.^[10]

4. 트리 패턴

이전 절의 기본 패턴을 사용하여 더 복잡한 패턴을 구성할 수 있다. 이는 일반적으로 다른 값을 결합하여 값을 만드는 방식과 동일하다. 변수 및 와일드카드 부분을 사용하는 패턴은 단일 값으로 구성되지 않고, 구체적인 요소와 패턴 구조 내에서 변할 수 있는 요소의 조합인 값 그룹과 일치한다는 차이점이 있다.

트리 패턴은 노드에서 시작하여 일부 분기와 노드를 지정하고, 변수 또는 와일드카드 패턴을 사용하여 일부를 지정하지 않고 트리의 일부를 설명한다. 추상 구문 트리와 대수적 자료형을 생각하면 이해하기 쉽다.

Haskell에서 다음 줄은 정수와 문자열을 래핑하는 단일 데이터 생성자 `ColorConstructor`를 갖는 대수적 자료형 `Color`를 정의한다.

```haskell

data Color = ColorConstructor Integer String

```

생성자는 트리의 노드이며 정수와 문자열은 분기의 리프이다.

`Color`를 추상 자료형으로 만들기 위해 함수를 작성하려면, 자료형과 상호 작용하는 함수를 작성해야 한다. 따라서 자료형에서 일부 데이터(예: 문자열 부분 또는 정수 부분만)를 추출해야 한다.

`Color`형 변수를 전달하는 경우, 이 변수에서 데이터를 가져오기 위해 간단한 트리 패턴을 사용할 수 있다. 예를 들어, `Color`의 정수 부분을 가져오는 함수는 다음과 같이 작성할 수 있다.

```haskell

integerPart (ColorConstructor theInteger _) = theInteger

```

마찬가지로, 문자열 부분을 가져오는 함수는 다음과 같다.

```haskell

stringPart (ColorConstructor _ theString) = theString

```

Haskell의 데이터 레코드 구문을 사용하여 이러한 함수의 생성을 자동화할 수 있다.

OCaml 예제는 재귀적 자료형에 의해 생성된 더 복잡한 구조와 일치하는 방법을 보여준다. 이 예제는 요소 삽입 후 다시 균형을 맞추는 함수와 함께 적흑 트리를 정의한다. 컴파일러는 컴파일 시점에 케이스 목록이 완전하고 중복이 없음을 확인한다.

```ocaml

type color = Red | Black

type 'a tree = Empty | Tree of color * 'a tree * 'a * 'a tree

let rebalance t = match t with

| Tree (Black, Tree (Red, Tree (Red, a, x, b), y, c), z, d)

| Tree (Black, Tree (Red, a, x, Tree (Red, b, y, c)), z, d)

| Tree (Black, a, x, Tree (Red, Tree (Red, b, y, c), z, d))

| Tree (Black, a, x, Tree (Red, b, y, Tree (Red, c, z, d)))

• > Tree (Red, Tree (Black, a, x, b), y, Tree (Black, c, z, d))

5. 패턴을 이용한 데이터 필터링

패턴 매칭은 특정 구조의 데이터를 필터링하는 데 사용할 수 있다. 예를 들어, 하스켈에서는 리스트 내포를 이러한 종류의 필터링에 사용할 수 있다.

```haskell

[A x | A x <- [A 1, B 1, A 2, B 2]]

```

위 코드는 다음과 같이 평가된다.

```text

[A 1, A 2]

6. Mathematica에서의 패턴 매칭

Mathematica에서 패턴은 트리의 위치에 `_`를 넣는 것을 포함한다. 예를 들어, 패턴 `A[_]`는 `A[1]`, `A[2]`, 또는 더 일반적으로 `A[''x'']` (여기서 ''x''는 임의의 엔티티)와 같은 요소와 일치한다. 이 경우 `A`는 구체적인 요소이고, `_`는 변할 수 있는 트리의 부분을 나타낸다. `_` 앞에 붙는 심볼은 일치하는 내용을 해당 변수 이름에 바인딩하고, `_` 뒤에 붙는 심볼은 해당 심볼의 노드로 일치를 제한한다. 빈칸 자체도 내부적으로 `_`에 대해 `Blank[]`, `_x`에 대해 `Blank[x]`로 표현된다.<sup>[11]</sup>

Mathematica 함수 `Cases`는 첫 번째 인수의 요소 중 두 번째 인수의 패턴과 일치하는 요소를 필터링한다.<sup>[11]</sup> 예를 들어, `Cases[{a[1], b[1], a[2], b[2]}, a[_] ]`는 `{a[1], a[2]}`로 평가된다. 패턴 매칭은 표현식의 ''구조''에 적용된다. 다음 예에서 `Cases[ {a[b], a[b, c], a[b[c], d], a[b[c], d[e]], a[b[c], d, e]}, a[b[_], _] ]`는 `a[b[_],_]`과 일치하는 요소만 있기 때문에 `{a[b[c],d], a[b[c],d[e]]}`를 반환한다.

Mathematica에서는 계산 과정에서 생성되는 구조를 생성 방법이나 위치에 관계없이 추출할 수도 있다. `Trace` 함수를 사용하여 계산을 모니터링하고 패턴과 일치하는 요소를 반환할 수 있다. 예를 들어, 피보나치 수를 다음과 같이 정의할 수 있다.

```mathematica

fib[0|1]:=1

fib[n_]:= fib[n-1] + fib[n-2]

```

그런 다음 `fib[3]`이 주어졌을 때 재귀적 피보나치 호출의 순서를 `Trace[fib[3], fib[_]]`를 통해 확인할 수 있다. 이는 계산 구조에서 패턴 `fib[_]`의 발생을 나타내는 구조인 `{fib[3],{fib[2],{fib[1]},{fib[0]}},{fib[1]}}`를 반환한다.

기호 프로그래밍 언어에서는 패턴을 함수의 인수 또는 데이터 구조의 요소로 쉽게 사용할 수 있다. 이로 인해 패턴을 사용하여 데이터 조각에 대해 선언적으로 진술하고 함수가 작동하는 방식을 유연하게 지시할 수 있다.

예를 들어, Mathematica 함수인 `Compile`을 사용하면 코드의 효율성을 높일 수 있다. 부분식 ``은 `Compile`에게 컴파일 목적으로 `com[_]` 형식의 식을 정수로 간주할 수 있다는 것을 지시한다.

```mathematica

com[i_] := Binomial[2i, i]

Compile[{x, {i, _Integer}}, x^com[i], ]

7. 패턴 매칭과 문자열

패턴 매칭의 가장 일반적인 형태는 문자열을 이용하는 것이다. 많은 프로그래밍 언어에서 특정 문자열 구문을 사용하여 정규 표현식을 나타내는데, 이는 문자열 문자를 설명하는 패턴이다.<sup>[14]</sup>

패턴 매칭 구조를 갖춘 초기 프로그래밍 언어로는 COMIT(1957), SNOBOL(1962), Refal(1968), 트리 기반 패턴 매칭을 지원하는 Prolog(1972), SASL(1976), NPL(1977), KRC(1981) 등이 있다.

QED 편집기와 같은 많은 텍스트 편집기들이 다양한 종류의 패턴 매칭을 지원한다. QED 편집기는 정규 표현식 검색을 지원하며, 일부 버전의 TECO는 검색에서 OR 연산자를 지원한다.<sup>[14]</sup>

수식 처리 시스템은 일반적으로 대수식의 패턴 매칭을 지원한다.<sup>[14]</sup>

7. 1. 문자열을 위한 트리 패턴

7. 2. SNOBOL

참조

<sub>[1]</sub> 웹사이트 Pattern Matching - C# Guide https://docs.microso[...] 2024-03-13
<sub>[2]</sub> 웹사이트 Pattern Matching - F# Guide https://docs.microso[...] 2021-11-05
<sub>[3]</sub> 웹사이트 A Gentle Introduction to Haskell: Patterns http://www.haskell.o[...]
<sub>[4]</sub> 웹사이트 What's New In Python 3.10 — Python 3.10.0b3 documentation https://docs.python.[...] 2021-07-06
<sub>[5]</sub> 웹사이트 pattern_matching - Documentation for Ruby 3.0.0 https://docs.ruby-la[...] 2021-07-06
<sub>[6]</sub> 웹사이트 Pattern Syntax - The Rust Programming Language https://doc.rust-lan[...]
<sub>[7]</sub> 웹사이트 Pattern Matching https://docs.scala-l[...] 2021-01-17
<sub>[8]</sub> 웹사이트 Patterns — The Swift Programming Language (Swift 5.1) https://docs.swift.o[...]
<sub>[9]</sub> 논문 Symbolic Integration MIT Project MAC 1967-12
<sub>[10]</sub> 웹사이트 Wildcard matching algorithms http://xoomer.virgil[...] 2003
<sub>[11]</sub> 웹사이트 Cases—Wolfram Language Documentation https://reference.wo[...] 2020-11-17
<sub>[12]</sub> 간행물 A theory of discrete patterns and their implementation in SNOBOL4 Commun. ACM 1973-02
<sub>[13]</sub> 웹사이트 https://wiki.haskell[...]
<sub>[14]</sub> 논문 Symbolic Integration MIT Project MAC 1967-12