[스칼라] 리스트 구현

Programming in scala 4th edition 22장

 

1. 스칼라 리스트

List는 scala.collection.immutable 내에 추상 클래스로 정의되어있다.

sealed abstract class List[+A] {
  ...
}

타입 파라미터가 +A로 선언되어있기 때문이 List는 공변적이다. 따라서 List[Int]는 List[Any] 타입의 변수에 할당할 수 있다.

List에는 다음 세 가지 연산이 추상메서드로 정의되어있고 모든 리스트 연산은 세 가지 기본 메서드로 만들 수 있다.

def isEmpty: Boolean
def head: A
def tail: List[A]

스칼라는 추상 클래스인 List를 상속받아 ::[A]와 Nil를 정의한다.

 

Nil 객체

Nil 객체는 빈 리스트를 나타낸다. 

case object Nil extends List[Nothing] {
  override def isEmpty = true
  def head: Nothing = throw new NoSuchElementException("head of empty list")
  def tail: List[Nothing] = throw new NoSuchElementException("tail of empty list")
}

 

:: 클래스

constructor의 약자인 cons라고 불리는 클래스, 비어있지 않은 리스트를 나타낸다. 스칼라는 어떤 패턴의 중위 연산자를 중위 연산자를 나타내는 클래스의 생성자에 피연산자들을 인자로 넘긴 형태로 다룬다. 그러니까 x :: xs 는 ::(x, xs)이다.

final case class ::[A](hd: A, tl: List[A]) extends List[A] {
  def head = hd
  def tail = tl
  override def isEmpty: Boolean = false
}

위는 ::의 구현이다.

 

추가적인 메서드

head, tail, isEmpty 세 가지 기본 메서드를 가지고 추가적인 메서드를 구현 할 수 있다.

def length: Int = if(isEmpty) 0 else 1 + tail.length

def drop(n: Int): List[T] = if(isEmpty) Nil else if (n <= 0) this else tail.drop(n - 1)

def map[B](f: A => B): List[B] = {
  if (isEmpty) Nil
  else f(head) :: tail.map(f)
}

 

리스트 구성

리스트는 ::, ::: 두 가지 구성 메서드가 있다. 두 메서드는 콜론으로 끝나기 때문에 x :: xs 는 xs.::(x), x ::: xs는 xs.:::(x)와 같다. 리스트 클래스 내의 :: 메서드의 정의는 아래와 같다.

def ::[B >: A](x: B): List[B] = new scala.::(x, this)

[B >: A]라고 타입 파라미터를 정의해 두었기 때문에 :: 메서드는 상속관계를 갖는 클래스에 대해서 유연하게 활용될 수 있다.

abstract class Fruit
class Apple extends Fruit
class Orange extends Fruit

val apples = new Apple :: Nil
val fruits = new Orange :: apples

fruits         // List[Fruit] 타입, List(Orange@d2c53e, Apple@7361363f)
apples         // List[Apple] 타입, List(Apple@7361363f)
fruits.tail    // List[Fruit] 타입, List(Apple@7361363f)

::: 메서드도 이와 비슷하게 정의할 수 있다.

def :::[B >: A](prefix: List[B]): List[B] = {
  if(prefix.isEmpty) this
  else prefix.head :: prefix.tail ::: this
}

 

2. ListBuffer

어떤 리스트를 순회하면서 값을 바꾸는 함수가 있다고 해보자

def incremental(xs: List[Int]) = {
  var result = List[Int]()
  for(x <- xs) {
    result = result ::: List(x + 1)
  }
  result
}

incremental(List(1, 2, 3, 4)) // List(2, 3, 4, 5) 리턴

위의 함수는 결과는 의도대로 생성하지만 ::: 으로 리스트의 맨 뒤에 원소를 추가시킬경우 result가 그 길이만큼의 연산 비용이 들기 때문에 비효율적이다.

ListBuffer는 원소 추가, toList연산을 상수 시간에 할 수 있다.

def incremental(xs: List[Int]) = {
  val result = new ListBuffer[Int]
  for(x <- xs) {
    result.append(x + 1)
  }
  result.toList
}

incremental(List(1, 2, 3, 4)) // List(2, 3, 4, 5)

 

3. 실제 List 클래스

아래는 실제 List 클래스에 정의된 map메서드이다.

final override def map[B](f: A => B): List[B] = {
  if (this eq Nil) Nil else {
    val h = new ::[B](f(head), Nil)
    var t: ::[B] = h
    var rest = tail
    while (rest ne Nil) {
      val nx = new ::(f(rest.head), Nil)
      t.next = nx
      t = nx
      rest = rest.tail
    }
    h
  }
}

아래는 실제 $colon$colon.class 이다

package scala.collection.immutable
final case class ::[+A](override val head : A, private[scala] var next : scala.collection.immutable.List[A]) extends scala.collection.immutable.List[A] with scala.Product with scala.Serializable {
  override def headOption : scala.Some[A] = { /* compiled code */ }
  override def tail : scala.collection.immutable.List[A] = { /* compiled code */ }
}

next 변수가 var로 설정되어있고 scala 패키지 내부의 private 권한으로 설정되어있어 List 내부 함수인 map메서드에서 t.next 와 같은 형태로 접근이 가능하다. List의 map 메소드나 ListBuffer 의 toList메소드는 next에 직접 접근할 수 있는 특성을 이용해 구현되어 효율적이다.