Scala 2.13 儲存架構

語言

    Julien Richard-Foy

    此文件詳細說明 Scala 儲存架構。與 儲存簡介 相比，您將進一步了解架構的內部運作方式。您還將瞭解此架構如何協助您使用幾行程式碼定義自己的儲存，同時重複使用架構中大量的儲存功能。

    Collections API 包含大量的集合操作，這些操作在許多不同的集合實作中均一致存在。為每個集合類型重新實作每個集合操作將導致大量的程式碼，其中大部分會從其他地方複製而來。當在集合函式庫的一部分中新增或修改操作，但未在其他部分中新增或修改時，這種程式碼重複可能會導致隨著時間推移而產生不一致性。集合架構的主要設計目標是避免任何重複，在盡可能少的地方定義每個操作。（理想情況下，所有內容都應該只定義在一個地方，但有一些例外情況需要重新定義。）設計方法是在集合「範本」中實作大多數操作，這些範本可以靈活地從個別基本類別和實作中繼承。

    更精確地說，這些範本解決了以下挑戰

    • 某些轉換操作會傳回相同的具體集合類型（例如，對 List[Int] 呼叫的 filter 會傳回 List[Int]），
    • 某些轉換操作會傳回具有不同元素類型的相同具體集合類型（例如，對 List[Int] 呼叫的 map 可以傳回 List[String]），
    • 某些集合具有單一元素類型（例如 List[A]），而其他集合則具有兩個元素類型（例如 Map[K, V]），
    • 集合上的某些操作會傳回不同的具體集合，具體取決於元素類型。例如，對 Map 呼叫的 map 如果對應函式傳回鍵值對，則會傳回 Map，否則會傳回 Iterable，
    • 某些集合上的轉換運算需要額外的隱含參數（例如 SortedSet 上的 map 會使用隱含的 Ordering），
    • 有些集合是嚴格的（例如 List），而有些則是非嚴格的（例如 View 和 LazyList）。

    以下各節說明範本如何解決這些挑戰。

    將共用運算抽離出來

    此節說明集合中發現的可變性，必須抽象化才能定義可重複使用的運算實作。

    我們可以將集合運算分為兩類

    • 轉換運算，會傳回另一個集合（例如 map、filter、zip 等），
    • 簡化運算，會傳回單一值（例如 isEmpty、foldLeft、find 等）。

    轉換運算較難在範本特質中實作，因為我們希望它們傳回尚未知的集合類型。例如，考慮 List[A] 和 Vector[A] 上 map 運算的簽章

    trait List[A] {
  def map[B](f: A => B): List[B]
}

trait Vector[A] {
  def map[B](f: A => B): Vector[B]
}

    trait List[A]:
  def map[B](f: A => B): List[B]

trait Vector[A]:
  def map[B](f: A => B): Vector[B]

    若要概括 map 的類型簽章，我們必須抽象化結果的集合類型建構函式。

    稍微不同的範例是 filter。考慮它在 List[A] 和 Map[K, V] 上的類型簽章

    trait List[A] {
  def filter(p: A => Boolean): List[A]
}

trait Map[K, V] {
  def filter(p: ((K, V)) => Boolean): Map[K, V]
}

    trait List[A]:
  def filter(p: A => Boolean): List[A]

