집합

집합 (Sets)

Set은 Set.Make 펑터를 제공해요. 먼저 Set.Make에 모듈 하나를 넘겨줘야 해요. 그 모듈이 여러분의 집합의 요소 타입을 지정해요. 그 대가로, 그 요소들에 대한 집합 연산들을 가진 또 다른 모듈을 받게 돼요.

주의: 이 튜토리얼의 예시는 OCaml 5.1이 필요해요. 이전 버전의 OCaml을 쓰고 있다면, OCaml 5.1에서 새로 나온 to_list 대신 elements를 쓰거나, opam update를 실행한 뒤 opam upgrade ocaml로 OCaml을 업그레이드하면 돼요. 현재 버전은 ocaml --version으로 확인할 수 있어요.

문자열 집합을 다뤄야 한다면 Set.Make(String)을 호출해야 해요. 그러면 새 모듈이 반환돼요.

# module StringSet = Set.Make(String);;
module StringSet :
  sig
    type elt = string
    type t = Set.Make(String).t
    val empty : t
    val add : elt -> t -> t
    val singleton : elt -> t
    val remove : elt -> t -> t
    val union : t -> t -> t
    val inter : t -> t -> t
...
  end

새로 만든 모듈 이름을 StringSet으로 지으면 OCaml의 toplevel이 모듈의 시그니처를 보여줘요. 여기에는 매우 많은 함수가 들어 있으므로, 복사해 온 출력은 간결함을 위해 (...)로 줄였어요.

이 모듈은 타입도 두 개 정의해요.

  • 요소를 위한 type elt = string, 그리고
  • 집합을 위한 type t = Set.Make(String).t

출처: OCaml 공식 문서

본문

집합 만들기 (Creating a Set)

  1. StringSet.empty로 빈 집합을 만들 수 있어요.
# StringSet.empty ;;
- : StringSet.t = <abstr>

# StringSet.empty |> StringSet.to_list;;
- : string list = []

StringSet.empty의 경우에 OCaml toplevel이 실제 값 대신 자리 표시자 <abstr>을 보여주는 걸 확인할 수 있어요. 다만 StringSet.to_list로 문자열 집합을 리스트로 바꾸면 빈 리스트가 나와요.

(기억하세요. OCaml 5.1 이전 버전에서는 StringSet.empty |> StringSet.elements;;가 될 거예요.)

  1. 요소 하나를 가진 집합은 StringSet.singleton으로 만들어요.
# StringSet.singleton "hello";;
- : StringSet.t = <abstr>

# StringSet.(singleton "hello" |> to_list);;
- : string list = ["hello"]
  1. 리스트를 집합으로 바꾸려면 StringSet.of_list를 써요.
# StringSet.of_list ["hello"; "hi"];;
- : StringSet.t = <abstr>

# StringSet.(of_list ["hello"; "hi"] |> to_list);;
- : string list = ["hello"; "hi"]

관련된 또 다른 함수로 StringSet.of_seq: string Seq.t -> StringSet.t가 있어요. sequence에서 집합을 만들어 내요.

집합 다루기 (Working With Sets)

이 두 집합을 사용해서 집합을 다루는 함수 몇 개를 살펴볼게요.

# let first_set = ["hello"; "hi"] |> StringSet.of_list;;
- : val first_set : StringSet.t = <abstr>

# let second_set = ["good morning"; "hi"] |> StringSet.of_list;;
- : val second_set : StringSet.t = <abstr>

집합에 요소 추가하기 (Adding an Element to a Set)

# StringSet.(first_set |> add "good morning" |> to_list);;
- : string list = ["good morning"; "hello"; "hi"]

타입 string -> StringSet.t -> StringSet.t의 StringSet.add 함수는 문자열과 문자열 집합을 모두 받아요. 새 문자열 집합을 돌려줘요. OCaml에서 Set.Make 펑터로 만든 집합은 불변(immutable)이므로, 집합에 요소를 추가하거나 제거할 때마다 새 집합이 만들어져요. 옛 값은 그대로 변하지 않아요.

집합에서 요소 제거하기 (Removing an Element from a Set)

# StringSet.(first_set |> remove "hello" |> to_list);;
- : string list = ["hi"]

타입 string -> StringSet.t -> StringSet.t의 StringSet.remove 함수는 문자열과 문자열 집합을 모두 받아요. 주어진 문자열이 빠진 새 문자열 집합을 돌려줘요.

