리스트

리스트 (Lists)

OCaml에서 리스트는 순서가 있는 요소들의 나열이에요. 리스트 안의 모든 요소는 같은 타입이어야 해요. 리스트는 언어에 내장되어 있고 특별한 문법을 가져요. 먼저 정수 세 개짜리 리스트를 볼게요.

# [1; 2; 3];;
- : int list = [1; 2; 3]

요소를 구분할 때 쉼표가 아니라 세미콜론(;)을 쓴다는 점을 주의하세요. 빈 리스트는 []라고 쓰고, 이 정수 리스트의 타입은 int list예요.

리스트가 비어있지 않다면 머리(head, 첫 번째 요소)와 꼬리(tail, 나머지 요소들로 이루어진 리스트)를 가져요. 우리 예시에서 머리는 정수 1이고 꼬리는 리스트 [2; 3]이에요. 빈 리스트는 머리도 꼬리도 없어요. 리스트를 몇 개 더 살펴볼게요.

# [];;
- : 'a list = []
# [1; 2; 3];;
- : int list = [1; 2; 3]
# [false; true; false];;
- : bool list = [false; true; false]
# [[1; 2]; [3; 4]; [5; 6]];;
- : int list list = [[1; 2]; [3; 4]; [5; 6]]

빈 리스트의 타입이 'a list라는 점을 눈여겨보세요 (그 요소 타입은 아직 정해지지 않았어요). 마지막 리스트의 타입 int list list, 즉 정수 리스트의 리스트라는 것도 확인해 두세요.

리스트에는 내장 연산자가 두 개 있어요. ::는 cons 연산자로 리스트의 맨 앞에 요소 하나를 추가하고, @는 append 연산자로 리스트 둘을 이어 붙여요.

# 1 :: [2; 3];;
- : int list = [1; 2; 3]
# [1] @ [2; 3];;
- : int list = [1; 2; 3]

리스트에 대한 함수 (Functions on Lists)

패턴 매칭을 이용하면 리스트를 다루는 함수를 작성할 수 있어요.

# let rec total l =
    match l with
    | [] -> 0
    | h :: t -> h + total t;;
val total : int list -> int = <fun>
# total [1; 3; 5; 3; 1];;
- : int = 13

리스트의 길이를 구하는 함수를 생각해 볼게요.

# let rec length l =
    match l with
    | [] -> 0
    | _ :: t -> 1 + length t;;
val length : 'a list -> int = <fun>

이 함수는 정수 리스트뿐 아니라 어떤 종류의 리스트에도 동작해요.

# length [1; 2; 3];;
- : int = 3
# length ["cow"; "sheep"; "cat"];;
- : int = 3
# length [[]];;
- : int = 1

왜 그럴까요? 패턴 _ :: t에서는 리스트의 머리를 조사하지 않으니 그 타입이 결과에 영향을 주지 않기 때문이에요. 이런 함수를 다형적(polymorphic)이라고 불러요. @ 연산자를 직접 구현한 또 다른 다형적 함수를 볼게요.

# let rec append a b =
  match a with
  | [] -> b
  | h :: t -> h :: append t b;;
val append : 'a list -> 'a list -> 'a list = <fun>

이때 두 번째 리스트의 메모리는 공유되지만, 첫 번째 리스트는 사실상 복사된다는 점을 알아두세요.

리스트의 고차 함수 (Higher Order Functions on Lists)

리스트의 각 요소에 함수를 적용해 새 리스트를 얻고 싶을 수 있어요. 다른 함수를 인자로 받는 map 함수를 작성해 볼게요. 이렇게 함수를 인자로 받는 함수를 "고차 함수"라고 불러요.

# let rec map f l =
    match l with
    | [] -> []
    | h :: t -> f h :: map f t;;
val map : ('a -> 'b) -> 'a list -> 'b list = <fun>

전체 타입 안에서 함수 f의 타입이 괄호로 묶여 있는 것을 확인하세요. 이 map 함수는 타입 'a -> 'b의 함수와 'a 리스트를 받아 'b 리스트를 만들어 내요. 물론 'a와 'b가 같은 타입일 때도 있어요. map 사용 예시 두 개를 볼게요.

# map (fun x -> x * 2) [1; 2; 3];;
- : int list = [2; 4; 6]
# map total [[1; 2]; [3; 4]; [5; 6]];;
- : int list = [3; 7; 11]

표준 라이브러리의 List 모듈 (The Standard Library List Module)

