Scala 2.8 컬렉션 디자인 튜토리얼

Scala 2.8 컬렉션 디자인 튜토리얼

---

숨막히는 혼란 에 이어 새로운 Scala 2.8 컬렉션 라이브러리가 어떻게 구성되었는지 설명하는 좋은 리소스는 무엇입니까 ? 다음 항목이 어떻게 결합되는지에 대한 정보를 찾고 싶습니다.

• 컬렉션 클래스 / 특성 자체 (예 : List, Iterable)
• 왜 ' 같이의 클래스가 존재한다 (예를 들어 TraversableLike)
• 동반자 방법에 대해 무엇 (예 List.companion)
• implicit주어진 지점에서 어떤 객체가 범위 내에 있는지 어떻게 알 수 있습니까?

---

머리말

Martin Odersky 의 2.8 컬렉션 워크 스루 가 아마도 첫 번째 참조가 될 것입니다. 또한 자신의 컬렉션을 디자인하려는 사람들에게 특히 흥미로울 건축 노트 로 보완되었습니다 .

이 답변의 나머지 부분은 그러한 것이 존재하기 전에 작성되었습니다 (사실 2.8.0 자체가 출시되기 전에).

Scala SID # 3 으로 이에 대한 논문을 찾을 수 있습니다 . 해당 분야의 다른 논문도 Scala 2.7과 2.8의 차이점에 관심이있는 사람들에게 흥미로울 것입니다.

나는 논문을 선별 적으로 인용하고 내 생각을 보완 할 것이다. decodified.com에서 Matthias가 생성 한 일부 이미지도 있으며 원본 SVG 파일은 여기 에서 찾을 수 있습니다 .

컬렉션 클래스 / 특성 자체

실제로 컬렉션에는 세 가지 특성 계층이 있습니다. 하나는 변경 가능한 컬렉션, 다른 하나는 변경 불가능한 컬렉션, 다른 하나는 컬렉션에 대해 가정하지 않습니다.

또한 Scala 2.9에 도입 된 병렬, 직렬 및 어쩌면 병렬 컬렉션 사이에 차이가 있습니다. 다음 섹션에서 이에 대해 이야기하겠습니다. 이 섹션에서 설명하는 계층 구조는 비 병렬 컬렉션에만 적용됩니다 .

다음 이미지는 Scala 2.8에 도입 된 비 특정 계층 구조를 보여줍니다.

표시된 모든 요소는 특성입니다. 다른 두 계층 구조에는 래퍼 클래스로의 암시 적 변환을 통해 해당 계층 구조에 속하는 것으로 볼 수있는 클래스뿐만 아니라 트레이 트를 직접 상속하는 클래스도 있습니다. 이 그래프의 범례는 그 뒤에 있습니다.

불변 계층에 대한 그래프 :

가변 계층에 대한 그래프 :

전설:

다음은 이미지를 볼 수없는 사용자를 위해 컬렉션 계층 구조의 ASCII 축약 형 묘사입니다.

                    Traversable
                         |
                         |
                      Iterable
                         |
      +------------------+--------------------+
     Map                Set                  Seq
      |                  |                    |
      |             +----+----+         +-----+------+
    Sorted Map  SortedSet   BitSet   Buffer Vector LinearSeq

병렬 컬렉션

Scala 2.9가 병렬 컬렉션을 도입했을 때 디자인 목표 중 하나는 최대한 원활하게 사용하는 것이 었습니다. 가장 간단한 용어로, 병렬이 아닌 (직렬) 컬렉션을 병렬 컬렉션으로 대체하고 즉시 이점을 얻을 수 있습니다.

그때까지 모든 컬렉션 시리얼 있었다 때문에,이를 이용하여 많은 알고리즘을 가정하고이 사실에 의존 했다 시리얼. 이러한 가정이있는 메서드에 제공되는 병렬 컬렉션은 실패합니다. 이러한 이유로 이전 섹션에서 설명한 모든 계층 구조는 직렬 처리를 요구합니다 .

병렬 컬렉션을 지원하기 위해 두 개의 새로운 계층이 생성되었습니다.

