[scala] List 정의와 예시

scala의 List 연산자 중, 

:::는 triple colon이라고 하고, 

::는 cons(콘즈)라고 한다.

Scala의 List는 단방향 연결 리스트이고 sealed abstract class이다. Nil과 ::라는 구현이 있다.

sealed trait List[+A] 

case object Nil extends List[Nothing] 

case class ::[A](head: A, tail: List[A]) extends List[A] 

List 트레이트 정의에 플러스(+) 기호가 있는 것을 주목한다. 플러스 기호는 List가 타입 매개변수 A에 공변성(covariant)이 있다는 것을 가르킨다. 공변성은 일반적인 타입에 다형성 제약을 표현할 수 있다. 예를 들면 다음 클래스를 살펴본다.

sealed trait Base

case class BaseImpl(value: Int) extends Base

여기에 Base와 Impl 간에 관계를 설명한다. Impl 클래스는 Base의 서브 타입이다. List가 함께 쓰인다면, 공변성은 List[Impl]은 List[Base]의 서브 타입이라는 뜻을 의미한다. 예시로 표현한 것은 공변성이 다음 코드를 컴파일할 수 있음을 의미한다. 

val bases : List[Base] = List[BaseImpl](BaseImpl(1))
println(bases)

결과는 다음과 같다.

List(BaseImpl(1))

이제 간단한 List 예시를 살펴본다. 적당하게 List를 선언한다. 

val list1 = List(1,2)
val list2 = List(3)

:: (콘즈)를 사용한다. 

val list3 = list1 :: list2
println(list3)

결과는 다음과 같다.리스트의 엘리먼트가 리스트가 되었다.

List(List(1, 2), 3)

이번에는 triple 리스트를 보자. 

val list4 = list1 ::: list2
println(list4)
val list4_1 = list2.:::(list1)
println(list4_1)

결과는 다음과 같다.

List(1, 2, 3)

::(콘즈)는 ::를 사용할 때와 .::()을 사용할 때가 정 반대임을 잘 기억하면 좋다.  ::(콘즈)는 두번째 리스트 끝에 첫번째 리스트를 붙이라는 의미를 가진다. 

val list5 = ::(1, ::(2, ::(3, Nil)))
println(list5)

val list5_1 = (1 :: (2 :: (3 :: Nil)))
println(list5_1)

val list5_2 = Nil.::(3).::(2).::(1)
println(list5_2)

val list5_3 = 1 :: 2 :: 3 :: Nil
println(list5_3)

결과는 모두 갖으며, 다음과 같다.

List(1, 2, 3)

List(1, 2, 3)

List(1, 2, 3)

List(1, 2, 3)

List는 다른 콜렉션과 다르게 패턴 매치 기능을 가지고 있다. ::(콘즈)와 함께 사용하면 재미있는 것을 만들어 볼 수 있다. List의 엘리먼트를 순차적으로 패턴매치를 하는 예시이다. 

0 엘리먼트부터 시작하는 경우에 대해서 다음 엘리먼트를 x에 저장하고 나머지를 rest로 저장하고 위해, 위에서 사용했던 ::을 사용해봤다. (0 :: x :: rest)

List(0, 1, 2, 3, 4, 5) match {
  case 0 :: x :: rest => println(s"2번째: $x, 나머지: $rest")
  case _ => println("others")
}

결과는 다음과 같다.

2번째: 1, 나머지: List(2, 3, 4, 5)

만약 아래 내용을 추가하지 않았다면, warning이 발생한다.

List(0, 1, 2, 3, 4, 5) match {
  case 0 :: x :: rest => println(s"2번째: $x, 나머지: $rest")
 }

scala에서는 List의 엘리먼트가 원치 않은 값에 대해서 처리할 수 없음을 warning으로 알려준다. 이런 이유로 case _ 구문을 추가했다.

Warning:(40, 9) match may not be exhaustive.

It would fail on the following inputs: List((x: Int forSome x not in 0)), List((x: Int forSome x not in 0), _), List(0), Nil

    List(0, 1, 2, 3, 4, 5) match {

정상적으로 출력되는지 확인하기 위해 다르게 테스트해본다.

List(6, 1, 2, 3, 4, 5, null) match {
  case 0 :: x :: rest => println(s"2번째: $x, 나머지: $rest")
  case _ => println("others")
}

결과는 다음과 같다. 

others

Scala의 List에 ::과 :::가 지원하는 것은 List에 prepend 연산이 최적화되어 있기 때문일지 모르겠다. 앞에 붙이는 연산은 싸고, 뒤로 붙이는 연산은 비싸다. 뒤에 붙이면 deep copy하고 새로운 리스트를 생성한다.

scala 문서(http://docs.scala-lang.org/overviews/collections/performance-characteristics.html)에 나온 이유가 이런 이유이다. append 연산은 constant time이지만, insert나 prepend는 linear하다. 

head	tail	apply	update	prepend	append	insert
immutable
List	C	C	L	L	C	L	-

C	The operation takes (fast) constant time.

L	The operation is linear, that is it takes time proportional to the collection size.