데이타 타입과 매칭

연결 리스트

펄(Perl)과 마찬가지로 Ocaml도 리스트를 언어 차원에서 지원한다. OCaml에서 리스트의 구성 요소는 모두 같은 타입이어야 한다. 리스트는 다음과 같이 쓴다.

[1; 2; 3]

(콤마가 아닌 세미콜론임을 명심하자.)

[] 는 빈 리스트를 의미한다.

 

리스트는 head (리스트의 첫 번째 원소)와 tail (리스트의 나머지 원소들)로 구성된다. 헤드는 원소이고, 테일은 다시 리스트가 된다. 위의 예제에서 헤드는 정수1 이고, 뒤에 테일은 리스트 [2; 3]이 된다.

리스트를 작성하기 위한 다른 방법은 head :: tail 형태로 cons 연산자를 이용하는 것이다. 아래는 같은 리스트를 작성하는 여러 방법이다.

[1; 2; 3]
1 :: [2; 3]
1 :: 2 :: [3]
1 :: 2 :: 3 :: []

필자가 왜 cons 연산자를 언급했을까? 이유는 다음에 언급할 패턴 매칭에서 리스트를 사용할 때 매우 유용하기 때문이다.

연결 리스트의 타입

정수형 연결 리스트의 타입은 int list이다. 일반적으로, foo의 연결 리스트의 타입은 foo list가 된다.

이는 연결 리스트의 모든 원소는 같은 타입을 가져야 함을 의미한다. 하지만 타입은 'a list 형태로 다형성을 가질 수 있다. 이는 "어떤 리스트"에 동작하는 일반적인 함수를 만들 때 무척 유용하다. (하지만 'a list가 각각의 원소가 다른 타입을 가질 수 있음을 의미하는 것은 아님을 유념하자. 여러분은 여전히 정수와 문자열이 섞여있는 리스트를 만들 수 없다. 원소의 타입은 무엇이든 될 수 있으나, 모두 같은 타입이어야 한다.)

OCaml List 모듈의 일부로 정의된 length가 좋은 예제이다. 리스트가 정수든, 문자열이든, 오브젝트든, 작은 털달린 동물이든 상관 없이 List.length 함수를 부를 수 있다. 따라서 List.length 함수의 타입은 다음과 같다.

List.length : 'a list -> int

구조체

C와 C++에는 구조체(structure)의 줄임말인 struct 개념이 있다. 자바는 훨씬 힘들긴 하지만 비슷한 효과를 낼 수 있는 클래스가 있다.

다음의 간단한 C 구조체를 생각해보자.

struct pair_of_ints {
  int a, b;
};

이와 동일한 OCaml의 가장 간단한 데이터 타입으로 int * int 타입을 가지는 (3, 4)와 같은 튜플(tuple)이 있다. 리스트와 달리 튜플은 서로 다른 타입의 원소를 가질 수 있다. 따라서 예를 들어 (3, "hello", 'x')int * string * char 타입을 가진다.

C struct를 작성하는 조금 더 복잡한 방법에는 레코드(record)가 있다. 레코드는 C 구조체와 마찬가지로 원소에 이름을 붙일 수 있다. 튜플은 원소에 이름을 붙일 수 없고 원소가 나타나는 순서를 기억해서 사용해야 한다. 다음은 위 C 구조체와 동일한 레코드이다.

type pair_of_ints = { a : int; b : int };;

이것은 타입을 정의하고, 다음은 실제로 이 타입의 객체를 생성하는 방법이다.

{ a=3; b=5 }

타입 정의에는 ":"를 사용하고, 이 타입의 객체를 만들 때는 "="를 사용했음에 유의하자.

다음은 이 타입을 탑 레벨에서 사용한 몇 가지 예제이다.

# type pair_of_ints = { a : int; b : int };;
type pair_of_ints = { a : int; b : int; }
# {a=3; b=5};;
- : pair_of_ints = {a = 3; b = 5}
# {a=3};;
Some record field labels are undefined: b

이처럼 OCaml은 일부 필드를 정의하지 않은 채 사용할 수 없다.

베리언트(Variants) (qualified unions and enums)

gcc 컴파일러 지원이 있긴 하지만, "qualified union"이 실제로 C에 존재하는 것은 아니다. 다음은 qualified union을 위해 C에서 흔히 쓰는 패턴이다.