병렬 컬렉션 계층 구조 특성에 대해 동일한 이름을 가지고 있지만, 앞에는 Par: ParIterable, ParSeq, ParMap와 ParSet. ParTraversable병렬 액세스를 지원하는 컬렉션은 더 강력한 ParIterable특성 을 지원할 수 있으므로 는 없습니다 . 직렬 계층 구조에 더 전문화 된 특성 중 일부도 없습니다. 이 전체 계층 구조는 디렉토리 아래에 scala.collection.parallel있습니다.

병렬 컬렉션 클래스를 구현하여도, 상이 ParHashMap하고 ParHashSet모두 가변 및 불변 병렬 콜렉션 플러스 ParRange및 ParVector구현 immutable.ParSeq및 ParArray실행 mutable.ParSeq.

또 다른 계층은 또한 거울을 직렬 및 병렬 컬렉션의 특성을 존재하지만 접두사로 Gen: GenTraversable, GenIterable, GenSeq, GenMap와 GenSet. 이러한 특성은 병렬 및 직렬 컬렉션의 부모 입니다. 즉, a를 취하는 메서드 Seq는 병렬 컬렉션을받을 수 없지만 a를받는 메서드 GenSeq는 직렬 및 병렬 컬렉션 모두에서 작동 할 것으로 예상됩니다.

이러한 계층 구조가 구조화 된 방식을 고려할 때 Scala 2.8 용으로 작성된 코드는 Scala 2.9와 완전히 호환되며 직렬 동작이 필요했습니다. 다시 작성하지 않으면 병렬 컬렉션을 활용할 수 없지만 필요한 변경 사항은 매우 적습니다.

병렬 컬렉션 사용

모든 컬렉션은 메서드 par를 호출하여 병렬 컬렉션으로 변환 할 수 있습니다 . 마찬가지로 모든 컬렉션은 메서드 seq를 호출하여 직렬 컬렉션으로 변환 할 수 있습니다 .

컬렉션이 이미 요청 된 유형 (병렬 또는 직렬)이면 변환이 발생하지 않습니다. 그러나 seq병렬 컬렉션이나 par직렬 컬렉션을 호출 하면 요청 된 특성을 가진 새 컬렉션이 생성됩니다.

seq컬렉션을 비 병렬 컬렉션으로 바꾸는를 컬렉션 의 요소에서 생성 toSeq된를 반환 하는와 혼동하지 마십시오 Seq. toSeq병렬 컬렉션을 호출 ParSeq하면 직렬 컬렉션이 아닌 을 반환합니다 .

주요 특성

많은 구현 클래스와 하위 특성이 있지만 계층 구조에는 몇 가지 기본 특성이 있습니다. 각 특성은 더 많은 메서드 또는보다 구체적인 보증을 제공하지만이를 구현할 수있는 클래스 수를 줄입니다.

다음 하위 섹션에서는 주요 특성과 그 뒤에 숨은 아이디어에 대해 간략하게 설명합니다.

TraversableOnce 특성

이 특성은 Traversable아래에 설명 된 특성과 거의 비슷 하지만 한 번만 사용할 수 있다는 제한이 있습니다 . 즉,에서 호출 된 모든 메서드는 사용할 수 없게 TraversableOnce 될 수 있습니다.

이러한 제한으로 인해 컬렉션과 Iterator. 이를 통해 특정 메서드 와 함께 작동 Iterator하지만 사용하지 않는 Iterator메서드가 실제로 모든 컬렉션과 함께 작동 할 수 있으며, accept하도록 다시 작성되면 반복기를 사용할 수 TraversableOnce있습니다.

TraversableOnce컬렉션과 반복자를 통합 하기 때문에 컬렉션에만 관련된 이전 그래프에는 나타나지 않습니다.

순회 가능한 특성

컬렉션 계층 구조 의 맨 위에는 특성이 Traversable있습니다. 그것의 유일한 추상적 인 연산은

def foreach[U](f: Elem => U)