trait Map[K, V]:
  def filter(p: ((K, V)) => Boolean): Map[K, V]

    要概括 filter 的類型簽章，我們必須抽象出結果的集合類型。

    總之，改變元素類型的運算（map、flatMap、collect 等）需要抽象出結果的集合類型建構函數，而保持相同元素類型的運算（filter、take、drop 等）需要抽象出結果的集合類型。

    抽象出集合類型

    範本特徵 IterableOps 實作了 Iterable[A] 集合類型上可用的運算。

    以下是特徵 IterableOps 的標頭

    trait IterableOps[+A, +CC[_], +C] { … }

    類型參數 A 代表可迭代元素的類型，類型參數 CC 代表集合類型建構函數，類型參數 C 代表集合類型。

    這讓我們可以這樣定義 filter 和 map 的簽章

    trait IterableOps[+A, +CC[_], +C] {
  def filter(p: A => Boolean): C = …
  def map[B](f: A => B): CC[B] = …
}

    trait IterableOps[+A, +CC[_], +C]:
  def filter(p: A => Boolean): C = …
  def map[B](f: A => B): CC[B] = …

    葉集合類型適當地實例化類型參數。例如，在 List[A] 的情況下，我們希望 CC 是 List，C 是 List[A]

    trait List[+A] extends Iterable[A]
  with IterableOps[A, List, List[A]]

    範本特徵的四個分支

    敏銳的讀者可能已經注意到，給定的 map 運算類型簽章不適用於 Map 集合，因為 IterableOps 特徵的 CC[_] 類型參數只接受一個類型參數，而 Map[K, V] 接受兩個類型參數。

    若要支援具有兩個類型參數的集合類型建構函式，我們有另一個名為 MapOps 的範本特徵

    trait MapOps[K, +V, +CC[_, _], +C] extends IterableOps[(K, V), Iterable, C] {
  def map[K2, V2](f: ((K, V)) => (K2, V2)): CC[K2, V2] = …
}

    trait MapOps[K, +V, +CC[_, _], +C] extends IterableOps[(K, V), Iterable, C]:
  def map[K2, V2](f: ((K, V)) => (K2, V2)): CC[K2, V2] = …

    然後 Map[K, V] 可以延伸此特徵並適當地實例化其類型參數

    trait Map[K, V] extends Iterable[(K, V)]
  with MapOps[K, V, Map, Map[K, V]]

    請注意 MapOps 特徵繼承自 IterableOps，以便在 IterableOps 中定義的運算在 MapOps 中也可用。另請注意，傳遞給 IterableOps 特徵的集合類型建構函式為 Iterable。這表示 Map[K, V] 繼承 map 運算的兩個重載

    // from MapOps
def map[K2, V2](f: ((K, V)) => (K2, V2)): Map[K2, V2]

