[Scala] Data Structures

3.1 함수적 자료구조의 정의

순수함수는 자료를 변경하거나, 기타 부수 효과를 수행하는 일이 없어야함.

따라서 함수적 자료구조는 정의에 의해 불변이 ( Immutable ) 이다.

자료구조의 조작시 기존의 변수를 수정하는 것이 아닌, 새로운 변수를 생성.

그렇다면, 여분의 복사가 많이 일어나지 않을까? 답은 "그렇지 않다"

 

단일 연결 목록

trait

하나의 추상 인터페이스로, 필요하다면 메서드의 구현을 담을 수 있다.

sealed 

모든 메서드가 이 파일 안에 선언되어 있어야 함을 뜻함 (abstract class를 사용해도 된다)

case

list의 두가지 구현, 즉 두가지 자료 생성자

이들은 list가 취할 수 있는 두 가지 형태를 나타낸다.

 

공변과 불변에 대해
trait List[+A] 선언에서 형식 매개변수 A 앞에 붙은 +는 A가 List의 공변(covariant) 매개 변수임을 뜻하는 가변 지정자(variance annotation: 가변 주해)이다. 그러한 매개변수를 '양의(positive)' 매개변수라고 부르기도 한다. 이것이 뜻하는 바는, 예를 들어 만일 Dog가 Animal의 하위형식(subtype)이면 List[Dog]가 List[Animal]의 하위형식으로 간주된다는 것이다. (좀 더 일반화하자면, X가 Y의 하위형식이라는 조건을 만족하는 모든 형식 X와 Y에 대해, List[X]는 List[Y]의 하위형식이다.) 반면, 만일 A 앞에 +가 없으면 그 형식 매개변수에 대해 List는 불변(invariant)이다.

그런데 Nil이 List[Nothing]을 확장(extends)함을 주목하자. Nothing은 모든 형식의 하위형식이고 A가 공변이므로 Nil을 List[Int]나 List[Double] 등 그 어떤 형식의 목록으로도 간주할 수 있다. 이는 우리가 정확히 원했던 것이다.

공변/불변에 관한 이러한 사항들이 현재의 논의에 아주 중요하지는 않다. 이들은 사실 스칼라가 하위형식을 이용해서 자료 생성자를 부호화하는 방식에 기인한 군더더기에 가까우므로, 지금 당장 이들이 명확히 이해되지 않는다고 해도 걱정할 필요는 없다. 가변 지정자를 전혀 사용하지 않고 코드를 작성하는 것도 얼마든지 가능하며, 그러면 함수 서명들이 다소 간단해진다(반면 형식 추론은 더 나빠지는 경우가 많겠지만).

 

3.2 pattern matching

그럼 object List에 속한 함수 sum과 product를 자세히 살펴보자. 이런 함수들을 List의 동반 객체(companion object)라고 부르기도 한다. 두 함수 모두 패턴 부합을 활용한다.

  
  def sum(ints: List[Int]): Int = ints match { // A function that uses pattern matching to add up a list of integers
    case Nil => 0 // The sum of the empty list is 0.
    case Cons(x,xs) => x + sum(xs) // The sum of a list starting with `x` is `x` plus the sum of the rest of the list.
  }

  def product(ds: List[Double]): Double = ds match {
    case Nil => 1.0
    case Cons(0.0, _) => 0.0
    case Cons(x,xs) => x * product(xs)
  }

 

Companion object

스칼라의 동반 객체
자료 형식과 자료 생성자와 함께 동반 객체(또는 짝 객체)를 선언하는 경우가 많다. 동반 객체는 자료 형식과 같은 이름(지금 예에서는 List)의 object로, 자료 형식의 값들을 생성하거나 조작하는 여러 편의용 함수들을 담는 목적으로 쓰인다.
예를 들어 요소 a의 복사본 n개로 이루어진 List를 생성하는 def fill[A] (n: Int, a: A): List[A]라는 함수가 필요하다면, 그러한 함수를 List의 동반 객체의 메서드로 만드는 것이 바람직하다. 스칼라에서 동반 객체는 관례에 가깝다. 이 모듈의 이름을 Foo라고 해도 안 될 것은 없지만, List라고 하면 이 모듈이 목록을 다루는 데 관련된 함수를 담고 있음이 좀 더 명확해진다.