이 작업은 컬렉션의 모든 요소를 ​​순회하고 주어진 작업 f를 각 요소에 적용하는 것을 의미합니다. 응용 프로그램은 부작용에 대해서만 수행됩니다. 사실 f의 모든 함수 결과는 foreach에 의해 버려집니다.

순회 가능한 객체는 유한하거나 무한 할 수 있습니다. 무한 순회 가능한 객체의 예는 자연수의 흐름입니다 Stream.from(0). 이 메서드 hasDefiniteSize는 컬렉션이 무한한지 여부를 나타냅니다. 경우 hasDefiniteSizetrue를 반환 컬렉션은 확실히 유한하다. false를 반환하면 컬렉션이 아직 완전히 정교화되지 않았으므로 무한하거나 유한 할 수 있습니다.

이 클래스는 foreach(그중 40 개 이상) 효율적으로 구현할 수있는 메서드를 정의합니다 .

반복 가능한 특성

이 특성은 iterator컬렉션의 모든 요소를 ​​하나씩 생성하는 반복자를 반환 하는 추상 메서드 를 선언합니다 . 의 foreach메서드 Iterable는 iterator. 의 서브 클래스는 Iterable종종 효율성을 위해 직접 구현으로 foreach를 재정의합니다.

Class Iterable는 또한 덜 자주 사용되는 메서드를에 추가합니다.이 메서드 는 사용 가능한 Traversable경우에만 효율적으로 구현할 iterator수 있습니다. 아래에 요약되어 있습니다.

xs.iterator          An iterator that yields every element in xs, in the same order as foreach traverses elements.
xs takeRight n       A collection consisting of the last n elements of xs (or, some arbitrary n elements, if no order is defined).
xs dropRight n       The rest of the collection except xs takeRight n.
xs sameElements ys   A test whether xs and ys contain the same elements in the same order

기타 특성

후 Iterable거기에서 상속 세 가지 기본 특성을 제공 : Seq, Set,와 Map. 세 가지 apply모두 방법이 있고 세 가지 모두 PartialFunction특성을 구현 하지만 그 의미는 apply각 경우에 다릅니다.

나는의 의미를 신뢰 Seq, Set그리고 Map직관적이다. 그 후에 클래스는 성능과 관련하여 특정 보장을 제공하는 특정 구현과 그 결과로 사용할 수있는 메서드로 나뉩니다. 또한 가능 등의 추가 개선, 일부 특성은 LinearSeq, IndexedSeq과 SortedSet.

아래 목록이 개선 될 수 있습니다. 제안 사항과 함께 댓글을 남겨 주시면 수정하겠습니다.

기본 클래스 및 특성

• Traversable-기본 컬렉션 클래스. 으로 만 구현할 수 있습니다 foreach.
  • TraversableProxy- Traversable. self실제 컬렉션을 가리 킵니다 .
  • TraversableView -일부 엄격하지 않은 메소드가있는 Traversable.
  • TraversableForwarder-에 전달합니다 대부분의 방법 underlying제외시켰다 toString, hashCode, equals, stringPrefix, newBuilder, view와 같은 종류의 새로운 반복 가능한 객체를 생성하는 모든 호출.
  • mutable.Traversable및 immutable.Traversable-와 동일 Traversable하지만 컬렉션 유형을 제한합니다.
  • Iterable과 같은 다른 특수한 경우 클래스 MetaData가 있습니다.
  • Iterable-을 Iterator(를 iterator) 통해 만들 수있는 컬렉션입니다 .
    • IterableProxy, IterableView, mutable와 immutable.Iterable.
• Iterator-의 후손이 아닌 특성 Traversable. 정의 next및 hasNext.
  • CountedIterator- 지금까지 본 요소를 반환 하는 Iterator정의 count.
  • BufferedIterator- head소비하지 않고 다음 요소를 반환 하는를 정의합니다 .
  • Iterator과 같은 다른 특수한 경우 클래스 Source가 있습니다.

지도

