Scala 源代码：如何理解 zipWithIndex
Scala Source Code: How to understand zipWithIndex
我想实现我的自定义函数 minWithIndex，所以我研究了 scala library 中的 zipWithIndex 函数。
我无法理解。
我知道这个函数是做什么的，但不知道它是怎么做到的。
提前致谢
def zipWithIndex[A1 >: A, That](implicit bf: CanBuildFrom[Repr, (A1, Int), That]): That = {
val b = bf(repr)
var i = 0
for (x <- this) {
b += ((x, i))
i += 1
}
b.result()
}
我看到 scala 有时在内部使用可变解决方案。与他们对 zipWithIndex 的实现相同。
基本上是:
- 遍历集合（
for 循环）
- 为每个元素创建 tuple
(a, Int) 和
- 将它们附加到可变可变缓冲区 (
b += ((x, i)))
因此，对于输入 List("first", "second")，您在 zipWithIndex 之后得到 List(("first", 1), ("second", 2))。
scala> List("first", "second").zipWithIndex
res3: List[(String, Int)] = List((first,0), (second,1))
您可以使用具有不变性的递归方法解决相同的问题，
object MyZippedCollection {
def main(args: Array[String]): Unit = {
def zipWithIndex[a](list: List[a]): List[(a, Int)] = {
def zipWith(index: Int, acc: List[(a, Int)], list: List[a]): List[(a, Int)] = {
if (list.isEmpty) acc
else zipWith(index + 1, acc :+ (list.head, index), list.tail)
}
zipWith(0, List.empty[(a, Int)], list)
}
val myList = List("scala", "fp", "haskell")
zipWithIndex(myList).foreach { case (value, index) =>
println(s"[$index]: $value")
}
}
}
您的问题看起来实际上是两个不同的问题：
Scala 标准库 collection 是如何设计的，特别是 zipWithIndex 是如何工作的？
如何实现我的自定义minWithIndex？
不幸的是，第一个问题可能比第二个问题更复杂。
Scala collection 的设计
从 2.12 版开始，当前 scala.collection 设计得非常灵活，但它需要使用许多高级功能 and/or 设计模式。还有人可能会争辩说 over-engineered 用于 real-world 用法，因此对于 Scala 新手来说很难理解。
设计 collection 的库是一个众所周知的难题，因为理想情况下您想要捕捉许多不同的方面。最主要的是您可能希望捕获尽可能多的方面，但同时尽可能少地重复代码。 （例如，考虑 linked-list 与 array-based 列表。两者可能都应该有像 indexOf 这样的方法，可以根据 size 和 getByIndex 来实现，所以理想情况下你我希望这里只有一个实现。）这是一个真正的设计挑战。
这里是影响 Scala collection 设计的 non-exhaustive 列表（您可能还会在早期 (2.8) 版本 here 上找到一些设计说明）：
实现相似事物的不同数据结构的统一接口（例如 linked-list 与 array-based 列表非常相似，而 linked-list 与 tree-based set 不太相似，但仍然有一些共同点）。这就是 Seq 或 GenTraversableLike 等各种特征和深继承层次结构的原因。
Type-safety。我们希望整数列表与字符串列表的类型不同。我们想知道存储元素的类型。这就是为什么所有 collection 都是通用的。
性能。在每种语言中，标准 collection 都是最常用的代码片段之一，因此良好的性能非常重要。这就是为什么在几个地方存在纯不可变 FP 接口的“不纯”可变实现的原因。
将 read-only 和可变 collection 分开（在 FP-languages 中尤其重要，但在其他方面也一样）。这就是为什么有 scala.collection、scala.collection.mutable 和 scala.collection.immutable 包的原因。
支持潜在的无限序列，例如生成的（斐波那契数列）或来自外部源（例如从控制台输入读取的字节序列）。这就是 TraversableOnce 或 Iterable.
之类的原因
支持不能（轻易）处理两次的序列。例如，一些主要证券交易所的所有交易流非常庞大，无法存储 re-processed。这就是 TraversableOnce 与 Traversable
的原因
内部迭代与外部迭代（这是Iterable与Traversable之间分离的原因）
急切计算与惰性计算（这就是“View”后缀类型的原因）
支持 collection-like object 而非 collection。例如，您正在实施 HTML-parser 甚至浏览器。许多 HTML-elements 可以有 children 但成为 children 的 collection 不是主要责任。这就是带有“Gen”前缀的各种特征的原因。
现在让我们回到zipWithIndex。这是对设计者提出额外挑战的众多方法之一（其他类似方法有 map、fitler 和许多其他方法）：这些方法从当前方法产生新的 collection。一方面，这样的方法可以为所有 collection 通用地实现一次，另一方面，如果采用天真的实现，我们将丢失特定类型，更糟糕的是，我们可能被迫更改实现，从而可能更改语义。考虑一下 filter 方法的这个简单实现：
trait Iterable[A] {
def filter(p: A => Boolean): ? = {
var res: List[A] = Nil
for (x <- this)
if (p(x)) res = x :: res
res
}
}
要输入什么 return 类型而不是 ?？如果我们只输入 Iterable[A] 就意味着我们立即失去了使用 Iterable 中不可用的 List 中所有方法的能力（例如通过索引访问）。但另一件事是，如果我们的 Iterable 实际上是 Set 会怎样。我们可能希望 filter 的结果再次成为 Set 而不是 List。这就是参考上面文章所说的“same-result-type原理”的东西。 Scala 是为数不多的语言之一，它允许您以最少的代码重复为这个问题设计一个优雅的解决方案。主要思想是为每个实现（例如 Iterable and immutable.List) and also a companion trait for each intermediate trait (for example SeqFactory 提供一个伴侣 object。这些伴侣提供的关键内容之一是能够创建 new “相同”的实例 collection（可能具有不同的通用类型）。
引用文章中最后没有涉及的是 CanBuildFrom 隐式参数。它背后的逻辑如下：假设你有一个linked-list (List) 并希望有一个 array-based 列表 (Vector) 用索引压缩。您是否必须在此过程中创建一个带有索引的中间 linked-list 压缩？ CanBuildFrom 是让答案成为：不，你不必这样做的技巧。隐式参数是 Scala 的一个相当高级的特性，如果您还不熟悉，您可能应该阅读更多关于它的内容。这个想法是编译器可以自动搜索匹配类型的参数。因此，如果有任何值与范围内的类型相匹配，代码就会编译。这意味着 CanBuildFrom 的存在可以作为 证据 你可以在你做一些事情的同时改变 collection 的底层数据结构数据操作（zipWithIndex、map、filter 等）。每个伴随 object 提供具有相同目标数据结构的默认 CanBuildFrom 值（例如参见 [=85=]）。
所以现在我们可以看到 IterableLike.zipWithIndex，这是所有子类型的默认实现，是如何实现的
def zipWithIndex[A1 >: A, That](implicit bf: CanBuildFrom[Repr, (A1, Int), That]): That = {
val b = bf(repr)
var i = 0
for (x <- this) {
b += ((x, i))
i += 1
}
b.result()
}
签名说使用 zipWithIndex 可以将 A 的 collection Repr 转换为 That - collection 元组(A1, Int)只要
A1 是 A 的超类型（这是一个安全的向上转换）- 您有证据表明您可以从
Repr（bf object） 构建 That
该方法的作用是请求 bf 证据来创建 b - 一个新的 Builder[(A1, Int), That]，然后用元组填充构建器，最后 return来自构建器 (b.result()) 的 That collection。构建器和 for 与 var i 都用于性能原因。
如何实现自己的 minWithIndex
答案取决于您希望它有多通用以及性能对您有多重要。以下是一些选项：
implicit class MinWithIndexOps[A, Repr <: IterableLike[A, Repr]](it: IterableLike[A, Repr]) {
def minWithIndexWithZip[B >: A](implicit cmp: Ordering[B], bf: CanBuildFrom[Repr, (A, Int), Iterable[(A, Int)]]): (A, Int) = it.zipWithIndex(bf).min(Ordering.by[(A, Int), B]((kv: (A, Int)) => kv._1))
def minWithIndexWithFold[B >: A](implicit cmp: Ordering[B]): (A, Int) = {
if (it.isEmpty)
throw new UnsupportedOperationException("empty.min")
val h = it.head
val res = it.foldLeft((h, 0, 0))((acc, cur) => acc match {
case (minVal, minIndex, curIndex) => if (cmp.lteq(minVal, cur)) (minVal, minIndex, curIndex + 1) else (cur, curIndex, curIndex + 1)
})
(res._1, res._2)
}
def minWithIndexWithVars[B >: A](implicit cmp: Ordering[B]): (A, Int) = {
if (it.isEmpty)
throw new UnsupportedOperationException("empty.min")
var minVal = it.head
var minIndex = 0
var i = 0
for (cur <- it) {
if (cmp.gt(minVal, cur)) {
minVal = cur
minIndex = i
}
i += 1
}
(minVal, minIndex)
}
}
def test(): Unit = {
val data = "qwerty" :: "asdfg" :: "zxcvb" :: Nil
println(data.minWithIndexWithZip)
println(data.minWithIndexWithFold)
println(data.minWithIndexWithVars)
}
请注意，此处的 implicit 关键字用于创建一个 implicit class 的不同含义，该 implicit class 使用新方法有效地扩展了 IterableLike 的每个实例。
第一个实现 minWithIndexWithZip 非常简单但可能非常低效：你实际上首先执行 zipWithIndex 然后调用 min（还要注意标准 min 使用对于抛出异常而不是 returning Option[A] 的 Scala 约定来说是不寻常的，我在其他实现中使用了相同的语义）。这种方法效率低下，因为您必须创建全新的 collection 才能几乎立即处理掉。
minWithIndexWithFold 是不依赖于 zipWithIndex 而是使用 foldLeft 的不同实现。 fold 同时是一个非常基本和非常通用的操作。此代码的一个好处是它也是不可变的。但正因为如此，它的性能也不好：很多中间累加器 object 几乎会立即创建和处理。
最后一个 minWithIndexWithVars 可能是最不“纯粹”但使用直接 imperative-like 代码的性能最高的版本。
我想实现我的自定义函数 minWithIndex，所以我研究了 scala library 中的 zipWithIndex 函数。 我无法理解。
我知道这个函数是做什么的，但不知道它是怎么做到的。 提前致谢
def zipWithIndex[A1 >: A, That](implicit bf: CanBuildFrom[Repr, (A1, Int), That]): That = {
val b = bf(repr)
var i = 0
for (x <- this) {
b += ((x, i))
i += 1
}
b.result()
}
我看到 scala 有时在内部使用可变解决方案。与他们对 zipWithIndex 的实现相同。
基本上是:
- 遍历集合（
for循环） - 为每个元素创建 tuple
(a, Int)和 - 将它们附加到可变可变缓冲区 (
b += ((x, i)))
因此，对于输入 List("first", "second")，您在 zipWithIndex 之后得到 List(("first", 1), ("second", 2))。
scala> List("first", "second").zipWithIndex
res3: List[(String, Int)] = List((first,0), (second,1))
您可以使用具有不变性的递归方法解决相同的问题，
object MyZippedCollection {
def main(args: Array[String]): Unit = {
def zipWithIndex[a](list: List[a]): List[(a, Int)] = {
def zipWith(index: Int, acc: List[(a, Int)], list: List[a]): List[(a, Int)] = {
if (list.isEmpty) acc
else zipWith(index + 1, acc :+ (list.head, index), list.tail)
}
zipWith(0, List.empty[(a, Int)], list)
}
val myList = List("scala", "fp", "haskell")
zipWithIndex(myList).foreach { case (value, index) =>
println(s"[$index]: $value")
}
}
}
您的问题看起来实际上是两个不同的问题：
Scala 标准库 collection 是如何设计的，特别是
zipWithIndex是如何工作的？如何实现我的自定义
minWithIndex？
不幸的是，第一个问题可能比第二个问题更复杂。
Scala collection 的设计
从 2.12 版开始，当前 scala.collection 设计得非常灵活，但它需要使用许多高级功能 and/or 设计模式。还有人可能会争辩说 over-engineered 用于 real-world 用法，因此对于 Scala 新手来说很难理解。
设计 collection 的库是一个众所周知的难题，因为理想情况下您想要捕捉许多不同的方面。最主要的是您可能希望捕获尽可能多的方面，但同时尽可能少地重复代码。 （例如，考虑 linked-list 与 array-based 列表。两者可能都应该有像 indexOf 这样的方法，可以根据 size 和 getByIndex 来实现，所以理想情况下你我希望这里只有一个实现。）这是一个真正的设计挑战。
这里是影响 Scala collection 设计的 non-exhaustive 列表（您可能还会在早期 (2.8) 版本 here 上找到一些设计说明）：
实现相似事物的不同数据结构的统一接口（例如 linked-list 与 array-based 列表非常相似，而 linked-list 与 tree-based set 不太相似，但仍然有一些共同点）。这就是
Seq或GenTraversableLike等各种特征和深继承层次结构的原因。Type-safety。我们希望整数列表与字符串列表的类型不同。我们想知道存储元素的类型。这就是为什么所有 collection 都是通用的。
性能。在每种语言中，标准 collection 都是最常用的代码片段之一，因此良好的性能非常重要。这就是为什么在几个地方存在纯不可变 FP 接口的“不纯”可变实现的原因。
将 read-only 和可变 collection 分开（在 FP-languages 中尤其重要，但在其他方面也一样）。这就是为什么有
scala.collection、scala.collection.mutable和scala.collection.immutable包的原因。支持潜在的无限序列，例如生成的（斐波那契数列）或来自外部源（例如从控制台输入读取的字节序列）。这就是
之类的原因TraversableOnce或Iterable.支持不能（轻易）处理两次的序列。例如，一些主要证券交易所的所有交易流非常庞大，无法存储 re-processed。这就是
的原因TraversableOnce与Traversable内部迭代与外部迭代（这是
Iterable与Traversable之间分离的原因）急切计算与惰性计算（这就是“View”后缀类型的原因）
支持 collection-like object 而非 collection。例如，您正在实施 HTML-parser 甚至浏览器。许多 HTML-elements 可以有 children 但成为 children 的 collection 不是主要责任。这就是带有“Gen”前缀的各种特征的原因。
现在让我们回到zipWithIndex。这是对设计者提出额外挑战的众多方法之一（其他类似方法有 map、fitler 和许多其他方法）：这些方法从当前方法产生新的 collection。一方面，这样的方法可以为所有 collection 通用地实现一次，另一方面，如果采用天真的实现，我们将丢失特定类型，更糟糕的是，我们可能被迫更改实现，从而可能更改语义。考虑一下 filter 方法的这个简单实现：
trait Iterable[A] {
def filter(p: A => Boolean): ? = {
var res: List[A] = Nil
for (x <- this)
if (p(x)) res = x :: res
res
}
}
要输入什么 return 类型而不是 ?？如果我们只输入 Iterable[A] 就意味着我们立即失去了使用 Iterable 中不可用的 List 中所有方法的能力（例如通过索引访问）。但另一件事是，如果我们的 Iterable 实际上是 Set 会怎样。我们可能希望 filter 的结果再次成为 Set 而不是 List。这就是参考上面文章所说的“same-result-type原理”的东西。 Scala 是为数不多的语言之一，它允许您以最少的代码重复为这个问题设计一个优雅的解决方案。主要思想是为每个实现（例如 Iterable and immutable.List) and also a companion trait for each intermediate trait (for example SeqFactory 提供一个伴侣 object。这些伴侣提供的关键内容之一是能够创建 new “相同”的实例 collection（可能具有不同的通用类型）。
引用文章中最后没有涉及的是 CanBuildFrom 隐式参数。它背后的逻辑如下：假设你有一个linked-list (List) 并希望有一个 array-based 列表 (Vector) 用索引压缩。您是否必须在此过程中创建一个带有索引的中间 linked-list 压缩？ CanBuildFrom 是让答案成为：不，你不必这样做的技巧。隐式参数是 Scala 的一个相当高级的特性，如果您还不熟悉，您可能应该阅读更多关于它的内容。这个想法是编译器可以自动搜索匹配类型的参数。因此，如果有任何值与范围内的类型相匹配，代码就会编译。这意味着 CanBuildFrom 的存在可以作为 证据 你可以在你做一些事情的同时改变 collection 的底层数据结构数据操作（zipWithIndex、map、filter 等）。每个伴随 object 提供具有相同目标数据结构的默认 CanBuildFrom 值（例如参见 [=85=]）。
所以现在我们可以看到 IterableLike.zipWithIndex，这是所有子类型的默认实现，是如何实现的
def zipWithIndex[A1 >: A, That](implicit bf: CanBuildFrom[Repr, (A1, Int), That]): That = {
val b = bf(repr)
var i = 0
for (x <- this) {
b += ((x, i))
i += 1
}
b.result()
}
签名说使用 zipWithIndex 可以将 A 的 collection Repr 转换为 That - collection 元组(A1, Int)只要
A1是A的超类型（这是一个安全的向上转换）- 您有证据表明您可以从
Repr（bfobject） 构建
That
该方法的作用是请求 bf 证据来创建 b - 一个新的 Builder[(A1, Int), That]，然后用元组填充构建器，最后 return来自构建器 (b.result()) 的 That collection。构建器和 for 与 var i 都用于性能原因。
如何实现自己的 minWithIndex
答案取决于您希望它有多通用以及性能对您有多重要。以下是一些选项：
implicit class MinWithIndexOps[A, Repr <: IterableLike[A, Repr]](it: IterableLike[A, Repr]) {
def minWithIndexWithZip[B >: A](implicit cmp: Ordering[B], bf: CanBuildFrom[Repr, (A, Int), Iterable[(A, Int)]]): (A, Int) = it.zipWithIndex(bf).min(Ordering.by[(A, Int), B]((kv: (A, Int)) => kv._1))
def minWithIndexWithFold[B >: A](implicit cmp: Ordering[B]): (A, Int) = {
if (it.isEmpty)
throw new UnsupportedOperationException("empty.min")
val h = it.head
val res = it.foldLeft((h, 0, 0))((acc, cur) => acc match {
case (minVal, minIndex, curIndex) => if (cmp.lteq(minVal, cur)) (minVal, minIndex, curIndex + 1) else (cur, curIndex, curIndex + 1)
})
(res._1, res._2)
}
def minWithIndexWithVars[B >: A](implicit cmp: Ordering[B]): (A, Int) = {
if (it.isEmpty)
throw new UnsupportedOperationException("empty.min")
var minVal = it.head
var minIndex = 0
var i = 0
for (cur <- it) {
if (cmp.gt(minVal, cur)) {
minVal = cur
minIndex = i
}
i += 1
}
(minVal, minIndex)
}
}
def test(): Unit = {
val data = "qwerty" :: "asdfg" :: "zxcvb" :: Nil
println(data.minWithIndexWithZip)
println(data.minWithIndexWithFold)
println(data.minWithIndexWithVars)
}
请注意，此处的 implicit 关键字用于创建一个 implicit class 的不同含义，该 implicit class 使用新方法有效地扩展了 IterableLike 的每个实例。
第一个实现 minWithIndexWithZip 非常简单但可能非常低效：你实际上首先执行 zipWithIndex 然后调用 min（还要注意标准 min 使用对于抛出异常而不是 returning Option[A] 的 Scala 约定来说是不寻常的，我在其他实现中使用了相同的语义）。这种方法效率低下，因为您必须创建全新的 collection 才能几乎立即处理掉。
minWithIndexWithFold 是不依赖于 zipWithIndex 而是使用 foldLeft 的不同实现。 fold 同时是一个非常基本和非常通用的操作。此代码的一个好处是它也是不可变的。但正因为如此，它的性能也不好：很多中间累加器 object 几乎会立即创建和处理。
最后一个 minWithIndexWithVars 可能是最不“纯粹”但使用直接 imperative-like 代码的性能最高的版本。