스칼라 25장 스칼라 컬렉션의 아키텍처(Programming in Scala, 3rd)

: 컬렉션 프레임워크의 주 설계 목표는 모든 연산을 가능한 한 적은 위치에 정의해서 중복을 피하는 것

=> 대부분의 컬렉션 연산을 컬렉션 템플릿에 정의해서 개별 기반 클래스나 구현을 필요에 따라 유연하게 상속할 수 있게 제공

 

25.1 빌더

: 거의 대부분의 컬렉션 연산이 빌더와 순회를 가지고 구현된다. 순회는 Traversable의 foreach 메소드를 통해 처리하며, 새 컬렉션 구축은 클래스 Builder의 인스턴스가 처리한다.

" Builder 클래스 개요 " package scala.collection.generic class Builder[-Elem, +To] {   def +=(elem: Elem): this.type   def result(): To   def clear()   def mapResult(f: To => NewTo): Builder[Elem, NewTo] = ... }

: b+=x 를 사용해 원소 x를 빌더 b에 넣을 수 있다.

: result() 메소드는 빌더에서 컬렉션을 반환한다. result() 호출 후 빌더 상태는 정의되어 있지 않다. clear()을 호출해 빈 상태에서 시작할 수 있다.

: 빌더는 원소 타입이 Elem이고 반환하는 컬렉션의 타입이 To인 제네릭 클래스

: mapResult() 메소드는 다른 빌더를 반환한다.

scala> val buf = new ArrayBuffer[Int]         // 빌더를 상속한 클래스로 배열 버퍼 자체가 빌더 buf: scala.collection.mutable.ArrayBuffer[Int] = ArrayBuffer() scala> val bldr = buf mapResult (_.toArray) // buf(빌더)의 result() => 배열 버퍼 반환 => _.toArray 적용해 배열 변환 => 배열 빌더 bldr: scala.collection.mutable.Builder[Int,Array[Int]] = ArrayBuffer()

 

25.2 공통 연산 한데 묶기

: 스칼라의 컬렉션은 동일 결과 타입 원칙을 따른다.

  * 가능하면 어떤 컬렉션에 대해 실행한 변환 코드의 결과는 같은 타입의 컬렉션이 된다.

Ex. List에 filter을 수행하면 List가 나오고, Map에 filter을 수행하면 Map이 나온다.

 

: 스칼라 컬렉션 라이브러리는 구현 트레이트라 불리는 제네릭 빌더와 순회를 사용해 코드 중복을 줄이고 동일 결과 타입 원칙을 달성한다. 이런 트레이트에는 Like 접미사가 붙는다.

Ex. IndexedSeqLike는 IndexedSeq의 구현 트레이트, Traversable의 구현 트레이트는 TraversableLike

: 컬렉션 클래스들은 모든 구체적인 메소드 구현을 구현 트레이트로부터 상속

: 구현 트레이트는 타입 파라미터로 원소의 타입과 컬렉션이 표현하는 타입(List, Seq)을 지정한다.

