맵

맵 (Maps)

가장 일반적인 의미에서, Map 모듈은 여러분의 타입을 위한 불변(immutable) 키-값 연관 배열을 만들게 해 줘요. 더 구체적으로 말하면 OCaml의 Map 모듈은 빠른 조회(O(Log n))를 지원하기 위해 이진 탐색 트리(binary search tree) 알고리즘으로 구현돼요.

참고: 이 튜토리얼에서 말하는 Map이라는 개념은 키-값 쌍의 집합을 저장하는 자료구조를 가리켜요. 사전(dictionary)이나 연관 테이블(association table)이라고 부르기도 해요. 이는 이전 수업에서 살펴본 List.map, Array.map, Option.map 같은 "맵"과는 다른 개념이에요. 그것들은 데이터를 연산하는 함수이지 데이터 자체가 아니니까요.

Map을 쓰려면 먼저 Map.Make 펑터(functor)를 이용해 우리만의 커스텀 맵 모듈을 만들어야 해요. 펑터에 대한 자세한 내용은 Functors를 참고하세요. 이 펑터는 맵에서 쓰일 키의 타입과 그 키들을 비교하는 함수를 정의하는 모듈 파라미터를 가져요.

OCaml 표준 라이브러리에서 연관 테이블의 다른 구현을 보려면 Hash Tables 튜토리얼을 참고하세요.

# module StringMap = Map.Make(String);;

module StringMap :
  sig
    type key = string
    type 'a t = 'a Map.Make(String).t
    val empty : 'a t
    val add : key -> 'a -> 'a t -> 'a t
    val add_to_list : key -> 'a -> 'a list t -> 'a list t
    val update : key -> ('a option -> 'a option) -> 'a t -> 'a t
    val singleton : key -> 'a -> 'a t
    val remove : key -> 'a t -> 'a t
    (* ... *)
  end

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

StringMap 모듈을 만들 때 Map.Make 펑터에 String 모듈을 넘겨 맵 키의 타입을 정의했어요. 이는 StringMap의 시그니처(type key = string)에서 확인할 수 있어요. 다만 값의 타입은 아직 정의하지 않았어요. 값의 타입은 첫 번째 맵을 만들 때 정해질 거예요.

출처: OCaml 공식 문서

본문

맵 만들기 (Creating a Map)

StringMap 모듈은 타입에 타입 파라미터 'a가 있는 empty 값을 가져요. 즉 empty : 'a t이죠.

이 말은 empty로 값이 어떤 타입이든 새 빈 맵을 만들 수 있다는 뜻이에요.

값의 타입은 두 가지 방식으로 지정할 수 있어요.

  • 주석(annotation)을 붙여 새 맵을 만들 때
  • 맵에 요소를 추가할 때

예시 1: 주석으로 지정하기

# let int_map : int StringMap.t = StringMap.empty;;
val int_map : int StringMap.t = <abstr>

예시 2: 요소를 추가해서 지정하기

# let int_map = StringMap.(empty |> add "one" 1);;
val int_map : int StringMap.t = <abstr>

맵 다루기 (Working With Maps)

이 튜토리얼의 나머지 부분에서는 다음 맵을 사용할게요.

# let lucky_numbers = StringMap.of_seq @@ List.to_seq [
    ("leostera", 2112);
    ("charstring88", 88);
    ("divagnz", 13);
  ];;
val lucky_numbers : int StringMap.t = <abstr>

맵에서 항목 찾기 (Finding Entries in a Map)

맵에서 항목을 찾으려면 find_opt나 find 함수를 써요.

# StringMap.find_opt "leostera" lucky_numbers;;
- : int option = Some 2112

# StringMap.find "leostera" lucky_numbers;;
- : int = 2112

검색한 키가 맵에 있을 때:

  • find_opt는 연관된 값을 옵션에 감싸 돌려줘요
  • find는 연관된 값을 돌려줘요

검색한 키가 맵에 없을 때:

  • find_opt는 None을 돌려줘요
  • find는 Not_found 예외를 던져요

조건자(predicate) 함수를 쓰고 싶다면 find_first_opt와 find_last_opt도 쓸 수 있어요.