struct foo {
  int type;
#define TYPE_INT 1
#define TYPE_PAIR_OF_INTS 2
#define TYPE_STRING 3
  union {
    int i;        // If type == TYPE_INT.
    int pair[2];  // If type == TYPE_PAIR_OF_INTS.
    char *str;    // If type == TYPE_STRING.
  } u;
};

이런 코드를 다들 한 번쯤 봤을텐데, 아름다운 코드는 아니다. 우선 이 패턴은 안전하지 않다. 프로그래머는 실수를 저지를 수 있고 실제로 문자열이 저장된 구조체에 실수로 u.i 필드를 사용할 수 있다. 또한 컴파일러는 switch 문에서 모든 타입이 다 검사되었는지 쉽게 확인할 수 없다. (특별히 이 문제만 풀기 위해서라면 enum 타입을 대신 사용할 수 있다.) 프로그래머는 type 필드를 설정하는 것을 잊어버릴 수도 있고, 이는 모든 종류의 이상한 버그의 원인이 된다. 또한, 이는 무척 귀찮은 일이다.

다음은 동일한 코드를 OCaml의 간결하고 우아한 코드로 나타낸 것이다.

type foo = Nothing | Int of int | Pair of int * int | String of string;;

이 부분은 타입 정의이다. 우선 |로 분리된 영역의 첫 번째 부분은 생성자(constructor)라 불린다. 이 부분은 대문자로 시작하는 한 어떤 이름을 써도 괜찮다. 만약 생성자가 값을 정의하는데 쓰였다면, of type가 뒤따라오며, 타입은 항상 소문자로 시작한다. 위 예에서 Nothing은 상수로 사용되었고, 다른 생성자는 값과 함께 사용된다.

실제로 이 타입의 값을 생성하기 위해서는 다음과 같이 쓴다.

Nothing
Int 3
Pair (4, 5)
String "hello"
     &c.

이 표현식들은 모두 foo 타입을 가진다.

of는 타입 정의를 쓸 때만 사용하고, 그 타입의 원소를 생성할 때는 사용하지 않음을 유의하자.

여기에 대한 확장으로, 다음과 같은 C의 간단한 enum

enum sign { positive, zero, negative };

OCaml로 다음과 같이 정의된다.

type sign = Positive | Zero | Negative;;

재귀 베리언트(recursive variants) (트리에 사용)

베리언트는 재귀적일 수 있으며, 이의 일반적인 용법은 트리 구조를 정의하는 것이다. 이 부분이 함수형 언어의 표현력이 두드러지는 곳이다.

type binary_tree = Leaf of int | Tree of binary_tree * binary_tree;;

다음은 바이너리 트리의 몇 가지 예제이다. 연습을 위해 종이에 그려보자.

Leaf 3
Tree (Leaf 3, Leaf 4)
Tree (Tree (Leaf 3, Leaf 4), Leaf 5)
Tree (Tree (Leaf 3, Leaf 4), Tree (Tree (Leaf 3, Leaf 4), Leaf 5))

파라미터화된 베리언트(parameterized variants)

이전 절의 바이너리 트리는 각 리프(leaf)에 정수를 가진다. 하지만 만약 바이너리 트리의 모양을 기술하되, 각 리프 노드의 무엇을 저장할지는 나중에 결정하고 싶다면 어떻게 해야할까? 우리는 이를 다음과 같은 파라미터화된(다형적인) 베리언트를 통해 할 수 있다.

type 'a binary_tree = Leaf of 'a | Tree of 'a binary_tree * 'a binary_tree;;

이는 일반적인 타입이다. 각 리프에 정수를 저장하는 특정 타입은 int binary_tree라 불린다. 유사하게 각 리프 노드에 문자열을 저장하는 특정 타입은 string binary_tree로 불린다. 다음 예제에서는 탑 레벨에 몇 가지 트리 인스턴스를 입력하고, 타입 추론 시스템이 타입을 찾아내도록 하였다.

# Leaf "hello";;
- : string binary_tree = Leaf "hello"
# Leaf 3.0;;
- : float binary_tree = Leaf 3.

타입 이름이 어떻게 거꾸로인지 확인하자. 이를 리스트의 타입 이름, 예를 들어 int list 등과 비교해보자.