• Map- Iterable의 Tuple2또 키 (튜플의 첫 번째 요소)를 소정 값 (튜플의 두 번째 요소)를 검색하는 방법을 제공한다. 확장 PartialFunction합니다.
  • MapProxy- ProxyA에 대한 Map.
  • DefaultMap- Map의 추상 방법 중 일부를 구현하는 특성 .
  • SortedMap- Map키가 정렬 된 A.
    • immutable.SortMap
      • immutable.TreeMap- immutable.SortedMap.
  • immutable.Map
    • immutable.MapProxy
    • immutable.HashMap- immutable.Map키 해싱을 통해 구현하는 클래스 .
    • immutable.IntMap- 키에 immutable.Map특화된 클래스를 구현 Int합니다. 키의 이진수를 기반으로 트리를 사용합니다.
    • immutable.ListMap- immutable.Map목록을 통해 구현하는 클래스 .
    • immutable.LongMap- 키에 immutable.Map특화된 클래스를 구현 Long합니다. 을 참조하십시오 IntMap.
    • 특정 요소 수에 최적화 된 추가 클래스가 있습니다.
  • mutable.Map
    • mutable.HashMap- mutable.Map키 해싱을 통해 구현하는 클래스 .
    • mutable.ImmutableMapAdaptor- mutable.Map기존 immutable.Map.
    • mutable.LinkedHashMap -?
    • mutable.ListMap- mutable.Map목록을 통해 구현하는 클래스 .
    • mutable.MultiMap -각 키에 대해 둘 이상의 고유 한 값을 허용하는 클래스.
    • mutable.ObservableMap- 와 혼합 될 때 인터페이스를 통해 관찰자에게 이벤트를 게시 하는 mixin .MapPublisher
    • mutable.OpenHashMap -개방형 해싱 알고리즘을 기반으로하는 클래스.
    • mutable.SynchronizedMap -- A mixin which should be mixed with a Map to provide a version of it with synchronized methods.
    • mutable.MapProxy.

The Sequences

• Seq -- A sequence of elements. One assumes a well-defined size and element repetition. Extends PartialFunction as well.
  • IndexedSeq -- Sequences that support O(1) element access and O(1) length computation.
    • IndexedSeqView
    • immutable.PagedSeq -- An implementation of IndexedSeq where the elements are produced on-demand by a function passed through the constructor.
    • immutable.IndexedSeq
      • immutable.Range -- A delimited sequence of integers, closed on the lower end, open on the high end, and with a step.
        • immutable.Range.Inclusive -- A Range closed on the high end as well.
        • immutable.Range.ByOne -- A Range whose step is 1.
      • immutable.NumericRange -- A more generic version of Range which works with any Integral.
        • immutable.NumericRange.Inclusive, immutable.NumericRange.Exclusive.
        • immutable.WrappedString, immutable.RichString -- Wrappers which enables seeing a String as a Seq[Char], while still preserving the String methods. I'm not sure what the difference between them is.
    • mutable.IndexedSeq
      • mutable.GenericArray -- An Seq-based array-like structure. Note that the "class" Array is Java's Array, which is more of a memory storage method than a class.
      • mutable.ResizableArray -- Internal class used by classes based on resizable arrays.
      • mutable.PriorityQueue, mutable.SynchronizedPriorityQueue -- Classes implementing prioritized queues -- queues where the elements are dequeued according to an Ordering first, and order of queueing last.
      • mutable.PriorityQueueProxy -- an abstract Proxy for a PriorityQueue.
  • LinearSeq -- A trait for linear sequences, with efficient time for isEmpty, head and tail.
    • immutable.LinearSeq
      • immutable.List -- An immutable, singlely-linked, list implementation.
      • immutable.Stream -- A lazy-list. Its elements are only computed on-demand, but memoized (kept in memory) afterwards. It can be theoretically infinite.
    • mutable.LinearSeq
      • mutable.DoublyLinkedList -- A list with mutable prev, head (elem) and tail (next).
      • mutable.LinkedList -- A list with mutable head (elem) and tail (next).
      • mutable.MutableList -- A class used internally to implement classes based on mutable lists.
        • mutable.Queue, mutable.QueueProxy -- A data structure optimized for FIFO (First-In, First-Out) operations.
        • mutable.QueueProxy -- A Proxy for a mutable.Queue.
  • SeqProxy, SeqView, SeqForwarder
  • immutable.Seq
    • immutable.Queue -- A class implementing a FIFO-optimized (First-In, First-Out) data structure. There is no common superclass of both mutable and immutable queues.
    • immutable.Stack -- A class implementing a LIFO-optimized (Last-In, First-Out) data structure. There is no common superclass of both mutable immutable stacks.
    • immutable.Vector -- ?
    • scala.xml.NodeSeq -- A specialized XML class which extends immutable.Seq.
    • immutable.IndexedSeq -- As seen above.
    • immutable.LinearSeq -- As seen above.
  • mutable.ArrayStack -- A class implementing a LIFO-optimized data structure using arrays. Supposedly significantly faster than a normal stack.
  • mutable.Stack, mutable.SynchronizedStack -- Classes implementing a LIFO-optimized data structure.
  • mutable.StackProxy -- A Proxy for a mutable.Stack..
  • mutable.Seq
    • mutable.Buffer -- Sequence of elements which can be changed by appending, prepending or inserting new members.
      • mutable.ArrayBuffer -- An implementation of the mutable.Buffer class, with constant amortized time for the append, update and random access operations. It has some specialized subclasses, such as NodeBuffer.
      • mutable.BufferProxy, mutable.SynchronizedBuffer.
      • mutable.ListBuffer -- A buffer backed by a list. It provides constant time append and prepend, with most other operations being linear.
      • mutable.ObservableBuffer -- A mixin trait which, when mixed to a Buffer, provides notification events through a Publisher interfaces.
      • mutable.IndexedSeq -- As seen above.
      • mutable.LinearSeq -- As seen above.