# let first_under_10_chars : (string * int) option =
  StringMap.find_first_opt
    (fun key -> String.length key < 10)
    lucky_numbers;;
val first_under_10_chars : (string * int) option = Some ("divagnz", 13)

find_first와 find_last 함수도 비슷하게 동작하지만, 옵션을 돌려주는 대신 예외를 던져요.

find_first_opt와 find_last_opt는 값만이 아니라 키-값 쌍을 돌려준다는 점을 주의하세요.

맵에 항목 추가하기 (Adding Entries to a Map)

맵에 항목을 추가하려면 add 함수를 쓰는데, 키, 값, 그리고 그 항목이 추가될 맵을 받아요. 그 키-값 쌍이 추가된 새 맵을 돌려줘요.

# let more_lucky_numbers = lucky_numbers |> StringMap.add "paguzar" 108;;
val more_lucky_numbers : int StringMap.t = <abstr>

# StringMap.find_opt "paguzar" lucky_numbers;;
- : int option = None

# StringMap.find_opt "paguzar" more_lucky_numbers;;
- : int option = Some 108

전달한 키에 이미 값이 연관되어 있으면, 전달한 값이 기존 값을 대체해요.

초기 맵 lucky_numbers는 그대로 유지된다는 점을 주의하세요.

맵에서 항목 제거하기 (Removing Entries From a Map)

맵에서 항목을 제거하려면 remove 함수를 쓰는데, 키와 맵을 받아요. 그 키의 항목이 제거된 새 맵을 돌려줘요.

# let fewer_lucky_numbers = lucky_numbers |> StringMap.remove "divagnz";;
val fewer_lucky_numbers : int StringMap.t = <abstr>

# StringMap.find_opt "divagnz" lucky_numbers;;
- : int option = Some 13

# StringMap.find_opt "divagnz" fewer_lucky_numbers;;
- : int option = None

맵에 없는 키를 제거해도 아무 효과가 없어요.

초기 맵 lucky_numbers는 그대로 유지된다는 점을 주의하세요.

키와 연관된 값 바꾸기 (Changing the Value Associated With a Key)

키와 연관된 값을 바꾸려면 update 함수를 써요. 키, 맵, 그리고 업데이트 함수를 받아요. 그 키와 연관된 값이 새 값으로 대체된 새 맵을 돌려줘요.

# let updated_lucky_numbers =
    lucky_numbers
    |> StringMap.update "charstring88" (Option.map (fun _ -> 99));;
val updated_lucky_numbers : int StringMap.t = <abstr>

# StringMap.find_opt "charstring88" lucky_numbers;;
- : int option = Some 88

# StringMap.find_opt "charstring88" updated_lucky_numbers;;
- : int option = Some 99

다른 업데이트 함수들로 직접 실험해 보세요. 여러 동작이 가능해요.

키가 맵에 들어 있는지 확인하기 (Checking if a Key is Contained in a Map)

키가 맵의 멤버인지 확인하려면 mem 함수를 써요.

# StringMap.mem "paguzar" less_lucky_numbers;;
- : bool = false

맵 병합하기 (Merging Maps)

두 맵을 병합하려면 union 함수를 써요. 이 함수는 두 맵과, 동일한 키를 가진 항목을 어떻게 처리할지 결정하는 함수를 받아 새 맵을 돌려줘요.

참고: Map의 다른 모든 함수와 마찬가지로, 입력 맵은 수정되지 않아요.

# StringMap.union;;
- : (string -> 'a -> 'a -> 'a option) ->
    'a StringMap.t -> 'a StringMap.t -> 'a StringMap.t
= <fun>

중복 키 해석 함수의 예시들을 볼게요.

# let pick_fst key v1 _ = Some v1;;
val pick_fst : 'a -> 'b -> 'c -> 'b option = <fun>

# let pick_snd key _ v2 = Some v2;;
val pick_snd : 'a -> 'b -> 'c -> 'c option = <fun>

# let drop _ _ _ = None;;
val drop : 'a -> 'b -> 'c -> 'd option = <fun>
  • pick_fst는 결과의 값을 첫 번째 맵에서 고른다
  • pick_snd는 결과의 값을 두 번째 맵에서 고른다
  • drop은 결과 맵에서 두 항목을 모두 버린다
# StringMap.(
    union pick_fst lucky_numbers updated_lucky_numbers
    |> find_opt "charstring88"
  );;