사실 같은 방식으로 'a list도 타입 이름이 거꾸로 읽는 것이 우연이 아니다. 리스트는 단순히 다음과 같은 다소 이상한 정의를 가지는 파라미터화된 베리언트 타입이다.

 type 'a list = [] | :: of 'a * 'a list   (* 실제 OCaml 코드가 아님 *)

사실 위 정의는 컴파일되지 않는다. 다음은 거의 동일한 정의이다.

# type 'a list = Nil | :: of 'a * 'a list;;
type 'a list = Nil | :: of 'a * 'a list
# Nil;;
- : 'a list = Nil
# 1 :: Nil;;
- : int list = :: (1, Nil)
# 1 :: 2 :: Nil;;
- : int list = :: (1, :: (2, Nil))

앞서 리스트가 두 가지 방법으로 작성될 수 있다고 이야기한 부분이 떠올리자. [1; 2; 3] 형태로 간단한 문법적 도움(syntactic sugar)을 받거나, 좀 더 정형적으로는 1 :: 2 :: 3 :: []로 쓸 수 있다. 위의 'a list 정의를 보면, 정형적인 정의가 왜 그렇게 작성되었는지 이유를 알 수 있을 것이다.

리스트, 구조체, 베리언트 요약

OCaml name 타입 정의 예제 용법 예제

list            int list                               [1; 2; 3]
tuple           int * string                           (3, "hello")
record          type pair = { a : int; b : string }    { a = 3; b = "hello" }
variant         type foo = Int of int                  Int 3
                         | Pair of int * string                                                                      
variant         type sign = Positive | Zero            Positive
                          | Negative                   Zero
parameterized   type 'a my_list = Empty                Cons (1, Cons (2, Empty))
  variant                  | Cons of 'a * 'a my_list

(데이터 타입에 대한) 패턴 매칭

함수형 언어의 가장 멋진 기능 하나는 데이터 구조를 잘라내서 데이터에 대한 패턴 매칭을 할 수 있는 능력이다. 다시 한 번 강조하지만 이 기능은 "함수형" 기능이 아니다. 패턴 매칭을 허용하는 C의 변형 언어를 상상해 볼 수도 있는데, 어쨌든 매우 멋진 기능임에는 틀림 없다.

실제 프로그램 요구사항을 가지고 시작해보자. 우리는 간단한 수학적 식인 n * (x + y)를 나타내고 싶고, 분배 법칙을 적용해 n * x + n * y라는 결과를 얻고 싶다.

이 식에 대한 타입을 정의해보자.

type expr = Plus of expr * expr        (* means a + b *)
          | Minus of expr * expr       (* means a - b *)
          | Times of expr * expr       (* means a * b *)
          | Divide of expr * expr      (* means a / b *)
          | Value of string            (* "x", "y", "n", etc. *)
          ;;

n * (x + y) 식은 다음과 같이 나타낼 수 있다.

Times (Value "n", Plus (Value "x", Value "y"))

Times (Value "n", Plus (Value "x", Value "y"))n * (x + y)와 같이 출력해 주는 함수를 작성해보자. 실제로 우리는 두 개의 함수를 작성할 것이다. 하나는 식을 알아볼 수 있는 문자열로 변경하는 함수이고, 또 다른 하나는 문자열을 출력하는 함수이다. (이렇게 하는 이유는 같은 문자열을 파일에 출력하고 싶을 때, 이를 위해 같은 연산을 반복하는 것을 막기 위해서이다.)

let rec to_string e =
  match e with
    Plus (left, right)   -> "(" ^ (to_string left) ^ " + " ^ (to_string right) ^ ")"
  | Minus (left, right)  -> "(" ^ (to_string left) ^ " - " ^ (to_string right) ^ ")"
  | Times (left, right)  -> "(" ^ (to_string left) ^ " * " ^ (to_string right) ^ ")"
  | Divide (left, right) -> "(" ^ (to_string left) ^ " / " ^ (to_string right) ^ ")"
  | Value v -> v
  ;;
let print_expr e =
  print_endline (to_string e);;

(NB: ^ 연산자는 문자열을 병합한다.)

다음은 출력 함수를 실행한 것이다.

# print_expr (Times (Value "n", Plus (Value "x", Value "y")));;
(n * (x + y))

패턴 매칭의 일반적인 형태는 다음과 같다.

match object with
  pattern    ->  result
| pattern    ->  result
    ...