The Sets

• Set -- A set is a collection that includes at most one of any object.
  • BitSet -- A set of integers stored as a bitset.
    • immutable.BitSet
    • mutable.BitSet
  • SortedSet -- A set whose elements are ordered.
    • immutable.SortedSet
      • immutable.TreeSet -- An implementation of a SortedSet based on a tree.
  • SetProxy -- A Proxy for a Set.
  • immutable.Set
    • immutable.HashSet -- An implementation of Set based on element hashing.
    • immutable.ListSet -- An implementation of Set based on lists.
    • Additional set classes exists to provide optimized implementions for sets from 0 to 4 elements.
    • immutable.SetProxy -- A Proxy for an immutable Set.
  • mutable.Set
    • mutable.HashSet -- An implementation of Set based on element hashing.
    • mutable.ImmutableSetAdaptor -- A class implementing a mutable Set from an immutable Set.
    • LinkedHashSet -- An implementation of Set based on lists.
    • ObservableSet -- A mixin trait which, when mixed with a Set, provides notification events through a Publisher interface.
    • SetProxy -- A Proxy for a Set.
    • SynchronizedSet -- A mixin trait which, when mixed with a Set, provides notification events through a Publisher interface.

---

• Why the Like classes exist (e.g. TraversableLike)

This was done to achieve maximum code reuse. The concrete generic implementation for classes with a certain structure (a traversable, a map, etc) is done in the Like classes. The classes intended for general consumption, then, override selected methods that can be optmized.

• What the companion methods are for (e.g. List.companion)

The builder for the classes, ie, the object which knows how to create instances of that class in a way that can be used by methods like map, is created by a method in the companion object. So, in order to build an object of type X, I need to get that builder from the companion object of X. Unfortunately, there is no way, in Scala, to get from class X to object X. Because of that, there is a method defined in each instance of X, companion, which returns the companion object of class X.

While there might be some use for such method in normal programs, its target is enabling code reuse in the collection library.

• How I know what implicit objects are in scope at a given point

You aren't supposed to care about that. They are implicit precisely so that you don't need to figure out how to make it work.

이러한 암시는 컬렉션의 메서드를 부모 클래스에 정의 할 수 있도록하지만 동일한 유형의 컬렉션을 반환하기 위해 존재합니다. 예를 들어 map메서드는에 정의되어 TraversableLike있지만에서 사용 List하면 다시받을 수 List있습니다.

참고 URL : https://stackoverflow.com/questions/1722137/scala-2-8-collections-design-tutorial