스칼라 22장 리스트 구현(Programming in Scala, 3rd)

22.1 List 클래스 개괄

: 리스트는 내장 언어 구성요소가 아니라 scala 패키지 안에 List라는 추상 클래스로 되어 있고 ::와 Nil 서브 클래스가 있다.

package scala abstract class List[+T]  ... {         def isEmpty: Boolean         def head: A         def tail: List[A]         .... }

: List는 추상 클래스 => new List X

: 공변성 => List[Int] 타입의 값을 List[Any] 같은 타입의 변수에 할당할 수 있다.

scala> val xs = List(1, 2, 3) xs: List[Int] = List(1, 2, 3) scala> var ys: List[Any] = xs ys: List[Any] = List(1, 2, 3)

스칼라 리스트의 클래스 계층구조

< Nil 객체 >

: 빈 리스트를 정의

: List[Nothing] 상속

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") }

 

< :: 클래스 >

: "::" 클래스는 콘즈라고 부르며 construct 약자이고 이름이 "::"인 이유는 중위 표기 "::"와 패턴 매치를 하기 위해서

: 스칼라는 중위 연산자에 대한 패턴 매치가 존재하지 않으며 중위 연산자를 그 중위 연산자에 각 인자들을 적용하는 생성자 호출로 다룬다. => "x::xs" 패턴은 "::(x,xs)"이다.

final case class ::[T](hd: T, tl: List[T]) extends List[T] {   def head = hd   def tail = tl   override def isEmpty: Boolean = false } => 케이스 클래스의 파라미터는 암시적으로 해당 클래스의 필드이다. final case class ::[T](head: T, tail: List[T])   extends List[T] {   override def isEmpty: Boolean = false }

 

< 리스트 구성 메소드 : "::", ":::" >

: ":"으로 끝나기 때문에 오른쪽 피연산자에 바인딩 => "x::xs" 는 "x.::(xs)"가 아니고 "xs.::(x)"와 같다.

" List 클래스의 :: 메소드 정의 " def ::[U >: T](x: U): List[U] = new scala.::(x, this)  // List는 공변적이기 때문에 하위 바운드를 사용   abstract class Fruit class Apple extends Fruit class Orange extends Fruit   scala> val apples = new Apple :: Nil apples: List[Apple] = List(Apple@585fa9) scala> val fruits = new Orange :: apples fruits: List[Fruit] = List(Orange@cd6798, Apple@585fa9)

위 예제의 스칼라 리스트 구조

" List 클래스의 ::: 메소드 정의 " def :::[U >: T](prefix: List[U]): List[U] =   if (prefix.isEmpty) this   else prefix.head :: prefix.tail ::: this

" 오른쪽으로 결합 " prefix.head :: prefix.tail ::: this prefix.head :: (prefix.tail ::: this) (prefix.tail ::: this).::(prefix.head) this.:::(prefix.tail).::(prefix.head)

 

22.2 ListBuffer 클래스

: 리스트에 대한 전형적인 접근 패턴은 재귀적

" 리스트 모든 원소를 map을 사용해 증가 " def incAll(xs: List[Int]): List[Int] = xs match {   case List() => List()   case x :: xs1 => x + 1 :: incAll(xs1) }

: incAll이 "::" 메소드 전에 호출되기 때문에 꼬리 재귀 X => 매번 새로운 스택 프레임 필요 => 30000~50000개보다 많은 원소를 가진 리스트에서 incAll 호출 불가 => 루프 사용

var result = List[Int]()    // a very inefficient approach for (x <- xs) result = result ::: List(x + 1) result

: ":::" 메소드는 첫 인자의 길이에 비례하는 시간이 필요하기 때문에 전체 연산이 리스트 길이의 제곱에 비례하는 시간 => 비효율적 => 리스트 버퍼 사용

import scala.collection.mutable.ListBuffer val buf = new ListBuffer[Int] for (x <- xs) buf += x + 1 buf.toList

: 리스트 버퍼는 추가 연산(+=)이나 toList연산을 상수 시간에 한다. => 효율적으로 리스트 생성

 

22.3 실제 List 클래스

: 비 꼬리 재귀 구현과 같은 스택 오버플로 문제가 존재하기 때문에 클래스 List는 실제로 구현하는 경우에는 대부분 재귀를 피하고 리스트 버퍼에 루프를 수행하는 방식을 택한다.

" 실제 map 구현 " 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 }

: 리스트 버퍼를 사용한 단순 루프로 매우 효율적, toList 메소드 호출 또한 리스트 길이와는 무관한 상수 시간이 걸린다.

 

* toList가 상수 시간이 걸리는 이유

" 실제 :: 클래스 " final case class ::[U](hd: U,                        private[scala] var tl: List[U]) extends List[U] {    // tl의 인자가 var, scala 패키지 안에서만 접근 가능   def head = hd   def tail = tl   override def isEmpty: Boolean = false }   " 실제 ListBuffer 클래스 " 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      // toList를 사용해 버퍼를 리스트로 바꾼 적이 있는지를 표시한다.     override def toList: List[T] = {   // ListBuffer에 저장된 리스트를 복사 X, but 반환한 리스트는 변경 불가능해야 돼 ListBuffer에 다른 값을 추가하면 start가 가리키는 리스트가 변한다.     exported = !start.isEmpty     start   }   override def += (x: T) {        // 새 원소를 추가하는 것은 해당 리스트의 last0의 tl 필드를 변경하는 것으로 구현     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     }   }

 

22.4 외부에서 볼 때는 함수형

: 리스트가 외부에서는 완전히 함수적이지만, 내부에서는 리스트 버퍼를 사용해 명령형으로 되어 있다.

 * 순수하지 않은 연산의 효과가 미치는 범위를 주의 깊게 제한함으로써 함수적 순수성을 효율적으로 달성한다.

=> 프로그램이 깨지기 쉽다는 단점을 해결, 추적하기 쉬워진다.

val ys = 1 :: xs val zs = 2 :: xs ys.drop(2).tail = Nil  // can't do this in Scala!

: ys와 zs에서 xs를 공유 => xs에 새로운 추가할 때마다 전체를 복사할 필요가 없음

: 변경이 허용될 경우 xs에 변경을 가할 때 부수효과로 ys와 zs도 변경

 

* "::"는 리스트 앞쪽에 원소를 하나씩 추가해나가거나 분할 정복 스타일의 재귀적 알고리즘에, 리스트 버퍼는 뒤에 원소를 더해나가거나 전통적인 루프 스타일에 많이 사용한다.