如何确保在map()期间保留自定义Scala集合的动态类型？

Question

我阅读了非常有趣的article on the architecture of the Scala 2.8 collections，并且一直在尝试它。首先，我简单地复制了很好的RNA示例的最终代码。这里有一个参考：

abstract class Base
case object A extends Base
case object T extends Base
case object G extends Base
case object U extends Base

object Base {
  val fromInt: Int => Base = Array(A, T, G, U)
  val toInt: Base => Int = Map(A -> 0, T -> 1, G -> 2, U -> 3)
}

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
    }
  }
}

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
    }
}

现在，我的问题来了。如果我运行这个，一切都很好：

val rna = RNA(A, G, T, U)
println(rna.map(e => e)) // prints RNA(A, G, T, U)

但是这段代码将RNA转换为Vector！

val rna: IndexedSeq[Base] = RNA(A, G, T, U)
println(rna.map(e => e)) // prints Vector(A, G, T, U)

这是一个问题，因为当仅从RNA映射到Vector时，不知道Base类的客户端代码可能会将其转换回Base。为什么会这样，有什么方法可以修复它？

附言:我已经找到了一个初步的答案(见下文)，如果我错了，请纠正我。

Answer 1

如果rna变量的静态类型为IndexedSeq[Base]，则自动插入的CanBuildFrom不能是RNA伴生对象中定义的类型，因为编译器不应该知道rna是RNA的实例。

那么它是从哪里来的呢？编译器依赖于IndexedSeq对象中定义的GenericCanBuildFrom实例。GenericCanBuildFrom通过在原始集合上调用genericBuilder[B]来生成它们的构建器，并且对该泛型构建器的一个要求是，它可以生成可以包含任何类型B的泛型集合-当然，传递给map()的函数的返回类型不受约束。

在这种情况下，RNA只是一个IndexedSeq[Base]，而不是一个通用的IndexedSeq，所以不可能在RNA中重写genericBuilder[B]来返回一个RNA-specific构建器-我们必须在运行时检查B是否为Base或其他值，但我们不能这样做。

我想这就解释了为什么在这个问题中，我们会得到一个Vector。至于我们如何修复它，这是一个悬而未决的问题，…

编辑：修复这个问题需要map()知道它是否映射到A的子类型。要实现这一点，需要在收藏库中进行重大改变。请参阅相关问题Should Scala's map() behave differently when mapping to the same type?。

Answer 2

关于为什么我认为静态键入比RNA弱的类型不是一个好主意。它真的应该是一个评论(因为它更多的是一个观点，但这会更难读懂)。从你的评论到我的评论：

有何不可？根据利斯科夫替换原理，作为IndexedSeqBase的一个子类，RNA可以做IndexedSeqBase做的所有事情。有时，你只知道它是一个IndexedSeq，而你仍然希望过滤器、地图和朋友保持相同的具体实现。实际上，filter可以做到这一点，但不能映射

filter这样做是因为编译器可以静态地保证它。如果保留特定集合中的元素，则最终会得到相同类型的集合。map不能保证这一点，它取决于传递的函数。

我的观点更多的是显式地指定一个类型，并期望它能提供更多的东西。作为RNA集合的用户，我可能会编写依赖于该集合的某些属性的代码，例如高效的内存表示。

因此，假设我在val rna: IndexedSeq[Base]中声明rna只是一个IndexedSeq。几行之后，我调用了一个方法doSomething(rna)，其中我希望得到有效的内存表示，那么最好的签名是什么？def doSomething[T](rna: IndexedSeq[Base]): T或def doSomething[T](rna: RNA): T

我认为应该是后者。但是如果是这种情况，那么代码将无法编译，因为rna不是静态的RNA对象。如果方法签名应该是前者，那么从本质上说，我并不关心内存表示的效率。因此，我认为显式指定较弱的类型但期望更强的行为的行为是矛盾的。这就是您在示例中所做的。

现在我明白了，即使我这么做了：

val rna = RNA(A, G, T, U)
val rna2 = doSomething(rna)

其他人写道：

def doSomething[U](seq: IndexedSeq[U]) = seq.map(identity)

我希望让rna2成为RNA对象，但这不会发生……这意味着，如果其他人想让调用者获得更具体的类型，就应该编写一个接受CanBuildFrom的方法：

def doSomething[U, To](seq: IndexedSeq[U])
   (implicit cbf: CanBuildFrom[IndexedSeq[U], U, To]) = seq.map(identity)(cbf)

然后我可以调用：val rna2: RNA = doSomething(rna)(collection.breakOut)