了解GenericTraversableTemplate和其他Scala集合内部

Question

我和一个熟人Kotlin,Clojure和Java8粉丝交换了电子邮件,并问他为什么不是Scala.他提供了很多理由(Scala太学术化,功能太多,不是我第一次听到这个,我认为这是非常主观的)但他最大的痛点就是一个例子,他不喜欢他能用的语言不了解基本数据结构的实现,他给了LinkedList作为例子.

我看了看scala.collection.LinkedList并计算了我理解或有点理解的事情.

• CanBuildFrom - 经过一番努力,我得到它,输入类,而不是历史上最长的遗书[1]
• LinkedListLike - 我不记得我在哪里阅读它,但我确信这是有充分理由的

但后来我开始盯着这些

• GenericTraversableTemplate - 现在我也在摸不着头脑......
• SeqFactory,GenericCompanion - 好的,现在你失去了我,我开始理解他的观点

能够理解这一点的人能解释一下GenericTraversableTemplate SeqFactory并GenericCompanion在LinkedList的上下文中吗？它们的用途是什么,对最终用户有什么影响(例如我确信它们存在的原因很充分,这是什么原因？)

它们是出于实际原因吗？或者它是一个可以简化的抽象层次？

我喜欢Scala集合,因为我不必理解内部能够有效地使用它们.我不介意复杂的实现,如果它帮助我保持我的使用更简单.例如,如果我能够使用它来编写更清晰,更优雅的代码,我不介意支付复杂库的价格.但是更好地理解它肯定会很好.

[1] - Scala 2.8馆藏图书馆是"历史上最长的遗书"吗？

Answer 1

我将尝试从一个随机行人的角度来描述这些概念（我从未向 Scala 集合库贡献过一行代码，所以如果我错了，请不要太严厉地打击我）。

由于LinkedList现在已弃用，并且由于地图提供了更好的示例，因此我将使用它TreeMap作为示例。

可以构建自

动机是这样的：如果我们采用 aTreeMap[Int, Int]并将其映射为

case (x, y) => (2 * x, y * y * 0.3d)

我们得到TreeMap[Int, Double]。仅这种类型安全性就已经解释了简单构造的必要性genericBuilder[X]。但是，如果我们将其映射为

case (x, y) => x

我们得到一个Iterable[Int]（更准确地说：a List[Int]），这不再是一个Map，容器的类型已经改变。这就是 CBF 发挥作用的地方：

CanBuildFrom[This, X, That]

可以看作是一种“类型级函数”，它告诉我们：如果我们将 This 类型的集合映射到一个返回 X 类型值的函数，我们就可以构建一个 That。最具体的 CBF 在编译时提供，在第一种情况下它将类似于

CanBuildFrom[TreeMap[_,_], (X,Y), TreeMap[X,Y]]

在第二种情况下，它会是这样的

CanBuildFrom[TreeMap[_,_], X, Iterable[X]]

所以我们总是能得到正确类型的容器。模式很一般。每当你有一个通用函数时

foo[X1, ..., Xn](x1: X1, ..., xn: Xn): Y 

其中结果类型Y 取决于 X1, ..., Xn，您可以引入隐式参数，如下所示：

foo[X1, ...., Xn, Y](x1: X1, ..., xn: Xn)(implicit CanFooFrom[X1, ..., Xn, Y]): Y

然后通过提供多个隐式 CanFooFrom 分段定义类型级函数 X1, ..., Xn -> Y。

链表类

在类定义中，我们看到这样的内容：

TreeMap[A, B] extends SortedMap[A, B] with SortedMapLike[A, B, TreeMap[A, B]]

这就是Scala表达所谓F-bounded多态性的方式。动机如下：假设我们有十几个（或至少两个......）特质的实现SortedMap[A, B]。现在我们要实现一个方法withoutHead，它可能看起来像这样：

def withoutHead = this.remove(this.head)

如果我们将实现转移到SortedMap[A, B]自身中，我们能做的最好的事情就是：

def withoutHead: SortedMap[A, B] = this.remove(this.head)

但这是我们可以获得的最具体的结果类型吗？不，这太模糊了。TreeMap[A, B]如果原始地图是 a ，我们希望返回TreeMap，并且 CrazySortedLinkedHashMap（或其他......）如果原始地图是 a CrazySortedLinkedHashMap。这就是为什么我们将实现移至SortedMapLike，并为该方法提供以下签名withoutHead：

trait SortedMapLike[A, B, Repr <: SortedMap[A, B]] {
  ...
  def withoutHead: Repr = this.remove(this.head)
}

现在因为TreeMap[A, B]extends SortedMapLike[A, B, TreeMap[A, B]]，结果类型 withoutHead是TreeMap[A,B]。这同样适用CrazySortedLinkedHashMap：我们得到确切的类型。在 Java 中，您必须返回SortedMap[A, B]或重写每个子类中的方法（这对于 Scala 中功能丰富的特征来说是维护噩梦）

通用Traversable模板

类型是：GenericTraversableTemplate[+A, +CC[X] <: GenTraversable[X]]

据我所知，这只是一个提供方法实现的特征，这些方法以某种方式返回具有相同容器类型但可能不同内容类型（例如，，，flatten）的常规集合。transposeunzip

像foldLeft, reduce,之类的东西exists不在这里，因为这些方法只关心内容类型，而不关心容器类型。

类似的东西flatMap不在这里，因为容器类型可以改变（同样是CBF）。

为什么它是一个单独的特征，它存在的根本原因是什么？我不这么认为......可能有可能以不同的方式对无数的方法进行分组。但这只是自然发生的事情：你开始实现一个特征，结果发现它有很多方法。因此，您可以将松散相关的方法分组，并将它们放入 10 个不同的特征中，并使用诸如“GenTraversableTemplate”之类的尴尬名称，然后将它们全部混合到您需要的特征/类中......

通用伴侣

这只是一个抽象类，它实现了大多数集合类的伴生对象所常见的一些基本功能（本质上，它只是实现了非常简单的工厂方法apply(varargs)和empty）。

例如，有一个方法apply采用varargs某种类型 A 并返回类型的集合CC[A]：

Array(1, 2, 3, 4) // calls Array.apply[A](elems: A*) on the companion object
List(1, 2, 3, 4) // same for List

实现非常简单，就是这样：

def apply[A](varargs: A*): CC[A] = {
  val builder = newBuilder[A]
  for (arg <- varargs) builder += arg
  builder.result()
}

这显然对于数组、列表、TreeMap 以及几乎所有其他东西都是一样的，除了像 Bitset 这样的“受约束的不规则集合”。因此，这只是大多数伴生对象的共同祖先类中的常见功能。没什么特别的。

序列工厂

与 GenericCompanion 类似，但这次更专门针对序列。添加一些常见的工厂方法，例如fill()和iterate()等等tabulate()。同样，这里没有什么特别火箭科学的内容......

一些一般性评论

总的来说：我认为人们不应该尝试理解这个库中的每一个特征。相反，人们应该尝试从整体上看待图书馆。总的来说，它有一个非常有趣的架构。在我个人看来，它实际上是一个非常美观的软件，但是人们必须盯着它看很长一段时间（并尝试多次重新实现整个架构模式）才能掌握它。另一方面：例如，CBF 是一种“设计模式”，显然应该在该语言的后继者中消除。整个故事以及隐式 CBF 的范围对我来说仍然像是一场噩梦。但很多事情一开始似乎完全难以理解，而且几乎总是以顿悟结束（这对于 Scala 来说是非常特殊的：对于大多数其他语言来说，这样的斗争通常以“这个作者是一个十足的白痴”的想法结束） 。