// from IterableOps
def map[B](f: ((K, V)) => B): Iterable[B]

    在使用位置，當您呼叫 map 運算時，編譯器會選取兩個重載中的其中一個。如果傳遞給 map 的函式傳回一對，則兩個函式都適用。在此情況下，將使用 MapOps 中的版本，因為它根據重載解析規則更具體，因此結果集合為 Map。如果引數函式未傳回一對，則僅適用於 IterableOps 中定義的版本。在此情況下，結果集合為 Iterable。這就是我們遵循「相同結果類型」原則的方式：只要有可能，集合上的轉換方法就會產生相同類型的集合。

    總之，由於 Map 集合類型採用兩個類型參數，因此無法將其轉換運算與 IterableOps 中的運算統一，因此需要有專門的 MapOps 範本特徵。

    在 IterableOps 中定義的轉換操作類型簽章與更具體的集合類型：SortedSet[A] 的類型簽章不匹配的情況下，還有另一種情況。在這種情況下，map 操作的類型簽章如下

    def map[B](f: A => B)(implicit ord: Ordering[B]): SortedSet[B]

    def map[B](f: A => B)(using ord: Ordering[B]): SortedSet[B]

    與我們在 IterableOps 中的簽章的區別在於，這裡我們需要元素類型的隱式 Ordering 實例。

    與 Map 一樣，SortedSet 需要一個專門的範本特徵，其中包含轉換操作的重載

    trait SortedSetOps[A, +CC[_], +C] extends IterableOps[A, Set, C] {
  def map[B](f: A => B)(implicit ord: Ordering[B]): CC[B] = …
}

    trait SortedSetOps[A, +CC[_], +C] extends IterableOps[A, Set, C]:
  def map[B](f: A => B)(using ord: Ordering[B]): CC[B] = …

    然後繼承 SortedSetOps 特徵的集合類型適當地實例化其類型參數

    trait SortedSet[A] extends SortedSetOps[A, SortedSet, SortedSet[A]]

    最後，有一種第四類集合需要一個專門的範本特徵：SortedMap[K, V]。這種類型的集合具有兩個類型參數，並且需要在鍵類型上有一個隱式排序實例。因此，我們有一個 SortedMapOps 範本特徵，它提供了適當的重載。

    總的來說，我們已經看到我們有四個範本特徵分支

    種類 未排序 已排序
    CC[_] IterableOps SortedSetOps
    CC[_, _] MapOps SortedMapOps

    以下是一個說明架構的圖表

    範本特徵為灰色，而集合類型為白色。

    嚴格和非嚴格集合

    在集合架構的設計中考慮的另一個區別是，有些集合類型會急切地評估它們的元素（例如 List、Set 等），而另一些集合類型會延遲評估，直到有效地存取元素（例如 LazyList 和 View）。前一類集合被稱為「嚴格」，而後一類集合被稱為「非嚴格」。

    因此，轉換操作的預設實作必須保留繼承這些實作的具體集合類型的「嚴謹性」。例如，我們希望預設的 map 實作在由 View 繼承時是非嚴謹的，而在由 List 繼承時是嚴謹的。

    為達成此目的，操作在預設上是以非嚴謹的 View 來實作。記錄上，View「描述」應用於集合的操作，但直到 View 實際被遍歷時才會評估其結果。以下是 View 的（簡化）定義

    trait View[+A] extends Iterable[A] with IterableOps[A, View, View[A]] {
  def iterator: Iterator[A]
}

    trait View[+A] extends Iterable[A], IterableOps[A, View, View[A]]:
  def iterator: Iterator[A]

    View 是 Iterable，只有一個抽象方法，用於傳回 Iterator 以遍歷其元素。View 元素僅在其 Iterator 被遍歷時才會被評估。

    操作實作

    現在我們對範本特質的階層更熟悉了，我們可以看看某些操作的實際實作。例如，考慮 filter 和 map 的實作

    trait IterableOps[+A, +CC[_], +C] {

  def filter(pred: A => Boolean): C =
    fromSpecific(new View.Filter(this, pred))

  def map[B](f: A => B): CC[B] = 
    from(new View.Map(this, f))

  protected def fromSpecific(coll: IterableOnce[A]): C
  protected def from[E](it: IterableOnce[E]): CC[E]
}

    trait IterableOps[+A, +CC[_], +C]:

  def filter(pred: A => Boolean): C =
    fromSpecific(View.Filter(this, pred))

  def map[B](f: A => B): CC[B] = 
    from(View.Map(this, f))

  protected def fromSpecific(coll: IterableOnce[A]): C
  protected def from[E](it: IterableOnce[E]): CC[E]

    讓我們詳細說明 filter 的實作，步驟如下

    • View.Filter 的實例化會建立一個（非嚴謹的）View，用於篩選基礎集合的元素；
    • 呼叫 fromSpecific 會將 View 轉換為具體集合 C。fromSpecific 的實作留給具體集合：它們可以決定以嚴格或非嚴格的方式評估操作所產生的元素。

    map 的實作類似，只不過它不是使用 fromSpecific，而是使用 from，後者會將元素類型 E 為任意值的可迭代物件當作參數。

    實際上，from 操作並未直接定義在 IterableOps 中，而是透過 (抽象的) iterableFactory 成員存取

    trait IterableOps[+A, +CC[_], +C] {

  def iterableFactory: IterableFactory[CC]
  
  def map[B](f: A => B): CC[B] = 
    iterableFactory.from(new View.Map(this, f))  
}

    trait IterableOps[+A, +CC[_], +C]:

  def iterableFactory: IterableFactory[CC]
  
  def map[B](f: A => B): CC[B] = 
    iterableFactory.from(View.Map(this, f))

    此 iterableFactory 成員由具體集合實作，且通常會參考其伴隨物件，後者提供用於建立具體集合實例的工廠方法。以下是 IterableFactory 定義的摘錄

    trait IterableFactory[+CC[_]] {
  def from[A](source: IterableOnce[A]): CC[A]
}

    trait IterableFactory[+CC[_]]:
  def from[A](source: IterableOnce[A]): CC[A]

    最後但並非最不重要的一點，如上文所述，由於我們有四個分支的範本特徵，因此我們有四個對應的分支工廠。例如，以下是 MapOps 中 map 操作實作的相關程式碼部分

    trait MapOps[K, +V, +CC[_, _], +C]
  extends IterableOps[(K, V), Iterable, C] {

  def map[K2, V2](f: ((K, V)) => (K2, V2)): CC[K2, V2] =
    mapFactory.from(new View.Map(this, f))

  // Similar to iterableFactory, but for Map collection types
  def mapFactory: MapFactory[CC]

}