패턴 부합은 표현식의 구조를 따라 내려가면서 그 구조의 부분 표현식을 추출하는 복잡한 switch 문과 비슷하게 작동한다. 패턴 부합 구문은 ds 같은 표현식으로 시작해서 그다음에 키워드 match가 오고, 그다음에 일련의 경우(case) 문들이 {}로 감싸인 형태이다. 부합의 각 경우 문은 =>의 좌변에 패턴(Cons(x, xs) 등)이 있고, 그 우변에 결과(x * product(xs))가 있는 형태이다. 대상이 경우 문의 패턴과 부합 하면, 그 경우 문의 결과가 전체 부합 표현식의 결과가 된다. 만일 대상과 부합하는 패턴이 여러 개이면 스칼라는 처음으로 부합한 경우 문을 선택한다.

• List(1, 2, 3) match { case _ => 42 } 는 42가 된다. 이 예는 임의의 표현식과 부합하는 변수 패턴 _ 을 사용한다. _ 대신 x나 foo를 사용해도 되지만, 경우 문의 결과 안에서 그 값이 무시되는 변수를 나타낼 때에는 이처럼 _ 를 사용하는 것이 보통이다.
• List(1, 2, 3) match { case Cons(h, _ ) => h } 의 경과는 1이다. 이 예는 자료 생성자 패턴과 변수들을 함께 사용해서 대상의 부분 표현식을 묶는다.
• List(1, 2, 3) match { case Cons(_ , t) => t } 의 결과는 List(2, 3)이다.
• List(1, 2, 3) match { case Nil => 42 } 의 결과는 실행시점 MatchError 오류이다. MatchError는 부합 표현식의 경우 문 중 대상과 부합하는 것이 하나도 없음을 뜻한다.

스칼라의 가변 인수 함수
object List의 apply 함수는 가변 인수 함수*(variadic function)이다. 이는 이 함수가 A 형식의 인수를 0개 이상 받을(즉, 하나도 받지 않거나 하나 또는 여러 개를 받을) 수 있음을 뜻한다.

        def apply[A](as: A*): List[A] = 
            if (as.isEmpty) Nil
            else Cons(as.head, apply(as.tail: _*))

자료 형식을 만들 때에는, 자료형식의 인스턴스를 편리하게 생성하기 위해 가변 인수 apply 메서드를 자료 형식의 동반 객체에 집어넣는 관례가 흔히 쓰인다. 그런 생성 삼수의 이름을 apply로 해서 동반 객체에 두면, List(1, 2, 3, 4)나 List(“hi”, “bye”)처럼 임의의 개수의 인수들을 쉼표로 구분한 구문(이를 목록 리터럴[list literal] 또는 그냥 리터럴 구문이라고 부르기도 한다)으로 함수를 호출할 수 있다.
가변 인수 함수는 요소들의 순차열을 나타내는 Seq를 생성하고 전달하기 위한 작은 구문적 겉치레일 뿐이다. Seq는 스칼라의 컬렉션 라이브러리에 있는 하나의 인터페이스로, 목록이나 대기열, 벡터 같은 순차열 비슷한 자료구조들이 구현하도록 마련된 것이다. apply 안에서 인수 as는 Seq[A]에 묶인다. Seq[A]에는 head(첫 요소를 돌려줌)와 tail(첫 요소를 제외한 나머지 모든 요소를 돌려줌)이라는 함수가 있다. 특별한 형식 주해인 _ 는 Seq를 가변 인수 메서드에 전달할 수 있게 한다.