Programming in Scala 스터디 정리 - 22장. 리스트 구현

Programming in Sala 책으로 스칼라 스터디하면서 정리했던 내용이다. 지금은 3판 번역본도 나왔지만, 약간 앞서서 스터디를 시작해서 2판으로 진행했다.

22장

리스트

package scala
abstract class List[+T]

• 리스트는 추상 클래스 : new List 불가능
• 리스트는 공변적(+T) : List[Int] 타입 값을 List[Any] 타입 변수에 할당 가능
• 리스트 연산은 세가지 기본 메소드(List 클래스의 추상 메소드)로 만들 수 있음
  • def isEmpty: Boolean
  • def head: T
  • def tail: List[T]

Nil 객체

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

:: 클래스

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

// 좀더 짧은 :: 클래스
final case class ::[T](val head: T, val tail: List[T]) excents List[T] {
  override def isEmpty: Boolean = false
}

추가 메소드

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[U](f: T => U): List[U] =
  if (isEmpty) Nil
  else f(head) :: tail.map(f)

리스트 구성 메소드

def ::[U >: T](x: U): List[U] = new scala.::(x, this)

• 원소 타입 T의 슈퍼 타입인 U가 타입 파라미터
• List 정의가 공변적이기 때문

def :::[U >: T](prefix: List[U]): List[U] =
  if (prefix.isEmpty) this
  else prefix.head :: prefix.tail ::: this

실제 List 클래스

// 효율을 위해서 루프 사용
final override def map[U](f: T => U): List[U] = {
  val b = new ListBuffer[U]
  var these = this
  while (!these.isEmpty) {
    b += f(these.head)
    these = these.tail
  }
  b.toList
}

final case class ::[T](hd: T, private[scala] var tl: List[T]) excents List[T] {
  def head = hd
  def tail = tl
  override def isEmpty: Boolean = false
}

package scala.collection.immutable
final class ListBuffer[T] extends Buffer[T] {
  private var start: List[T] = Nil
  private var last0: ::[T] = _
  private var exported: Boolean = false
  ...

  override def toList[T] = {
    exported = !start.isEmpty
    start
  }

  override def += (x: T) {
    if (exported) copy()
    if (start.isEmpty) {
      last0 = new scala.::(x, Nil)
      start = last0
    } else {
      val last1 = last0
      last0 = new scala.::(x, Nil)
      last1.tl = last0  // 콘즈의 tl이 var 인 이유
    }
  }
}