표준 라이브러리 List 모듈에는 아주 다양한 유틸리티 함수가 들어 있어요. 우리가 이 튜토리얼에서 직접 작성한 함수들이 이미 구현된 버전도 그중에 포함돼요. 인자에 라벨이 붙은 버전은 StdLabels의 일부로 제공돼요.

List 모듈 문서에서는 예외를 발생시킬 수 있는 함수에 표시를 해 두었어요. 그런 예외는 보통 리스트가 비어 있거나(그래서 머리도 꼬리도 없거나), 길이가 맞지 않는 리스트 때문에 생겨요.

맵과 이터레이터 (Maps and Iterators)

map 함수는 우리가 처음부터 직접 작성해 봤는데, 그게 List 모듈에 이미 들어 있는 건 당연해요. 리스트 두 개를 받는 변형 함수도 있어요.

# List.map2 ( + ) [1; 2; 3] [4; 5; 6];;
- : int list = [5; 7; 9]

추가로 map의 명령형(imperative) 버전인 iter도 있어요. iter는 타입 'a -> unit의 함수와 'a list를 받아 각 요소에 그 함수를 차례로 적용해요. print_endline이 딱 어울리는 함수예요.

# List.iter print_endline ["frank"; "james"; "mary"];;
frank
james
mary
- : unit = ()

리스트 두 개를 받는 변형 iter2도 있어요.

# List.iter2
    (fun a b -> print_endline (a ^ " " ^ b))
    ["frank"; "james"; "mary"]
    ["carter"; "lee"; "jones"];;
frank carter
james lee
mary jones
- : unit = ()

map2와 iter2는 두 리스트의 길이가 다르면 실패한다는 점을 기억하세요.

# List.map2 ( + ) [1; 2; 3] [4; 5];;
Exception: Invalid_argument "List.map2".

리스트 스캔 (List Scanning)

유용한 함수 mem은 리스트의 내용을 훑어서 주어진 요소가 멤버로 있는지 확인해요.

# List.mem "frank" ["james"; "frank"; "mary"];;
- : bool = true
# List.mem [] [[1; 2]; [3]; []; [5]];;
- : bool = true

더 정교한 스캔 함수들도 있어요. 리스트의 모든 요소가 짝수인지, 혹은 어떤 요소 하나라도 짝수인지 확인하고 싶다고 생각해 보죠. 리스트의 각 요소를 돌면서 불리언 검사를 유지하는 함수를 직접 쓸 수도 있고, 이미 알고 있는 mem 같은 함수를 활용할 수도 있어요.

# let all =
    not (List.mem false (List.map (fun x -> x mod 2 = 0) [2; 4; 6; 8]));;
val all : bool = true
# let any =
    List.mem true (List.map (fun x -> x mod 2 = 0) [1; 2; 3]);;
val any : bool = true

이건 좀 번거롭네요. 표준 라이브러리는 이 흔한 문제를 위해 유용한 함수 for_all과 exists를 제공해요.

# List.for_all (fun x -> x mod 2 = 0) [2; 4; 6; 8];;
- : bool = true
# List.exists (fun x -> x mod 2 = 0) [1; 2; 3];;
- : bool = true

이렇게 보면 표준 라이브러리가 지금의 모습까지 어떻게 진화해 왔는지 짐작할 수 있어요. 자주 쓰이는 코드 조각들이 유용한 일반 함수로 바뀐 거죠.

리스트 검색 (List Searching)

find 함수는 주어진 조건자(predicate, 요소를 받아 true나 false를 돌려주는 검사 함수)와 일치하는 리스트의 첫 번째 요소를 돌려줘요. 그런 요소를 찾지 못하면 예외를 발생시켜요.

# List.find (fun x -> x mod 2 = 0) [1; 2; 3; 4; 5];;
- : int = 2
# List.find (fun x -> x mod 2 = 0) [1; 3; 5];;
Exception: Not_found.

filter 함수는 역시 조건자를 받아 리스트의 각 요소에 검사를 적용하는데, 이번에는 검사가 true인 모든 요소로 이루어진 리스트를 돌려줘요.

# List.filter (fun x -> x mod 2 = 0) [1; 2; 3; 4; 5];;
- : int list = [2; 4]

어떤 요소가 검사에 걸리지 않았는지도 알고 싶다면 partition을 쓸 수 있어요. 조건자가 true인 요소들의 리스트와 false인 요소들의 리스트, 이렇게 리스트 두 개의 쌍을 돌려줘요.

# List.partition (fun x -> x mod 2 = 0) [1; 2; 3; 4; 5];;
- : int list * int list = ([2; 4], [1; 3; 5])

filter와 partition의 문서는 입력의 순서가 출력에서 보존된다고 알려줘요. 문서에서 명시하지 않는 경우에는 그런 보존을 가정할 수 없어요.