왼쪽 편의 패턴은 to_string 함수에서처럼 간단할 수도 있고, 복잡하고 중첩되어 있을 수도 있다. 다음 예제는 n * (x + y)(x + y) * n 같은 식의 곱셈을 분배해주는 함수인데, 이를 위해서 중첩 패턴을 사용한다.

let rec multiply_out e =
  match e with
    Times (e1, Plus (e2, e3)) ->
      Plus (Times (multiply_out e1, multiply_out e2),
            Times (multiply_out e1, multiply_out e3))
  | Times (Plus (e1, e2), e3) ->
      Plus (Times (multiply_out e1, multiply_out e3),
            Times (multiply_out e2, multiply_out e3))
  | Plus (left, right) -> Plus (multiply_out left, multiply_out right)
  | Minus (left, right) -> Minus (multiply_out left, multiply_out right)
  | Times (left, right) -> Times (multiply_out left, multiply_out right)
  | Divide (left, right) -> Divide (multiply_out left, multiply_out right)
  | Value v -> Value v
  ;;

다음은 실행 예이다.

# print_expr (multiply_out (Times (Value "n", Plus (Value "x", Value "y"))));;
((n * x) + (n * y))

multiply_out 함수가 어떻게 동작하는 것일까? 핵심은 첫 두 패턴에 있다. 첫 번째 패턴 Times (e1, Plus (e2, e3))e1 * (e2 + e3) 형태의 식을 매치한다. 이제 이 패턴의 오른쪽 편을 보면, (e1 * e2) + (e1 * e3)임을 알게 될 것이다.

두 번째 패턴도 같은 일을 하는데, 매치되는 식이 (e1 + e2) * e3라는 차이만 있다.

나머지 패턴은 식의 모양을 바꾸지 않지만, multiply_out 함수를 재귀적으로 호출해준다. 이는 식 내의 모든 보조식에서 분배법칙이 적용됨을 의미한다. (만약 최상위 수준의 식만 분배법칙을 적용하려 했다면, 나머지 패턴을 간단히 e -> e로 바꿔주면 된다.)

반대의 일(인수분해)도 할 수 있을까? 물론 할 수 있다. (하지만 약간 더 복잡하다.) 다음 버전은 최상위 수준에서만 동작한다. 물론 여러분은 모든 수준, 더 복잡한 상황에서 동작하도록 코드를 확장할 수 있다.

let factorize e =
  match e with
    Plus (Times (e1, e2), Times (e3, e4)) when e1 = e3 -> Times (e1, Plus (e2, e4))
  | Plus (Times (e1, e2), Times (e3, e4)) when e2 = e4 -> Times (Plus (e1, e3), e4)
  | e -> e
  ;;
# factorize (Plus (Times (Value "n", Value "x"), Times (Value "n", Value "y")));;
- : expr = Times (Value "n", Plus (Value "x", Value "y"))

위의 인수분해 함수는 또 다른 몇 개의 기능을 소개한다. 여러분은 가드(guard)로 알려진 기능을 패턴 매치에 추가할 수 있다. 가드는 when에 뒤따라오는 조건문으로, 패턴이 매치되고 when 구문의 조건이 만족되었을 때만 패턴 매치가 일어난다.

match object with
  pattern    [ when condition ]   ->  result
  pattern    [ when condition ]   ->  result
    ...

두 번째 기능은 두 표현식 사이의 "구조적 동일성(structural equality)"을 비교하는 = 연산자이다. 이는 실제로 재귀적으로 따라가서 각 표현식이 모든 수준에서 동일한 값을 갖는지 보는 것이다.

OCaml은 컴파일 타임에 패턴에서 모든 가능성을 확인했는지 검사해준다. 필자는 위 type expr에서 Product 베리언트를 추가해 타입 정의를 변경하였다.

type expr = Plus of expr * expr        (* means a + b *)
          | Minus of expr * expr       (* means a - b *)
          | Times of expr * expr       (* means a * b *)
          | Divide of expr * expr      (* means a / b *)
          | Product of expr list       (* means a * b * c * ... *)
          | Value of string            (* "x", "y", "n", etc. *)
          ;;

그리고 to_string 함수를 수정 없이 재컴파일하였다. OCaml은 다음과 같은 경고 메시지를 보여준다.

Warning: this pattern-matching is not exhaustive.
Here is an example of a value that is not matched:
Product _