- : int option = Some 88

# StringMap.(
    union pick_snd lucky_numbers updated_lucky_numbers
    |> find_opt "charstring88"
  );;
- : int option = Some 99

# StringMap.(
    union drop lucky_numbers updated_lucky_numbers
    |> find_opt "charstring88"
  );;
- : int option = None

맵 필터링하기 (Filtering a Map)

맵을 필터링하려면 filter 함수를 써요. 항목을 걸러 낼 조건자와 맵을 받아요. 조건자를 만족하는 항목들을 담은 새 맵을 돌려줘요.

# let even_numbers =
  StringMap.filter
    (fun _ number -> number mod 2 = 0)
    lucky_numbers;;
val even_numbers : int StringMap.t = <abstr>

맵에 맵하기 (Map a Map)

Map 모듈에는 map 함수가 있어요.

StringMap.map;;
- : ('a -> 'b) -> 'a StringMap.t -> 'b StringMap.t = <fun>

lucky_numbers 맵은 문자열 키를 정수 값과 연관지어요.

# lucky_numbers;;
- : int StringMap.t = <abstr>

StringMap.map을 사용해 키를 문자열 값과 연관짓는 맵을 만들어 볼게요.

# let lucky_strings = StringMap.map string_of_int lucky_numbers;;
val lucky_strings : string StringMap.t = <abstr>

두 맵의 키는 같아요. 각 키에 대해 lucky_numbers의 값은 string_of_int를 사용해 lucky_strings의 값으로 변환돼요.

# lucky_numbers |> StringMap.find "leostera" |> string_of_int;;
- : string = "2112"

# lucky_strings |> StringMap.find "leostera";;
- : string = "2112"

커스텀 키 타입을 가진 맵 (Maps With Custom Key Types)

커스텀 키 타입을 가진 맵을 만들어야 한다면, 두 가지를 구현한 모듈을 Map.Make 펑터에 넘겨줄 수 있어요.

  1. 맵 키의 타입을 드러내는 t 타입
  2. t 값을 비교하는 compare : t -> t -> int 함수

음수가 아닌 숫자를 위한 커스텀 맵을 정의해 볼게요.

먼저 대소문자를 구분하지 않는 방식으로 문자열을 비교하는 문자열 모듈을 정의하고 시작할게요.

# module Istring = struct
    type t = string
    let compare a b = String.(compare (lowercase_ascii a) (lowercase_ascii b))
  end;;
module Istring : sig type t val compare : t -> t -> int end

우리 모듈에 type t와 compare 함수가 있다는 것을 주목하세요. 이제 Map.Make 펑터를 호출해 음수가 아닌 숫자를 위한 맵을 얻을 수 있어요.

# module IstringMap = Map.Make(Istring);;
module IstringMap :
  sig
    type key = Istring.t
    type 'a t = 'a Map.Make(Istring).t
    val empty : 'a t
    val is_empty : 'a t -> bool
    val mem : key -> 'a t -> bool
    val add : key -> 'a -> 'a t -> 'a t
    val update : key -> ('a option -> 'a option) -> 'a t -> 'a t
    val singleton : key -> 'a -> 'a t
    val remove : key -> 'a t -> 'a t
    (* ... *)
end

# let lucky_int_numbers = IstringMap.of_seq @@ List.to_seq [
    ("leostera", 2112);
    ("charstring88", 88);
    ("divagnz", 13);
  ];;
val lucky_int_numbers : int IstringMap.t = <abstr>

결론 (Conclusion)

지금까지 OCaml의 Map 모듈을 개괄적으로 살펴봤어요. 맵은 합리적으로 효율적이고, 명령형의 Hashtbl 모듈의 대안이 될 수 있어요.

더 자세한 내용은 표준 라이브러리 문서의 Map을 참고하세요.

더 알아보기