Martin Odersky 和 Lex Spoon
這些頁面詳細描述 Scala 收藏架構的架構。與 Scala 2.8 收藏 API 相比，您將會發現更多關於架構內部運作的資訊。您還將會了解這個架構如何協助您使用幾行程式碼定義自己的收藏，同時重複使用架構中絕大部分的收藏功能。
Scala 2.8 收藏 API 包含大量收藏操作，這些操作一致存在於許多不同的收藏實作中。為每個收藏類型重新實作每個收藏操作會產生大量的程式碼，其中大部分會從其他地方複製而來。當在收藏函式庫的一部份新增或修改操作，但未在其他部份進行相同動作時，這種程式碼重複可能會隨著時間而導致不一致。新收藏架構的主要設計目標是避免任何重複，在最少的地方定義每個操作。(理想情況下，所有內容都應該只定義在一個地方，但有少數例外情況需要重新定義。)設計方法是在收藏「範本」中實作大部分操作，這些範本可以彈性地繼承自個別基本類別和實作。以下頁面說明這些範本和其他類別和特質，這些類別和特質構成架構的「建構區塊」，以及它們支援的建構原則。
建構器
Builder 特質的概要
package scala.collection.mutable
trait Builder[-Elem, +To] {
def +=(elem: Elem): this.type
def result(): To
def clear(): Unit
def mapResult[NewTo](f: To => NewTo): Builder[Elem, NewTo] = ...
}
幾乎所有收藏操作都是根據橫越和建構器實作的。橫越是透過 Traversable 的 foreach 方法處理，而建立新的收藏則是由 Builder 類別的執行個體處理。上述清單顯示這個特質的簡略概要。
您可以使用 b += x 將元素 x 加入到建構器 b 中。此外，也有語法可以一次加入多個元素，例如 b += (x, y)。使用 b ++= xs 加入另一個集合時，其作用方式與緩衝區相同（事實上，緩衝區是建構器的豐富版本）。result() 方法會從建構器傳回一個集合。在取得建構器的結果後，建構器的狀態會變為未定義，但可以使用 clear() 將其重設為新的空白狀態。建構器在元素類型 Elem 和傳回集合的類型 To 中都是通用的。
建構器通常可以參照其他建構器來組合集合的元素，但之後可能會想要轉換其他建構器的結果，例如將其指定為不同的類型。這個任務已透過 Builder 類別中的 mapResult 方法簡化。例如，假設您有一個陣列緩衝區 buf。陣列緩衝區本身就是建構器，因此取得陣列緩衝區的 result() 會傳回相同的緩衝區。如果您要使用這個緩衝區來產生建構陣列的建構器，您可以像這樣使用 mapResult
scala> val buf = new ArrayBuffer[Int]
buf: scala.collection.mutable.ArrayBuffer[Int] = ArrayBuffer()
scala> val bldr = buf mapResult (_.toArray)
bldr: scala.collection.mutable.Builder[Int,Array[Int]]
= ArrayBuffer()
結果值 bldr 是使用陣列緩衝區 buf 來收集元素的建構器。當從 bldr 要求結果時，會計算 buf 的結果，這會產生陣列緩衝區 buf 本身。然後，這個陣列緩衝區會使用 _.toArray 映射到陣列。因此，最終結果是 bldr 是陣列的建構器。
分解常見的運算
TraversableLike 特質綱要
package scala.collection
trait TraversableLike[+Elem, +Repr] {
def newBuilder: Builder[Elem, Repr] // deferred
def foreach[U](f: Elem => U): Unit // deferred
...
def filter(p: Elem => Boolean): Repr = {
val b = newBuilder
foreach { elem => if (p(elem)) b += elem }
b.result
}
}
集合函式庫重新設計的主要目標是同時具備自然型別和最大程度的實作程式碼共用。特別是，Scala 的集合遵循「相同結果型別」原則：只要有可能，集合上的轉換方法會產生相同型別的集合。例如，filter 函式應在每個集合型別上產生相同集合型別的執行個體。對 List 套用 filter 應產生 List；對 Map 套用應產生 Map，依此類推。在本節的其餘部分，您將瞭解如何達成此目的。
Scala 集合函式庫透過在所謂的實作特質中使用泛型建構函式和集合遍歷來避免程式碼重複，並達成「相同結果型別」原則。這些特質以 Like 字尾命名；例如，IndexedSeqLike 是 IndexedSeq 的實作特質，類似地，TraversableLike 是 Traversable 的實作特質。例如 Traversable 或 IndexedSeq 等集合特質會從這些特質繼承其所有具體方法實作。實作特質有兩個型別參數，而非一般集合的一個。它們不僅針對集合的元素型別進行參數化，也針對集合的表示型別進行參數化，亦即基礎集合的型別，例如 Seq[T] 或 List[T]。例如，以下是特質 TraversableLike 的標頭
trait TraversableLike[+Elem, +Repr] { ... }
類型參數 Elem 代表可遍歷元素的類型，而類型參數 Repr 代表其表示。對 Repr 沒有限制。特別是 Repr 可能會實例化為其本身不是 Traversable 子類型的類型。這樣一來，集合階層之外的類別，例如 String 和 Array，仍然可以使用在集合實作特質中定義的所有運算。
以 filter 為例，此運算在特質 TraversableLike 中對所有集合類別定義一次。相關程式碼的概要顯示在上述 特質 TraversableLike 的概要 中。此特質宣告兩個抽象方法 newBuilder 和 foreach，它們在具體的集合類別中實作。使用這些方法，filter 運算對所有集合實作的方式相同。它會先使用 newBuilder 為表示類型 Repr 建立新的產生器。然後它會使用 foreach 遍歷目前集合的所有元素。如果元素 x 符合指定的謂詞 p（亦即 p(x) 為 true），它就會加入產生器。最後，產生器中收集的元素會透過呼叫產生器的 result 方法，以 Repr 集合類型的實例回傳。
稍為複雜一點的是集合上的 map 操作。例如，如果 f 是從 String 到 Int 的函數，而 xs 是 List[String]，那麼 xs map f 應該給出 List[Int]。同樣地，如果 ys 是 Array[String]，那麼 ys map f 應該給出 Array[Int]。問題是如何在不重複清單和陣列中 map 方法定義的情況下實現這一點。在 特質 TraversableLike 中顯示的 newBuilder/foreach 架構對此還不夠，因為它只允許建立同一集合類型的新實例，而 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)
如果您對位元組集執行倍增函數 _ * 2，您會得到另一個位元組集。但是，如果您對同一組位元組執行函數 (_.toFloat)，結果將是通用的 Set[Float]。當然，它不能是位元組集，因為位元組集包含 Int，而不是 Float。
請注意，map 的結果類型取決於傳遞給它的函數類型。如果該函數參數的結果類型再次為 Int，則 map 的結果為 BitSet，但如果函數參數的結果類型為其他內容，則 map 的結果只是一個 Set。您很快就會發現 Scala 如何實現這種類型靈活性。
BitSet 的問題並非孤立案例。以下是與解釋器的另外兩個互動，它們都將函數映射到 Map
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，但我們仍然可以形成 Iterable，它是 Map 的超特徵。
你可能會問，為什麼不限制 map，使其總是回傳相同類型的集合？例如，在位元組集合中，map 只能接受 Int 對 Int 的函式，而在 Map 中，它只能接受成對的函式。此類限制不僅從物件導向建模的角度來看是不可取的，而且是非法的，因為它們會違反 Liskov 替換原則：Map 是 Iterable。因此，在 Iterable 上合法的每個操作也必須在 Map 上合法。
Scala 改用重載來解決這個問題：不是 Java 繼承的簡單重載形式（那不夠靈活），而是由隱含參數提供的更系統化的重載形式。
在 TraversableLike 中實作 map
def map[B, That](f: Elem => B)
(implicit bf: CanBuildFrom[Repr, B, That]): That = {
val b = bf(this)
this.foreach(x => b += f(x))
b.result
}
上述清單顯示特質 TraversableLike 的 map 實作。它與 特質 TraversableLike 中顯示的 filter 實作非常類似。主要的差異在於 filter 使用 newBuilder 方法，該方法在 TraversableLike 中是抽象的，而 map 使用一個建構器工廠，該工廠作為類型為 CanBuildFrom 的額外隱含參數傳遞。
特質 CanBuildFrom
package scala.collection.generic
trait CanBuildFrom[-From, -Elem, +To] {
// Creates a new builder
def apply(from: From): Builder[Elem, To]
}
以上清單顯示特質 CanBuildFrom 的定義，它代表建構器工廠。它有三個類型參數：From 指出此建構器工廠適用的類型，Elem 指出要建構的集合的元素類型，To 指出要建構的集合類型。透過定義建構器工廠的正確隱式定義，您可以依需要調整正確的輸入行為。以類別 BitSet 為例。它的伴隨物件會包含類型 CanBuildFrom[BitSet, Int, BitSet] 的建構器工廠。這表示在對 BitSet 執行操作時，您可以建構另一個 BitSet，前提是要建構的集合的元素類型為 Int。如果不是這種情況，編譯器會檢查超類別，並回退到 mutable.Set 的伴隨物件中定義的隱式建構器工廠。此更通用的建構器工廠的類型（其中 A 是泛型類型參數）為
CanBuildFrom[Set[_], A, Set[A]]
這表示在對任意 Set（由存在類型 Set[_] 表示）執行操作時，您可以再次建構 Set，不論元素類型 A 為何。有了這兩個 CanBuildFrom 的隱式實例，您就可以依賴 Scala 的隱式解析規則來選取適當且最明確的那一個。
因此，隱式解析會提供正確的靜態類型，以進行棘手的集合運算，例如 map。但動態類型呢？特別是，假設您對具有 Iterable 作為其靜態類型的 List 值套用一些函式
scala> val xs: Iterable[Int] = List(1, 2, 3)
xs: Iterable[Int] = List(1, 2, 3)
scala> val ys = xs map (x => x * x)
ys: Iterable[Int] = List(1, 4, 9)
上面 ys 的靜態類型為 Iterable，正如預期。但其動態類型是（且仍應該是）List！此行為是透過另一個間接方式來實現的。 CanBuildFrom 中的 apply 方法將來源集合作為引數傳遞。大多數泛用可遍歷項目的建構函式工廠（事實上，除了葉狀類別的建構函式工廠之外）會將呼叫轉發到集合的 genericBuilder 方法。反過來，genericBuilder 方法會呼叫屬於它所定義的集合的建構函式。因此，Scala 使用靜態隱式解析來解析 map 類型的約束，並使用虛擬調度來選取對應於這些約束的最佳動態類型。
在目前的範例中，靜態隱式解析會選取 Iterable 的 CanBuildFrom，它會對收到作為引數的值呼叫 genericBuilder。但在執行階段，因為虛擬調度，會呼叫 List.genericBuilder 而不是 Iterable.genericBuilder，所以 map 會建立一個 List。
整合新的集合：RNA 序列
如果您想要整合新的集合類別，讓它可以從所有預定義的運算中獲益並使用正確的類型，需要執行哪些步驟？在接下來的幾個區段中，您將逐步了解兩個執行此項操作的範例，分別是 RNA 鹼基序列和使用 Patricia 樹狀結構實作的前綴對應。
首先從第一個範例開始，我們定義四個 RNA 鹼基
abstract class Base
case object A extends Base
case object U extends Base
case object G extends Base
case object C extends Base
object Base {
val fromInt: Int => Base = Array(A, U, G, C)
val toInt: Base => Int = Map(A -> 0, U -> 1, G -> 2, C -> 3)
}
假設您想要為 RNA 鏈建立新的序列類型，這些鏈是鹼基 A（腺嘌呤）、U（尿嘧啶）、G（鳥嘌呤）和 C（胞嘧啶）的序列。如上方的 RNA 鹼基清單所示，可以輕鬆設定鹼基的定義。
每個鹼基都定義為繼承自共用抽象類別 Base 的案例物件。Base 類別有一個伴隨物件，定義兩個在鹼基和整數 0 到
- 您可以在範例中看到使用集合來實作這些函式的兩種不同方式。
toInt函式實作為從Base值到整數的Map。反向函式fromInt實作為陣列。這利用了映射和陣列都是函式的這個事實，因為它們繼承自Function1特質。
下一個任務是為 RNA 鏈定義一個類別。在概念上，RNA 鏈只是一個 Seq[Base]。然而，RNA 鏈可能相當長，因此在精簡表示法上投入一些工作是有意義的。由於只有四個鹼基，因此可以用兩個位元來識別一個鹼基，因此您可以將十六個鹼基作為兩個位元值儲存在一個整數中。然後，這個想法是建立 Seq[Base] 的一個特殊子類別，它使用這個封裝的表示法。
RNA 鏈類別的第一個版本
import collection.IndexedSeqLike
import collection.mutable.{Builder, ArrayBuffer}
import collection.generic.CanBuildFrom
final class RNA1 private (val groups: Array[Int],
val length: Int) extends IndexedSeq[Base] {
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 {
// Number of bits necessary to represent group
private val S = 2
// Number of groups that fit in an Int
private val N = 32 / S
// Bitmask to isolate a group
private val M = (1 << S) - 1
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)
}
The RNA strands class listing above
presents the first version of this
class. It will be refined later. The class RNA1 has a constructor that
takes an array of Ints as its first argument. This array contains the
packed RNA data, with sixteen bases in each element, except for the
last array element, which might be partially filled. The second
argument, length, specifies the total number of bases on the array
(and in the sequence). Class RNA1 extends IndexedSeq[Base]. Trait
IndexedSeq, which comes from package scala.collection.immutable,
defines two abstract methods, length and apply. These need to be
implemented in concrete subclasses. Class RNA1 implements length
automatically by defining a parametric field of the same name. It
implements the indexing method apply with the code given in class
RNA1. Essentially, apply first
extracts an integer value from the
groups array, then extracts the correct two-bit number from that
integer using right shift (>>) and mask (&). The private constants S,
N, and M come from the RNA1 companion object. S specifies the size of
each packet (i.e., two); N specifies the number of two-bit packets per
integer; and M is a bit mask that isolates the lowest S bits in a
word.
Note that the constructor of class RNA1 is private. This means that
clients cannot create RNA1 sequences by calling new, which makes
sense, because it hides the representation of RNA1 sequences in terms
of packed arrays from the user. If clients cannot see what the
representation details of RNA sequences are, it becomes possible to
change these representation details at any point in the future without
affecting client code. In other words, this design achieves a good
decoupling of the interface of RNA sequences and its
implementation. However, if constructing an RNA sequence with new is
impossible, there must be some other way to create new RNA sequences,
else the whole class would be rather useless. In fact there are two
alternatives for RNA sequence creation, both provided by the RNA1
companion object. The first way is method fromSeq, which converts a
given sequence of bases (i.e., a value of type Seq[Base]) into an
instance of class RNA1. The fromSeq method does this by packing all
the bases contained in its argument sequence into an array, then
calling RNA1’s private constructor with that array and the length of
the original sequence as arguments. This makes use of the fact that a
private constructor of a class is visible in the class’s companion
object.
建立 RNA1 值的第二種方式是由 RNA1 物件中的 apply 方法提供的。它採用變數個 Base 參數，並簡單地將它們作為一個序列轉發到 fromSeq。以下是兩個建立方案的實際操作
scala> val xs = List(A, G, U, A)
xs: List[Product with Serializable with Base] = List(A, G, U, A)
scala> RNA1.fromSeq(xs)
res1: RNA1 = RNA1(A, G, U, A)
scala> val rna1 = RNA1(A, U, G, G, C)
rna1: RNA1 = RNA1(A, U, G, G, C)
調整 RNA 方法的結果類型
以下是與 RNA1 抽象的更多互動
scala> rna1.length
res2: Int = 5
scala> rna1.last
res3: Base = C
scala> rna1.take(3)
res4: IndexedSeq[Base] = Vector(A, U, G)
前兩個結果符合預期，但取 rna1 前三個元素的最後一個結果可能不符合預期。事實上，您會看到 IndexedSeq[Base] 作為靜態結果類型，以及 Vector 作為結果值的動態類型。您可能期望看到 RNA1 值。但這是不可能的，因為在 類別 RNA1 中所做的所有事情都是讓 RNA1 延伸 IndexedSeq。另一方面，類別 IndexedSeq 有 take 方法，它會傳回 IndexedSeq，並且這是在 IndexedSeq 的預設實作 Vector 中實作的。因此，這就是您在先前互動的最後一行中看到的內容。
現在您了解為什麼事情會變成這樣，接下來的問題應該是需要做什麼來改變它們？執行此操作的一種方法是在類別 RNA1 中覆寫 take 方法，或許像這樣
def take(count: Int): RNA1 = RNA1.fromSeq(super.take(count))
這會為 take 完成工作。但 drop、filter 或 init 呢？事實上，序列中有超過五十種方法會再傳回一個序列。為了保持一致性，所有這些都必須被覆寫。這看起來越來越不像一個有吸引力的選項。幸運的是，有一個更簡單的方法可以達到相同的目的，如下一節所示。
RNA 序列類別的第二個版本
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 = // as before
}
RNA 類別不僅需要繼承自 IndexedSeq，還需要繼承自其實作特質 IndexedSeqLike。這在 RNA2 類別的上述清單中顯示。新的實作僅在兩個方面與前一個實作不同。首先，RNA2 類別現在也擴充 IndexedSeqLike[Base, RNA2]。其次，它提供 RNA 鏈的建構器。IndexedSeqLike 特質以可擴充的方式實作 IndexedSeq 的所有具體方法。例如，take、drop、filter 或 init 等方法的回傳類型是傳遞給 IndexedSeqLike 類別的第二個類型參數，亦即在 RNA2 類別中，它本身就是 RNA2。
為了能夠執行此操作，IndexedSeqLike 以 newBuilder 抽象為基礎，此抽象會建立正確類型的建構器。IndexedSeqLike 特質的子類別必須覆寫 newBuilder 以回傳它們自己的類型的集合。在 RNA2 類別中，newBuilder 方法會回傳類型為 Builder[Base, RNA2] 的建構器。
要建構這個建構器，它首先會建立一個 ArrayBuffer，它本身是一個 Builder[Base, ArrayBuffer]。然後，它透過呼叫 mapResult 方法，將 ArrayBuffer 建構器轉換成 RNA2 建構器。mapResult 方法預期會有一個從 ArrayBuffer 轉換成 RNA2 的轉換函式作為其參數。提供的函式只是 RNA2.fromSeq，它會將任意基礎序列轉換成 RNA2 值（請記住，陣列緩衝區是一種序列，因此 RNA2.fromSeq 可以套用於它）。
如果你省略 newBuilder 定義，你會收到類似以下的錯誤訊息
RNA2.scala:5: error: overriding method newBuilder in trait
TraversableLike of type => scala.collection.mutable.Builder[Base,RNA2];
method newBuilder in trait GenericTraversableTemplate of type
=> scala.collection.mutable.Builder[Base,IndexedSeq[Base]] has
incompatible type
class RNA2 private (val groups: Array[Int], val length: Int)
^
one error found
錯誤訊息很長而且複雜，反映了收集函式庫的組成方式很複雜。最好忽略方法的來源資訊，因為在這種情況下，它帶來的負面影響大於正面影響。剩下的就是一個方法 newBuilder，其結果類型為 Builder[Base, RNA2]，需要定義，但找到了結果類型為 Builder[Base,IndexedSeq[Base]] 的方法 newBuilder。後者不會覆寫前者。第一個方法，其結果類型為 Builder[Base, RNA2]，是一個抽象方法，在 類別 RNA2 中以這種類型實例化，方法是將 RNA2 類型參數傳遞給 IndexedSeqLike。第二個方法，結果類型為 Builder[Base,IndexedSeq[Base]]，是由繼承的 IndexedSeq 類別提供的。換句話說，RNA2 類別在沒有定義第一個結果類型的 newBuilder 的情況下是無效的。
透過 RNA2 類別 的精緻實作，方法（例如 take、drop 或 filter）現在可以如預期般運作
scala> val rna2 = RNA2(A, U, G, G, C)
rna2: RNA2 = RNA2(A, U, G, G, C)
scala> rna2 take 3
res5: RNA2 = RNA2(A, U, G)
scala> rna2 filter (U !=)
res6: RNA2 = RNA2(A, G, G, C)
處理 map 及相關函式
然而，集合中還有另一類方法尚未處理。這些方法並不總是會回傳相同的集合類型。它們可能會回傳相同類型的集合，但元素類型不同。這類方法的經典範例是 map 方法。如果 s 是 Seq[Int]，且 f 是從 Int 到 String 的函數，則 s.map(f) 會回傳 Seq[String]。因此，接收者和結果之間的元素類型會改變，但集合的類型保持不變。
還有許多其他方法的行為與 map 類似。有些方法您會預期有這種行為（例如 flatMap、collect），但有些方法您可能不會預期。例如，附加方法 ++ 也可能會回傳與其參數類型不同的結果，將 String 清單附加到 Int 清單會產生 Any 清單。這些方法應如何調整為 RNA 序列？理想的行為是在將鹼基對應到鹼基或使用 ++ 附加兩個 RNA 序列時，會取得 RNA 序列。
scala> val rna = RNA(A, U, G, G, C)
rna: RNA = RNA(A, U, G, G, C)
scala> rna map { case A => U case b => b }
res7: RNA = RNA(U, U, G, G, C)
scala> rna ++ rna
res8: RNA = RNA(A, U, G, G, C, A, U, G, G, C)
另一方面，將鹼基對應到 RNA 序列中的其他類型無法產生另一個 RNA 序列，因為新元素的類型錯誤。它必須產生序列。同樣地，將非 Base 類型的元素附加到 RNA 序列會產生一般序列，但無法產生另一個 RNA 序列。
scala> rna map Base.toInt
res2: IndexedSeq[Int] = Vector(0, 1, 2, 2, 3)
scala> rna ++ List("missing", "data")
res3: IndexedSeq[java.lang.Object] =
Vector(A, U, G, G, C, missing, data)
這是理想情況下您會預期的。但這不是 RNA2 類別 提供的。事實上，所有範例都會傳回 Vector 的執行個體，而不仅仅是最後兩個。如果您使用此類別的執行個體執行以上前三個指令，您會得到
scala> val rna2 = RNA2(A, U, G, G, C)
rna2: RNA2 = RNA2(A, U, G, G, C)
scala> rna2 map { case A => U case b => b }
res0: IndexedSeq[Base] = Vector(U, U, G, G, C)
scala> rna2 ++ rna2
res1: IndexedSeq[Base] = Vector(A, U, G, G, C, A, U, G, G, C)
因此，map 和 ++ 的結果永遠不會是 RNA 序列，即使已產生集合的元素類型是 Base。若要了解如何做得更好，最好仔細查看 map 方法 (或具有類似簽章的 ++) 的簽章。map 方法最初在 scala.collection.TraversableLike 類別中定義，其簽章如下
def map[B, That](f: A => B)
(implicit cbf: CanBuildFrom[Repr, B, That]): That
其中 A 是集合元素的類型，而 Repr 是集合本身的類型，也就是傳遞給實作類別 (例如 TraversableLike 和 IndexedSeqLike) 的第二個類型參數。map 方法會再採用兩個類型參數，B 和 That。B 參數代表對應函數的結果類型，也是新集合的元素類型。That 出現在 map 的結果類型中，因此它代表已建立的新集合類型。
如何決定 That 類型？實際上，它透過隱含參數 cbf 與其他類型連結，類型為 CanBuildFrom[Repr, B, That]。這些 CanBuildFrom 隱含值由個別集合類別定義。回想一下，類型為 CanBuildFrom[Repr, B, That] 的隱含值表示：「這是一個方法，給定類型為 Repr 的集合和類型為 B 的新元素，建立包含這些元素的類型為 That 的集合」。
現在 map 和 ++ 在 RNA2 序列上的行為變得更清楚。沒有建立 RNA2 序列的 CanBuildFrom 執行個體，因此在繼承特質 IndexedSeq 的伴隨物件中找到下一個可用的 CanBuildFrom。該隱含值建立 Vector（回想一下 Vector 是 IndexedSeq 的預設實作），而這正是您將 map 套用至 rna2 時所看到的。
RNA 鏈類別的最終版本
final class RNA private (val groups: Array[Int], val length: Int)
extends IndexedSeq[Base] with IndexedSeqLike[Base, RNA] {
import RNA._
// Mandatory re-implementation of `newBuilder` in `IndexedSeq`
override protected[this] def newBuilder: Builder[Base, RNA] =
RNA.newBuilder
// Mandatory implementation of `apply` in `IndexedSeq`
def apply(idx: Int): Base = {
if (idx < 0 || length <= idx)
throw new IndexOutOfBoundsException
Base.fromInt(groups(idx / N) >> (idx % N * S) & M)
}
// Optional re-implementation of foreach,
// to make it more efficient.
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
}
}
}
RNA 伴隨物件的最終版本
object RNA {
private val S = 2 // number of bits in group
private val M = (1 << S) - 1 // bitmask to isolate a group
private val N = 32 / S // number of groups in an Int
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] =
new CanBuildFrom[RNA, Base, RNA] {
def apply(): Builder[Base, RNA] = newBuilder
def apply(from: RNA): Builder[Base, RNA] = newBuilder
}
}
To address this shortcoming, you need to define an implicit instance
of CanBuildFrom in the companion object of the RNA class. That
instance should have type CanBuildFrom[RNA, Base, RNA]. Hence, this
instance states that, given an RNA strand and a new element type Base,
you can build another collection which is again an RNA strand. The two
listings above of class RNA and
its companion object show the
details. Compared to class RNA2
there are two important
differences. First, the newBuilder implementation has moved from the
RNA class to its companion object. The newBuilder method in class RNA
simply forwards to this definition. Second, there is now an implicit
CanBuildFrom value in object RNA. To create this value you need to
define two apply methods in the CanBuildFrom trait. Both create a new
builder for an RNA collection, but they differ in their argument
list. The apply() method simply creates a new builder of the right
type. By contrast, the apply(from) method takes the original
collection as argument. This can be useful to adapt the dynamic type
of builder’s return type to be the same as the dynamic type of the
receiver. In the case of RNA this does not come into play because RNA
is a final class, so any receiver of static type RNA also has RNA as
its dynamic type. That’s why apply(from) also simply calls newBuilder,
ignoring its argument.
這就是了。最後的 RNA 類別 在預期的類型中實作所有集合方法。其實作需要一點點協定。基本上，您需要知道在哪裡放置 newBuilder 工廠和 canBuildFrom 隱含函數。好處是，透過相對較少的程式碼，您可以自動定義大量的函數。此外，如果您不打算對集合執行大量操作，例如 take、drop、map 或 ++，您可以選擇不執行額外的長度，並停止在 類別 RNA1 中顯示的實作。
到目前為止的討論都集中在定義新序列時，使用符合特定類型的函數所需的最小定義量。但在實務上，您可能也想為序列新增新功能，或覆寫現有函數以提升效率。這方面的範例是類別 RNA 中覆寫的 foreach 函數。foreach 本身就是一個重要的函數，因為它實作了集合的迴圈。此外，許多其他集合函數都是以 foreach 為基礎實作的。因此，花點功夫最佳化函數的實作是有意義的。 IndexedSeq 中 foreach 的標準實作只會使用 apply 選取集合中的每個第 i 個元素，其中 i 的範圍從 0 到集合長度減一。因此，這個標準實作會為 RNA 序列中的每個元素選取一個陣列元素，並解開其中的鹼基。類別 RNA 中覆寫的 foreach 比這更聰明。它會立即對每個選取的陣列元素套用指定的函數，套用在其中包含的所有鹼基上。因此，陣列選取和位元解開的工作量大幅減少。
整合新的前綴對應
作為第二個範例，您將學習如何將新類型的映射整合到集合架構中。這個想法是透過「Patricia 樹」實作一個可變動的映射，其中 String 為鍵的類型。Patricia 一詞實際上是「用來擷取字母數字編碼資訊的實用演算法」的縮寫，而 trie 則來自 retrieval（trie 也稱為基數樹或前綴樹）。這個想法是將一個集合或映射儲存在一個樹中，其中搜尋鍵中的後續字元會唯一地決定樹中的路徑。例如，儲存字串「abc」、「abd」、「al」、「all」和「xy」的 Patricia 樹會像這樣
一個 Patricia 樹範例：
要在這個 trie 中找到對應於字串「abc」的節點，只要照著標籤為「a」的子樹走，從那裡繼續走到標籤為「b」的子樹，最後到達標籤為「c」的子樹即可。如果 Patricia 樹用作映射，則與鍵關聯的值會儲存在可透過該鍵到達的節點中。如果它是一個集合，您只需儲存一個標記，表示該節點存在於集合中。
Patricia 樹支援非常有效率的查詢和更新。另一個不錯的功能是它們支援透過提供前綴來選取子集合。例如，在上面的 Patricia 樹中，您只要從樹的根節點照著「a」連結走，就可以取得所有以「a」開頭的鍵的子集合。
基於這些想法，我們現在將引導您實作一個以 Patricia 樹實作的映射。我們將映射稱為 PrefixMap，這表示它提供一個方法 withPrefix，用來選取所有以給定前綴開頭的鍵的子映射。我們將先定義一個前綴映射，其中鍵如執行範例中所示
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))
然後對 m 呼叫 withPrefix 會產生另一個前綴對應
scala> m withPrefix "a"
res14: PrefixMap[Int] = Map((bc,0), (bd,1), (l,2), (ll,3))
Patricia trie 實作
import collection._
class PrefixMap[T]
extends mutable.Map[String, T]
with mutable.MapLike[String, T, PrefixMap[T]] {
var suffixes: immutable.Map[Char, PrefixMap[T]] = Map.empty
var value: Option[T] = None
def get(s: String): Option[T] =
if (s.isEmpty) value
else suffixes get (s(0)) flatMap (_.get(s substring 1))
def withPrefix(s: String): PrefixMap[T] =
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]
}
前一個清單顯示 PrefixMap 的定義。對應的鍵是 String 類型，而值是參數類型 T。它延伸 mutable.Map[String, T] 和 mutable.MapLike[String, T, PrefixMap[T]]。您已在 RNA 序列範例中看過序列的這種模式；然後，繼承實作類別（例如 MapLike）就像現在一樣，可為轉換（例如 filter）取得正確的結果類型。
前綴對應節點有兩個可變動欄位：suffixes 和 value。value 欄位包含與節點相關聯的選用值。它初始化為 None。suffixes 欄位包含從字元到 PrefixMap 值的對應。它初始化為空對應。
您可能會問，為什麼我們選用不可變動對應作為 suffixes 的實作類型？難道可變動對應不會更標準，因為 PrefixMap 整體而言也是可變動的嗎？答案是，僅包含幾個元素的不可變動對應在空間和執行時間上都非常有效率。例如，包含少於 5 個元素的對應會表示為單一物件。相反地，標準可變動對應是 HashMap，即使它為空，通常也會佔用約 80 個位元組。因此，如果小型集合很常見，最好選用不可變動而非可變動。在 Patricia tries 的情況下，我們預期除了樹最頂端的節點外，大多數節點只會包含幾個後繼。因此，將這些後繼儲存在不可變動對應中可能會更有效率。
現在來看一下一個映射必須實作的第一個方法：get。演算法如下：要取得在字首映射中與空字串關聯的值，只要選擇儲存在樹根（目前的映射）中的選用 值 即可。否則，如果金鑰字串不為空，請嘗試選擇對應於字串第一個字元的子映射。如果這樣會產生一個映射，請接著在該映射中查詢第一個字元之後的剩餘金鑰字串。如果選擇失敗，表示金鑰未儲存在映射中，因此傳回 None。選用值 opt 上的合併選擇可以使用 opt.flatMap(x => f(x)) 優雅地表示。當套用於為 None 的選用值時，它會傳回 None。否則 opt 為 Some(x)，且函式 f 會套用於封裝的值 x，產生一個新的選項，由 flatMap 傳回。
要實作一個可變映射的後續兩個方法為 += 和 -=。在 PrefixMap 的實作中，它們是根據其他兩個方法定義的：update 和 remove。
remove 方法與 get 方法非常類似，不同之處在於在傳回任何關聯值之前，會將包含該值的欄位設定為 None。update 方法會先呼叫 withPrefix 來導覽至需要更新的樹狀節點，然後將該節點的 value 欄位設定為指定值。withPrefix 方法會導覽樹狀結構，並在必要時建立子地圖，如果字元的前綴尚未包含在樹狀結構中的路徑中。
The last abstract method to implement for a mutable map is
iterator. This method needs to produce an iterator that yields all
key/value pairs stored in the map. For any given prefix map this
iterator is composed of the following parts: First, if the map
contains a defined value, Some(x), in the value field at its root,
then ("", x) is the first element returned from the
iterator. Furthermore, the iterator needs to traverse the iterators of
all submaps stored in the suffixes field, but it needs to add a
character in front of every key string returned by those
iterators. More precisely, if m is the submap reached from the root
through a character chr, and (s, v) is an element returned from
m.iterator, then the root’s iterator will return (chr +: s, v)
instead. This logic is implemented quite concisely as a concatenation
of two for expressions in the implementation of the iterator method in
PrefixMap. The first for expression iterates over value.iterator. This
makes use of the fact that Option values define an iterator method
that returns either no element, if the option value is None, or
exactly one element x, if the option value is Some(x).
請注意，PrefixMap 中未定義 newBuilder 方法。因為地圖和集合附帶預設建構函式，它們是 MapBuilder 類別的執行個體，所以不需要。對於可變動地圖，預設建構函式會從一個空地圖開始，然後使用地圖的 += 方法加入後續元素。對於不可變動地圖，會使用非破壞性元素加入方法 +，而不是 += 方法。集合的工作方式相同。
不過，在所有這些情況中，若要建立正確類型的集合，您需要從該類型的空集合開始。這是由 empty 方法提供的，它是 PrefixMap 中定義的最後一個方法。此方法只會傳回一個新的 PrefixMap。
前綴地圖的伴隨物件
import scala.collection.mutable.{Builder, MapBuilder}
import scala.collection.generic.CanBuildFrom
object PrefixMap extends {
def empty[T] = new PrefixMap[T]
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]
}
}
我們現在將轉到伴隨物件 PrefixMap。事實上，定義這個伴隨物件並非絕對必要，因為類別 PrefixMap 本身就能獨立存在。物件 PrefixMap 的主要目的是定義一些方便的工廠方法。它也定義了一個 CanBuildFrom 隱式函數，以讓輸入的類型運作得更好。
這兩個方便的方法是 empty 和 apply。Scala 的收集架構中所有其他收集都存在相同的方法，因此在此定義它們也很合理。有了這兩個方法，你可以撰寫 PrefixMap 文字，就像你對任何其他收集所做的那樣
scala> PrefixMap("hello" -> 5, "hi" -> 2)
res0: PrefixMap[Int] = Map(hello -> 5, hi -> 2)
scala> PrefixMap.empty[String]
res2: PrefixMap[String] = Map()
物件 PrefixMap 中的另一個成員是一個隱式的 CanBuildFrom 執行個體。它與 RNA 伴隨物件 中的 CanBuildFrom 定義有相同目的，也就是讓 map 等方法回傳最佳的可能類型。例如，考慮將一個函數對應到 PrefixMap 的鍵/值對。只要該函數產生字串對和某些第二種類型，結果收集就會再次成為 PrefixMap。以下是一個範例
scala> res0 map { case (k, v) => (k + "!", "x" * v) }
res8: PrefixMap[String] = Map(hello! -> xxxxx, hi! -> xx)
給定的函數引數會取得前綴映射 res0 的鍵值繫結，並產生字串對。 map 的結果是 PrefixMap，這次值類型為 String，而非 Int。若沒有 PrefixMap 中隱含的 canBuildFrom，結果只會是一般可變動映射，而非前綴映射。為方便起見， PrefixMap 物件定義了 newBuilder 方法，但它仍只使用預設 MapBuilder。
摘要
總之，如果您想將新的集合類別完全整合到架構中，您需要留意下列幾點
- 決定集合是可變動還是不可變動。
- 為集合挑選正確的基本特質。
- 繼承自正確的實作特質，以實作大部分的集合操作。
- 如果您希望
map和類似的操作傳回集合類型的執行個體，請在類別的伴隨物件中提供隱含CanBuildFrom。
您現在已經了解 Scala 的集合是如何建構的，以及如何新增新的集合類型。由於 Scala 豐富的抽象支援，每個新的集合類型都有大量的函式，而不需要重新實作所有函式。
致謝
這些頁面包含改編自 Odersky、Spoon 和 Venners 所著的 Programming in Scala 第 2 版的資料。我們感謝 Artima 慷慨同意我們發表此資料。