package scala.collection class TraversableLike[+Elem, +Repr] {   def newBuilder: Builder[Elem, Repr] // deferred   def foreach[U](f: Elem => U)        // deferred   ...   def filter(p: Elem => Boolean): Repr = {     val b = newBuilder     foreach { elem => if (p(elem)) b += elem }     b.result   } }

: Repr은 Traversable의 서브 타입이 아닌 타입이 가능 => String이나 Array처럼 컬렉션 계층 구조에 없는 클래스도 컬렉션 구현 트레이트가 정의하는 모든 연산 사용 가능

: TraversableLike 트레이트는 newBuilder, foreach 추상 멤버가 존재하고 구체적인 컬렉션 클래스에서 정의한다. filter의 구현은 newBuilder와 foreach 추상 메소드를 사용하며 모든 컬렉션에 대해 동일하다. => newBuilder와 foreach만 구현하면 모든 컬렉션에 대해 filter을 사용할 수 있다.

: filter => newBuilder을 사용해 Elem 원소를 담고 Repr 컬렉션에 대한 빌더 생성 => 현재 컬렉션의 모든 원소를 foreach를 사용해 방문 => 원소 x가 술어를 만족하면 빌더에 추가 => 빌더의 result를 호출해 빌더에서 모은 원소들을 Repr 컬렉션 타입의 인스턴스로 반환

 

: map 연산의 경우 Array[String]이 Array[Int]로 원소의 타입이 변경되기 때문에 newBuilder와 foreach로 충분하지 않다.

=> newBuilder은 원래의 컬렉션과 같은 타입의 인스턴스만 만든다. map의 결과 타입에 따라 일일이 메소드를 정의하는 것도 힘들다. 결과 타입은 map에 들어가는 함수 타입에 의존적이다.

scala> import collection.immutable.BitSet import collection.immutable.BitSet scala> val bits = BitSet(1, 2, 3) bits: scala.collection.immutable.BitSet = BitSet(1, 2, 3) scala> bits map (_ * 2) res13: scala.collection.immutable.BitSet = BitSet(2, 4, 6) scala> bits map (_.toFloat) res14: scala.collection.immutable.Set[Float] = Set(1.0, 2.0, 3.0) scala> Map("a" -> 1, "b" -> 2) map { case (x, y) => (y, x) } res3: scala.collection.immutable.Map[Int,java.lang.String] = Map(1 -> a, 2 -> b) scala> Map("a" -> 1, "b" -> 2) map { case (x, y) => y } res4: scala.collection.immutable.Iterable[Int] = List(1, 2)

: map을 제한해서 항상 같은 종류의 컬렉션을 반환하게 만들 수 있다. 하지만 제약을 가하면 리스코프 치환 법칙을 어겨 올바르지 않다.

Ex. Map은 Iterable이기도 하므로 Iterable에서 할 수 있는 일은 Map에서도 할 수 있어야 한다.

* 리스코프 치환 원칙 : U 타입의 값이 필요한 모든 경우를 T 타입의 값으로 대치할 수 있다면 T 타입을 U 타입의 서브타입으로 가정해도 안전하다.

=> 스칼라는 암시적 파라미터를 통한 오버로드를 사용해 문제를 해결

" TraversableLike의 map 구현 " def map[B, That](p: Elem => B)                 (implicit bf: CanBuildFrom[Repr, B, That]): That = {   // ConBuildFrom 타입의 빌더 팩토리   val b = bf(this)   for (x <- this) b += f(x)   b.result }   " CanBuildFrom 트레이트 " package scala.collection.generic trait CanBuildFrom[-From, -Elem, +To] {   def apply(from: From): Builder[Elem, To]       // 새로운 빌더를 만든다. } : From 타입의 컬렉션을 받아서 Elem 타입의 원소를 갖는 컬렉션 To를 반환하는 빌더 생성 => CanBuildFrom의 암시적 정의를 제대로 하면 map의 타입 변환을 필요에 따라 변경할 수 있다.

Ex. BitSet

: BitSet의 동반 객체에는 CanBuildFrom[BitSet, Int, BitSet]이 있다. BitSet에 대해 map 연산을 적용할 때 만들려는 결과 컬렉션의 원소 타입이 Int인 새 BitSet을 만들 수 있다. => 이를 만족시킬 수 없다면 다른 암시적 빌드 팩토리 시도 => 더 일반적인 mutable.Set의 동반 객체에 있는 CanBuildFrom[Set[_], A, Set[A]] 적용한다. A의 타입과 관계없이 다시 Set을 만들 수 있다.

: 가장 적당하면서 최대한 상세한 빌더를 찾는다.

 

scala> val xs: Iterable[Int] = List(1, 2, 3) xs: Iterable[Int] = List(1, 2, 3)       // 정적 타입은 Iterable, 동적 타입은 List scala> val ys = xs map (x => x * x) ys: Iterable[Int] = List(1, 4, 9)     // map 결과 타입이 동적 타입에 매칭

: CanBuildFrom의 apply 메소드가 원래 컬렉션의 인자로 넘어가고 apply 호출을 genericBuilder에 있는 메소드에 넘긴다. genericBuilder 메소드는 실제 그 메소드가 정의된 컬렉션의 빌더를 호출한다.

=> 스칼라는 정적인 암시 파라미터 해결을 사용해 맵의 타입에 대한 제약을 해결하고 가상 디스패치를 사용해 이런 제약을 만족하는 가장 좋은 동적인 타입을 가져온다.

 

25.3 새 컬렉션 통합

: 새로운 컬렉션 클래스를 만들면서 기존에 정의된 컬렉션 연산이 새 타입 위에 잘 동작하도록 통합하는 예

< RNA 가닥을 표현하는 시퀀스 타입 >

: RNA 가닥은 A, T, G, U 염기의 시퀀스

" RNA 염기들 " abstract class Base case object A extends Base case object T extends Base case object G extends Base case object U extends Base object Base {   val fromInt: Int => Base = Array(A, T, G, U)              // 정수를 Base 값으로 바꾸는 배열   val toInt: Base => Int = Map(A -> 0, T -> 1, G -> 2, U -> 3)   // Base 값을 정수로 바꾸는 맵 }

: RNA 가닥은 단지 Seq[Base] 이지만 네 가지 염기밖에 없기 때문에 2비트만을 사용해 염기를 구별 => 정수에는 2비트 값인 염기를 16개 저장 => Seq[Base]에 특화된 서브 클래스를 만들어 압축한 내부 표현 사용

import collection.IndexedSeqLike import collection.mutable.{Builder, ArrayBuffer} import collection.generic.CanBuildFrom final class RNA1 private (val groups: Array[Int],       // 비트로 압축된 RNA 정보                           val length: Int) extends IndexedSeq[Base] {                         // length : 배열 안의 염기 개수, IndexedSeq에는 length, apply 추상 메소드 존재   import RNA1._   def apply(idx: Int): Base = {             // 인덱스의 염기 반환     if (idx < 0 || length <= idx)       throw new IndexOutOfBoundsException     Base.fromInt(groups(idx / N) >> (idx % N * S) & M)              } } object RNA1 {   private val S = 2        // 염기를 표현하는 비트 수   private val N = 32 / S         // Int(32 bit)에 들어갈 그룹의 수   private val M = (1 << S) - 1       // 어떤 그룹만 떼어내기 위한 비트 마스크(11)   def fromSeq(buf: Seq[Base]): RNA1 = {     val groups = new Array[Int]((buf.length + N - 1) / N)        for (i <- 0 until buf.length)       groups(i / N) |= Base.toInt(buf(i)) << (i % N * S)     new RNA1(groups, buf.length)   }   def apply(bases: Base*) = fromSeq(bases) }

: 생성자 비공개 => 클라이언트가 RNA 시퀀스의 내부 표현을 볼 수 없다. => 클라이언트 코드에는 영향을 주지 않으면서 표현을 바꿀 수 있다. => 동반 객체를 활용해 팩토리 메소드 제공

scala> val xs = List(A, G, T, A) xs: List[Product with Base] = List(A, G, T, A) scala> RNA1.fromSeq(xs) res1: RNA1 = RNA1(A, G, T, A) scala> val rna1 = RNA1(A, U, G, G, T) rna1: RNA1 = RNA1(A, U, G, G, T)

< RNA 메소드의 결과 타입 변환 >

scala> rna1.length res2: Int = 5 scala> rna1.last res3: Base = T scala> rna1.take(3) res4: IndexedSeq[Base] = Vector(A, U, G) : IndexedSeq에 IndexedSeq를 반환하는 take 메소드가 있고 IndexedSeq 구현이 Vector => RNA1 X => RNA1 클래스의 take 메소드 오버라이드 def take(count: Int) : RNA1 = RNA1.fromSeq(super.take(count)) => drop, filter과 같은 컬렉션 메소드도 똑같이 하기는 힘들다. => IndexedSeq의 구현 클래스인 IndexedSeqLike를 상속한다.

 

final class RNA2 private (                            val groups: Array[Int],                            val length: Int                          ) extends IndexedSeq[Base] with IndexedSeqLike[Base, RNA2] {   import RNA2._   override def newBuilder: Builder[Base, RNA2] =     new ArrayBuffer[Base] mapResult fromSeq   def apply(idx: Int): Base = // RNA1과 같다. }

: take, drop, filter 등의 반환 타입은 IndexedSeqLike의 두 번째 타입 파라미터다. 이를 위해 IndexedSeqLike는 newBuilder라는 추상 메소드에 의존한다.

: IndexedSeqLike 트레이트의 서브 클래스들은 newBuilder를 오버라이드해서 자기가 원하는 컬렉션을 반환하게 해야 한다.

=> RNA2 클래스에서 newBuilder 메소드는 Builder[Base, RNA2] 타입의 빌더를 반환한다.

=> Builder[Base, ArrayBuffer] 인 ArrayBuffer을 mapResult 메소드를 호출해 RNA2 빌더를 만드는 데 ArrayBuffer=>RNA2 함수를 파라미터로 전달해 기존 ArrayBuffer을 RNA2 빌더로 변환한다.

scala> val rna2 = RNA2(A, U, G, G, T) rna2: RNA2 = RNA2(A, U, G, G, T) scala> rna2 take 3 res5: RNA2 = RNA2(A, U, G) scala> rna2 filter (U !=) res6: RNA2 = RNA2(A, G, G, T)

 

< map과 친구들 다루기 >

: map은 같은 종류의 컬렉션을 반환하지만 원소 타입이 바뀔 수 있다.(Seq[Int] => Seq[String]) => 원소 타입이 바뀌더라도 컬렉션 종류는 그대로다.

scala> val rna2 = RNA2(A, U, G, G, T) rna2: RNA2 = RNA2(A, U, G, G, T) scala> rna2 map { case A => T case b => b } res0: IndexedSeq[Base] = Vector(T, U, G, G, T) scala> rna2 ++ rna2 res1: IndexedSeq[Base] = Vector(A, U, G, G, T, A, U, G, G, T) : 모두 RNA2 타입이 아니라 IndexedSeq 타입이다.

def map[B, That](f: Elem => B)       (implicit cbf: CanBuildFrom[Repr, B, That]): That

: Elem은 컬렉션의 원소 타입이며 Repr은 컬렉션 자체의 타입(TraversableLike나 IndexedSeqLike 같은 구현 클래스에 들어가는 타입 파라미터)

: B는 매핑 함수의 결과 타입인 동시에 결과 컬렉션의 원소 타입

: That은 새로 만들어질 컬렉션의 타입

: 컴파일러는 That과 B의 타입을 암시적 파라미터 cbf에 의해 결정

: cbf의 타입은 CanBuildFrom[Repr, B, That]으로 From 타입의 컬렉션을 받아서 Elem 타입의 원소를 갖는 컬렉션 To를 만드는 방법이 있다고 알린다.

=> ++나 map이 동작할 때 RNA2를 만드는 CanBuildFrom 인스턴스가 없기 때문에 부모 트레이트인 IndexedSeq 동반 객체에서 암시적 파라미터를 찾았다.

=> CanBuildFrom[RNA, Base, RNA] 타입의 인스턴스를 정의

" 최종 RNA 클래스 " final class RNA private (val groups: Array[Int], val length: Int)   extends IndexedSeq[Base] with IndexedSeqLike[Base, RNA] {   import RNA._   override protected[this] def newBuilder: Builder[Base, RNA] =  // newBuilder의 구현을 동반 객체로 옮김     RNA.newBuilder   def apply(idx: Int): Base = {     if (idx < 0 || length <= idx)       throw new IndexOutOfBoundsException     Base.fromInt(groups(idx / N) >> (idx % N * S) & M)   }   override def foreach[U](f: Base => U): Unit = {     var i = 0     var b = 0     while (i < length) {       b = if (i % N == 0) groups(i / N) else b >>> S       f(Base.fromInt(b & M))       i += 1     }   } } object RNA {   private val S = 2            private val M = (1 << S) - 1   private val N = 32 / S      def fromSeq(buf: Seq[Base]): RNA = {     val groups = new Array[Int]((buf.length + N - 1) / N)     for (i <- 0 until buf.length)       groups(i / N) |= Base.toInt(buf(i)) << (i % N * S)     new RNA(groups, buf.length)   }   def apply(bases: Base*) = fromSeq(bases)   def newBuilder: Builder[Base, RNA] =     new ArrayBuffer mapResult fromSeq   implicit def canBuildFrom: CanBuildFrom[RNA, Base, RNA] =      // CanBuildFrom 타입 암시 값 정의     new CanBuildFrom[RNA, Base, RNA] {       def apply(): Builder[Base, RNA] = newBuilder       def apply(from: RNA): Builder[Base, RNA] = newBuilder     } }

: CanBuildFrom은 두 가지 메소드를 정의해야 한다.

1. apply() : 반환할 빌더 타입을 만들기만 한다.

2. apply(from) : 원래의 컬렉션을 인자로 받아 반환하는 컬렉션 타입을 인자로 받은 컬렉션 타입과 같게 만든다.

   * RNA의 경우 final이기 때문에 정적인 타입이 RNA이면 동적인 타입도 RNA => 기능이 쓰일 여지가 없다.

 

=> 코드의 양을 조금만 추가하면 컬렉션에서 제공하는 연산을 사용할 수 있다

=> 효율을 위해 기존 메소드를 오버라이드하거나 시퀀스에 새로운 기능을 추가하고 싶을 때가 있다.

* 위 코드의 foreach 메소드 : foreach 메소드는 컬렉션에 대한 루프를 구현하기에 다른 컬렉션 메소드들이 foreach를 기반해 만들어 졌다. => foreach 구현을 최적화

: IndexedSeq의 표준 foreach 구현은 단지 컬렉션에 apply를 호출에 0부터 컬렉션의 length-1까지 모든 i번째 원소를 가져온다. => RNA는 모든 배열에서 한 번에 순회한다.

 

< 새로운 집합과 맵의 통합 : 패트리샤 트라이 >

- 집합이나 맵을 트리로 구성하되 검색 키의 각 문자가 유일한 자식 트리를 구성하게 만드는 것

Ex. "abc", "abd", "al", "all", "xy" 문자열을 포함한 패트리샤 트라이 : "abc" 문자열을 찾으려면 "a" => "b" => "c" 서브트리를 찾는다.

: 패트시랴 트라이는 어떤 접두사를 포함하는 하위 컬렉션을 쉽게 선택할 수 있어야 한다.

Ex. 트리에서 "a"로 시작하는 모든 하위 컬렉션을 찾으려면 단지 트리 루트에서 "a"를 따라 링크를 하나 내려가기만 하면 된다.

scala> val m = PrefixMap("abc" -> 0, "abd" -> 1, "al" -> 2,  "all" -> 3, "xy" -> 4)   m: PrefixMap[Int] = Map((abc,0), (abd,1), (al,2), (all,3), (xy,4))   scala> m withPrefix "a"            // "a"로 시작하는 접두사 맵 획득   res14: PrefixMap[Int] = Map((bc,0), (bd,1), (l,2), (ll,3))

 

" 패트리샤 트라이를 사용한 접두사 맵 구현 " import collection._ class PrefixMap[T]  extends mutable.Map[String, T]  with mutable.MapLike[String, T, PrefixMap[T]] {         // MapLike 구현 클래스 상속을 통해 filter 같은 메소드에서 올바른 타입의 결과를 얻고 쉽게 컬렉션 메소드를 사용할 수 있다.     var suffixes: immutable.Map[Char, PrefixMap[T]] = Map.empty    // 문자에 해당하는 PrefixMap 값을 보내는 맵   var value: Option[T] = None      // 해당 노드와 관련된 Option 값   def get(s: String): Option[T] =              // s키를 가진 노드의 value 리턴     if (s.isEmpty) value     else suffixes get (s(0)) flatMap (_.get(s substring 1))   def withPrefix(s: String): PrefixMap[T] =      // 접두사 s로 시작하는 모든 하위 컬렉션 리턴     if (s.isEmpty) this     else {       val leading = s(0)       suffixes get leading match {         case None =>           suffixes = suffixes + (leading -> empty)         case _ =>       }       suffixes(leading) withPrefix (s substring 1)     }   override def update(s: String, elem: T) =      // += 메소드     withPrefix(s).value = Some(elem)   override def remove(s: String): Option[T] =       // -= 메소드      if (s.isEmpty) { val prev = value; value = None; prev }     else suffixes get (s(0)) flatMap (_.remove(s substring 1))   def iterator: Iterator[(String, T)] =     (for (v <- value.iterator) yield ("", v)) ++     (for ((chr, m) <- suffixes.iterator;            (s, v) <- m.iterator) yield (chr +: s, v))        def += (kv: (String, T)): this.type = { update(kv._1, kv._2); this }   def -= (s: String): this.type  = { remove(s); this }   override def empty = new PrefixMap[T] }

" 접두사 맵의 동반 객체 " import scala.collection.mutable.{Builder, MapBuilder} import scala.collection.generic.CanBuildFrom object PrefixMap extends {   def empty[T] = new PrefixMap[T]     // 빈 PrefixMap 객체 반환 // 변경 불가능한 맵이나 집합은 비파괴적 원소 추가 메소드인 +를 사용하기 때문에 어떤 집합이나 맵을 만들려면 원하는 타입의 빈 집합이나 빈 맵을 만들어야 한다.   def apply[T](kvs: (String, T)*): PrefixMap[T] = {         val m: PrefixMap[T] = empty     for (kv <- kvs) m += kv     m   }   def newBuilder[T]: Builder[(String, T), PrefixMap[T]] =      new MapBuilder[String, T, PrefixMap[T]](empty)   implicit def canBuildFrom[T]     : CanBuildFrom[PrefixMap[_], (String, T), PrefixMap[T]] =        new CanBuildFrom[PrefixMap[_], (String, T), PrefixMap[T]] {         def apply(from: PrefixMap[_]) = newBuilder[T]         def apply() = newBuilder[T]       } }

 

< 정리 > : 새 컬렉션 클래스를 프레임워크에 완전히 통합하고 싶다면 다음과 같은 점에 주의

1. 컬렉션을 변경 가능하게 할지 여부를 결정해야 한다.

2. 기반 트레이트를 제대로 선택해야 한다.

3. 대부분의 컬렉션 연산을 구현하기 위해 구현 트레이트를 제대로 선택해야 한다.

4. map이나 그와 비슷한 연산을 사용해 컬렉션 타입의 인스턴스를 반환해야 한다면 암시적인 CanBuildFrom을 동반 객체에 제공해야 한다.

 

 

* 문제를 어떻게 정의 => 코드를 어떤 생각으로 짯는 가, 그대로 구현 되어 있는가 

* 용어를 내 말로 어떻게 정리할 것인가????