연관 리스트 (Association Lists)

연관 리스트는 사전(dictionary) 자료구조, 즉 각각 연관된 값을 가진 키들의 묶음을 구현하는 간단한(그리고 단순한) 방법이에요. 큰 사전에는 효율을 위해 표준 라이브러리의 Map이나 Hashtbl 모듈을 쓰는 게 좋아요. 하지만 List 모듈의 이런 함수들은 대체로 작은 리스트에 유용하고, 다른 장점도 있어요. 그냥 쌍들의 리스트이기 때문에 쉽게 만들고 수정할 수 있고, toplevel에서도 쉽게 출력할 수 있죠.

# List.assoc 4 [(3, "three"); (1, "one"); (4, "four")];;
- : string = "four"
# List.mem_assoc 4 [(3, "three"); (1, "one"); (4, "four")];;
- : bool = true

연관 리스트를 사용할 때나 다른 목적에서, 리스트들의 쌍에서 쌍들의 리스트를 만들거나 그 반대를 만들 수 있으면 유용할 때가 있어요. List 모듈은 이 용도를 위해 split과 combine 함수를 제공해요.

# List.split [(3, "three"); (1, "one"); (4, "four")];;
- : int list * string list = ([3; 1; 4], ["three"; "one"; "four"])
# List.combine [3; 1; 4] ["three"; "one"; "four"];;
- : (int * string) list = [(3, "three"); (1, "one"); (4, "four")]

리스트 정렬 (Sorting Lists)

List.sort 함수는 타입 'a -> 'a -> int의 비교 함수(같으면 0, 첫 번째가 작으면 음수, 두 번째가 작으면 양수)와 타입 'a list의 입력 리스트를 받아, 그 비교 함수 기준으로 정렬된 리스트를 돌려줘요. 보통은 내장 비교 함수 compare를 쓰는데, 이 함수는 같은 타입의 두 값을 (비교할 수 없는 함수를 제외하고) 비교해요.

# List.sort compare [1; 4; 6; 4; 1];;
- : int list = [1; 1; 4; 4; 6]
# List.sort compare ["Reynolds"; "Smith"; "Barnes"];;
- : string list = ["Barnes"; "Reynolds"; "Smith"]
# List.sort (Fun.flip compare) [1; 4; 6; 4; 1];;
- : int list = [6; 4; 4; 1; 1]
# List.sort compare [(1, 3); (1, 2); (2, 3); (2, 2)];;
- : (int * int) list = [(1, 2); (1, 3); (2, 2); (2, 3)]
# List.sort
    (fun a b -> compare (fst a) (fst b))
    [(1, 3); (1, 2); (2, 3); (2, 2)];;
- : (int * int) list = [(1, 3); (1, 2); (2, 3); (2, 2)]

Fun.flip 함수는 이항 함수의 인자 순서를 뒤집어요.

폴드 (Folds)

List 모듈에는 이름이 재미있는 함수가 두 개 있어요. fold_left와 fold_right예요. 이 함수들의 역할은 주어진 함수로 리스트의 요소들을 결합하면서 답을 누적(accumulate)하고, 그 답을 돌려주는 것이에요. 돌려받는 답은 주어진 함수, 리스트의 요소들, 그리고 제공한 누적기의 초기값에 달려 있어요. 그래서 상당히 일반적인 함수라고 상상할 수 있겠죠. 먼저 fold_left를 살펴볼게요.

이 예시에서는 덧셈 함수와 초기 누적값 0을 제공해요.

# List.fold_left ( + ) 0 [1; 2; 3];;
- : int = 6

결과는 리스트 요소들의 합이에요. 이번에는 덧셈 함수 대신, 주어진 두 정수 중 큰 값을 돌려주는 OCaml 내장 max 함수를 써 볼게요. 초기 누적값으로는 가능한 가장 작은 정수인 min_int를 사용해요.

# List.fold_left max min_int [2; 4; 6; 0; 1];;
- : int = 6

리스트에서 가장 큰 수가 찾아졌어요. 이제 fold_left 함수의 타입을 살펴볼게요.

# List.fold_left;;
- : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a = <fun>

함수는 타입 'a -> 'b -> 'a인데, 여기서 'a는 누적기, 'b는 리스트 각 요소의 타입이에요. 다음 인자는 타입 'a여야 하는 초기 누적기이고, 마지막으로 타입 'b list의 입력 리스트가 와요. 결과는 누적기의 최종 값이므로 타입이 'a여야 해요. 물론 위 두 예시에서는 'a와 'b가 서로 같지만, 항상 그런 건 아니에요.