trait MapFactory[+CC[_, _]] {
  def from[K, V](it: IterableOnce[(K, V)]): CC[K, V]
}

    trait MapOps[K, +V, +CC[_, _], +C]
  extends IterableOps[(K, V), Iterable, C]:

  def map[K2, V2](f: ((K, V)) => (K2, V2)): CC[K2, V2] =
    mapFactory.from(View.Map(this, f))

  // Similar to iterableFactory, but for Map collection types
  def mapFactory: MapFactory[CC]

trait MapFactory[+CC[_, _]]:
  def from[K, V](it: IterableOnce[(K, V)]): CC[K, V]

    當嚴格評估較佳 (或不可避免) 時

    在前文中，我們說明具體集合的「嚴格性」應由預設操作實作保留。然而，在某些情況下，這會導致較不有效率的實作。例如，partition 必須對底層集合執行兩次遍歷。在其他一些情況下 (例如 groupBy)，如果不評估集合元素，就無法實作操作。

    對於這些情況，我們也提供在嚴格模式中實作運算的方法。模式不同：它不是基於 View，而是基於 Builder。以下是 Builder 特質的概要

    package scala.collection.mutable

trait Builder[-A, +C] {
  def addOne(elem: A): this.type
  def result(): C
}

    package scala.collection.mutable

trait Builder[-A, +C]:
  def addOne(elem: A): this.type
  def result(): C

    Builder 在元素類型 A 和它們傳回的集合類型 C 中都是泛型的。您可以使用 b.addOne(x)（或 b += x）將元素 x 新增到 builder b。 result() 方法會從 builder 傳回一個集合。

    透過與 fromSpecificIterable 和 fromIterable 對稱，範本特質提供取得 builder 的方法，而 builder 會產生具有相同類型元素的集合，以及取得 builder 的方法，而 builder 會產生相同類型的集合，但元素類型不同。以下程式碼顯示 IterableOps 和 IterableFactory 的相關部分，以在嚴格和非嚴格模式中建立集合

    trait IterableOps[+A, +CC[_], +C] {
  def iterableFactory: IterableFactory[CC]
  protected def fromSpecific(coll: IterableOnce[A]): C
  protected def newSpecificBuilder: Builder[A, C]
}

trait IterableFactory[+CC[_]] {
  def from[A](source: IterableOnce[A]): CC[A]
  def newBuilder[A]: Builder[A, CC[A]]
}

    trait IterableOps[+A, +CC[_], +C]:
  def iterableFactory: IterableFactory[CC]
  protected def fromSpecific(coll: IterableOnce[A]): C
  protected def newSpecificBuilder: Builder[A, C]

trait IterableFactory[+CC[_]]:
  def from[A](source: IterableOnce[A]): CC[A]
  def newBuilder[A]: Builder[A, CC[A]]

    請注意，一般來說，不必是嚴格的運算應在非嚴格模式中實作，否則在非嚴格具體集合上使用時會導致令人驚訝的行為（您可以在 這篇文章 中閱讀有關該陳述的更多資訊）。話雖如此，嚴格模式通常更有效率。這就是我們提供範本特質的原因，其運算實作已覆寫以利用嚴格 builder。這些範本特質的名稱總是從 StrictOptimized 開始。如果您的自訂集合是嚴格集合，您應該為其使用此類範本特質。

    摘要

    本文說明

    • 集合操作實作在以 Ops 為字尾的範本特質中（例如 IterableOps[A, CC[_], C]），
    • 這些範本特質抽象集合元素的類型 (A)、傳回集合的類型建構函式 (CC) 和傳回集合的類型 (C），
    • 有四個範本特質分支（IterableOps、MapOps、SortedSetOps 和 SortedMapOps），
    • 有些轉換操作（例如 map）會根據其引數類型重載以傳回不同的結果類型，
    • 轉換操作的邏輯主要實作在檢視中，但有範本特質的特殊版本（以 StrictOptimized 為字首）會覆寫這些操作以使用基於建構函式的做法。

    現在您已具備實作 自訂集合類型 所需的所有知識。

    致謝

    此頁面包含改編自 Odersky、Spoon 和 Venners 所著的《Programming in Scala》一書的資料。我們感謝 Artima 慷慨同意我們刊登此內容。

    此頁面的貢獻者

    內容
    此頁面有問題嗎？
         請協助我們修正！