두 집합의 합집합 (Union of Two Sets)

# StringSet.(union first_set second_set |> to_list);;
- : string list = ["good morning"; "hello"; "hi"]

StringSet.union 함수로 두 집합의 합집합을 계산할 수 있어요.

두 집합의 교집합 (Intersection of Two Sets)

# StringSet.(inter first_set second_set |> to_list);;
- : string list = ["hi"]

StringSet.inter 함수로 두 집합의 교집합을 계산할 수 있어요.

한 집합에서 다른 집합 빼기 (Subtracting a Set from Another)

# StringSet.(diff first_set second_set |> to_list);;
- : string list = ["hello"]

StringSet.diff 함수로 첫 번째 집합에서 두 번째 집합의 요소를 제거할 수 있어요.

집합 필터링하기 (Filtering a Set)

# ["good morning"; "hello"; "hi"]
  |> StringSet.of_list
  |> StringSet.filter (fun str -> String.length str <= 5)
  |> StringSet.to_list;;
- : string list = ["hello"; "hi"]

타입 (string -> bool) -> StringSet.t -> StringSet.t의 StringSet.filter 함수는 기존 집합에서 조건자를 만족하는 요소들만 남겨 새 집합을 만들어요.

요소가 집합에 들어 있는지 확인하기 (Checking if an Element is Contained in a Set)

# ["good morning"; "hello"; "hi"]
  |> StringSet.of_list
  |> StringSet.mem "hello";;
- : bool = true

요소가 집합에 들어 있는지 확인하려면 StringSet.mem 함수를 써요.

커스텀 비교자를 가진 집합 (Sets With Custom Comparators)

Set.Make 펑터는 두 정의를 가진 모듈을 기대해요. 요소 타입을 나타내는 타입 t와, 시그니처가 t -> t -> int인 compare 함수요. String 모듈이 그 구조에 맞으므로, String을 Set.Make에 직접 인자로 넘길 수 있어요. 덧붙이자면, Int와 Float를 포함한 다른 많은 모듈도 그 구조를 가지므로, 그들 역시 Set.Make에 직접 넘겨 해당하는 집합 모듈을 만들 수 있어요.

우리가 만든 StringSet 모듈은 String 모듈이 제공하는 내장 compare 함수를 사용해요.

String.compare가 제공하는 대소문자 구분 비교 대신 대소문자를 구분하지 않는 비교를 수행하는 문자열 집합을 만든다고 해 볼게요.

Set.Make 함수에 임시(ad-hoc) 모듈을 넘기면 이걸 할 수 있어요.

# module CISS = Set.Make(struct
  type t = string
  let compare a b = compare (String.lowercase_ascii a) (String.lowercase_ascii b)
end);;
- : sig
    type elt = string
    type t
    val empty : t
    val is_empty : t -> bool
    val mem : elt -> t -> bool
    val add : elt -> t -> t
(...)

결과 모듈 이름을 CISS("Case Insensitive String Set"의 줄임말)라고 지었어요.

이 모듈이 의도한 동작을 하는 걸 확인할 수 있어요.

# CISS.singleton "hello" |> CISS.add "HELLO" |> CISS.to_list;;
- : string list = ["hello"]

"HELLO" 값은 이미 집합에 들어 있는 "hello"와 같다고 간주되므로 집합에 추가되지 않았어요.

의미 있는 compare 연산만 정의한다면 요소에 어떤 타입이든 쓸 수 있어요.

# type color = Red | Green | Blue;;
type color = Red | Green | Blue

# module SC = Set.Make(struct
  type t = color
  let compare a b =
    match a, b with
    | (Red, Red) -> 0
    | (Red, Green) -> 1
    | (Red, Blue) -> 1
    | (Green, Red) -> -1
    | (Green, Green) -> 0
    | (Green, Blue) -> 1
    | (Blue, Red) -> -1
    | (Blue, Green) -> -1
    | (Blue, Blue) -> 0
end);;
...

결론 (Conclusion)

Set.Make 펑터로 StringSet 모듈을 만들어 OCaml의 Set 모듈을 개괄적으로 살펴봤어요. 또 커스텀 비교 함수를 기반으로 집합을 만드는 방법도 알아봤어요. 더 자세한 내용은 표준 라이브러리 문서의 Set을 참고하세요.

더 알아보기