fold_right를 사용한 append 정의를 살펴볼게요. (fold_left는 요소를 왼쪽부터, fold_right는 오른쪽부터 고려해요.)

# let append x y =
    List.fold_right (fun e a -> e :: a) x y;;
val append : 'a list -> 'a list -> 'a list = <fun>

이 예시에서 초기 누적기는 두 번째 리스트이고, 첫 번째 리스트의 각 요소가 차례로 그 앞에 cons돼요. fold right의 인자 순서는 조금 다르다는 것을 볼 수 있어요.

# List.fold_right;;
- : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b = <fun>

함수가 먼저 오고, 그다음에 요소들의 리스트, 그다음에 초기 누적값이 와요. fold_right를 사용해 우리의 보통 map 함수를 정의할 수도 있어요.

# let map f l =
    List.fold_right (fun e a -> f e :: a) l [];;
val map : ('a -> 'b) -> 'a list -> 'b list = <fun>

하지만 주의가 필요해요. 리스트들의 리스트를 이어 붙여 하나의 리스트로 만드는 List.concat에 이 방식을 적용하면 이런 결과가 나와요.

# let concat l = List.fold_left ( @ ) [] l;;
val concat : 'a list list -> 'a list = <fun>

아쉽게도 여기서 평가 순서 때문에 점점 더 큰 항목들이 @ 연산자의 첫 번째 인자로 전달돼서, 이 함수의 실행 시간이 List.concat보다 나빠져요. 리스트와 기타 일반적인 OCaml 자료구조의 시간·공간 효율성에 대해 더 알고 싶다면 표준 컨테이너 비교 문서를 참고할 수 있어요.

여기 fold_left나 fold_right로 다시 정의한 익숙한 함수들이 몇 개 더 있어요. 어떻게 동작하는지 직접 짐작해 볼 수 있을까요?

# let length' l =
    List.fold_left (fun a _ -> a + 1) 0 l;;
val length' : 'a list -> int = <fun>
# let rev' l =
    List.fold_left (fun a e -> e :: a) [] l;;
val rev' : 'a list -> 'a list = <fun>
# let split' l =
    List.fold_right
      (fun (x, y) (xs, ys) -> (x :: xs, y :: ys))
      l
      ([], []);;
val split' : ('a * 'b) list -> 'a list * 'b list = <fun>

리스트와 꼬리 재귀 (Lists and Tail Recursion)

앞에서 정의했던 length 함수는 입력 리스트의 크기에 비례하는 중간 표현식을 쌓아 올려요.

   length [1; 2; 3]
=> 1 + length [2; 3]
=> 1 + (1 + length [3])
=> 1 + (1 + (1 + length []))
=> 1 + (1 + (1 + 0))
=> 1 + (1 + 1)
=> 1 + 2
=> 3

참고 위 내용은 OCaml 문법이 아니라 length [1; 2; 3]의 평가가 어떻게 일어나는지 설명하기 위한 그림이에요. => 기호는 평가 단계 하나를 나타내요.

긴 리스트에서는 이렇게 하면 스택이 넘칠(컴퓨터가 처리하기엔 너무 커질) 수 있어요. 해결책은 누적 인자(accumulating parameter)를 쓰는 함수를 작성하는 것이에요.

# let rec length acc l =
    match l with
    | [] -> acc
    | _ :: t -> length (acc + 1) t;;
val length : int -> 'a list -> int = <fun>
# let l = length 0 [1; 2; 3];;
val l : int = 3

이 함수는 이제 스택에서 일정한 양의 공간만 사용해요.

   length 0 [1; 2; 3]
=> length 1 [2; 3]
=> length 2 [3]
=> length 3 []
=> 3

이런 함수를 꼬리 재귀적(tail-recursive)이라고 불러요. 초기 누적값이 자동으로 제공되도록 래퍼(wrapper) 함수를 작성할 수도 있어요.

# let rec length_inner acc l =
    match l with
    | [] -> acc
    | _ :: t -> length_inner (acc + 1) t;;
val length_inner : int -> 'a list -> int = <fun>
# let length l = length_inner 0 l;;
val length : 'a list -> int = <fun>

아니면 한 함수 안에서 모두 처리할 수도 있어요.

# let length l =
    let rec length_inner acc l =
      match l with
      | [] -> acc
      | _ :: t -> length_inner (acc + 1) t
    in
      length_inner 0 l;;
val length : 'a list -> int = <fun>

표준 라이브러리 문서에서는 꼬리 재귀적이지 않은 함수에 표시를 해 두었어요.

더 알아보기