SML - 유용한 자료구조

튜플(Tuple)은 변수를 고정된 개수만큼 모아둔 것^1↗이다. 변수의 타입은 같을 필요가 없다.

val x = (10, false, "hello")

튜플의 타입은 그것의 원소의 타입을 *로 연결한 것이다. 즉, 위의 x의 타입은 int * bool * string 이다.

당연히, 튜플 안에 튜플이 가능하다. 이를 nesting이라고 한다.

val y = (10, (20, "hello", 30), true)
(* 
  type of y: int * (int * string * int) * bool 
*)

튜플의 각 원소에 접근하는 방법은 간단하다. #index를 사용하면 된다.

val x = (10, (false, 20), "hello")

val x1 = #1 x         (* x1 is 10 *)
val x2 = #2 x         (* x2 is (false, 20) *)
val x21 = #1 (#2 x)   (* x21 is false *)

index가 1부터 시작한다는 점에 유의하자.

사실, #index는 그 자체로 함수이다. 근데 sml 에서의 함수를 call 할때, 인자가 1개일 때는 굳이 소괄호를 쓰지 않아도 된다. 하지만, 연산은 항상 left-to-right로 일어나기 때문에 다음과 같은 구문은 error를 발생시킨다.

(* 위의 x tuple을 그대로 사용 *)

val x21 = #1 #2 x
(* compiler see this as (#1 #2) x, and this causes type error. *)

즉, #1의 인자로 #2가 온다고 해석하는 것이다. #1가 인자로 받기를 기대하는(expecting) 타입은 tuple^2↗인데, tuple이 아닌 웬 이상한 함수 #2가 와서 type error가 발생하는 것이다. 따라서, sml 코드를 짤 때는 괄호를 잘 써서 연산의 순서를 명시해주자.

int pair (2-tuple)을 받아서 두 원소의 합을 반환하는 함수를 써보자.

fun sumPair (pr: int * int) =
  (#1 pr) + (#2 pr)

리스트(List)는 같은 타입의 원소를 여러개 모아둔 것이다. 크기는 고정되어있지 않기 때문에, 늘릴 수 있다.

val x = [1, 2, 3]

(* type of x: int list *)

sml에서는 임의의 타입을 alpha, beta, gamma, ... 라는 이름으로 부르는데, 이를 실제 그리스 문자를 사용해서 표기하기는 어려우므로, alpha 대신에 'a, beta 대신에 'b, ... 이런 표기법을 쓴다.
즉, 임의의 타입을 가지는 리스트의 타입은 'a list 로 쓴다.

그러면, 본격적으로 리스트를 만드는 방법에 대해 알아보자. 리스트는 다음과 같은 규칙에 의해서 만들어진다.

• []는 'a list 타입의 빈 리스트이다.
• 'a 타입의 x와, 'a list 타입의 xs 에 대하여, x::xs 는 'a list 타입의 리스트이고, 이는 xs 앞에 x를 붙인 리스트이다.

예를들어, 1::[2,3,4] = [1,2,3,4] 이다.

여기서 드는 생각이 꽤 많아야 한다. 대표적으로는, 왜 ::는 앞에만 붙일 수 있지? append같은 것은 없나? 라는 것과, 도대체 :: 는 뭐임? 같은 것이 있겠다.

답을 하자면, append는 있지만 :: 같이 근본적으로 '리스트'를 '구성'하지는 않는다. 그렇다면, ::이 상당히 특이한 녀석이라는 것인데, 이는 후에 패턴 매칭을 배우면서 자세히 다뤄볼 것이다.
일단은, :: 자체가 일종의 'a * 'a list -> 'a list 같은 함수이며, right associative한 infix operator인 것만 알고 있자.

즉, 사실 리스트 [1,2,3,4] 는 다음과 같은 방법으로 구성된 것이다.

(* [1,2,3,4] is same as *)
1 :: 2 :: 3 :: 4 :: []

어떤 리스트 xs에 대하여, 다음과 같은 유용한 함수들을 통해 원소에 접근할 수 있다.

• null xs

  xs 가 비어있다면 true를, 아니면 false를 반환한다.

• hd xs

  xs의 가장 첫번째 원소를 반환한다. 만일 xs가 empty list 이면 예외를 발생시킨다.

• tl xs

  xs에서 hd xs 를 제외한 리스트를 반환한다. 만일 xs가 empty list 이면 예외를 발생시킨다.

즉, 예시를 들자면 다음과 같다.

val xs = [1,2,3,4]

val isNull = null xs        (* false *)
val head = hd xs            (* 1 *)
val tail = tl xs            (* [2,3,4] *)

각각의 타입은 null: 'a list -> bool, hd: 'a list -> 'a, tl: 'a list -> 'a list 임을 쉽게 확인할 수 있을 것이다.

(* Sum all element in the list
   ex) sumList([1,2,3,4]) = 10 *)
fun sumList (xs: int list) = 
  if null xs
  then 0
  else (hd xs) + sumList(tl xs)


(* Find nth element of list. 
   If fails, return 0 (bad style! but skip now)
   ex) findNth([1,2,3,4], 2) = 3 *)
fun findNth (xs: 'a list, n: int) =
  if null xs
  then 0
  else if n = 0
       then (hd xs)
       else findNth(tl xs, n - 1)


(* Append ys to the end of xs.
   ex) append([1,2,3,4], [5,6,7]) = [1,2,3,4,5,6,7] *)
fun append (xs: 'a list, ys: 'a list) =
  if null xs
  then ys
  else (hd xs)::append(tl xs, ys) 

참고로, 두 리스트를 append 하는 것은 다음과 같은 sml 내장 operator @을 이용해서도 할 수 있다.

[1,2,3,4] @ [5,6,7]     (* same with append([1,2,3,4], [5,6,7])
                           which results [1,2,3,4,5,6,7] *)

record는 필드와 값을 가진다. 다음 예시 코드를 보자.

val x = {name = "monognuisy", id = 123456}

(* type of x is {name: string, id: int} *)

record는 마치 C의 구조체(struct)와도 닮았다.

record는 필드의 이름으로 값에 접근할 수 있다. 다음과 같이 말이다.

val x = {name = "monognuisy", id = 123456}

val xname = #name x   (* xname = "monognuisy" *)
val xid = #id x       (* xid = 123456 *)

응? 이렇게 보니 마치 '튜플'같다. 실제로, 이 레코드는 튜플과 연관이 있다.

사실, 튜플 (e1, e2, ..., en)은 레코드 {1 = e1, 2 = e2, ..., n = en}를 조금 다르게 쓴 것이다. 즉, 튜플은 '필드 이름이 숫자인 레코드' 라는 것이다.

하지만, 필드 이름을 숫자로 하는 것은 가독성에도 나쁜 영향을 끼치고, 튜플이라는 것이 sml에서 워낙 많이 쓰이다 보니 조금 더 간편하게(?) 쓸 수 있도록 만든 것이다. 이런 것을 Syntactic sugar 라고 한다.