prepend 如何保持 List 的不变性，但 append 却没有？

Question

如果我们将一个元素附加到列表中，如何在 Scala 中保持列表的不变性？难道不应该列一个新的清单吗？在java中，如果你添加一个字母作为第一个字符，那么就会创建一个新的String，而在Java中，字符串是不可变的。在 Scala 中追加是线性时间的原因是什么？是遍历整个列表并在末尾添加还是线性的，因为我们需要在更改对象后创建一个全新的列表？

Answer 1

添加和附加到 List 都会产生新的 List，从而保持 List 的不变性。我们可以这样检查

val l = List(1)
l.prepended(0)
l.appended(2)
l             // just has List(1) instead of List(0,1,2)

Prepend 是常量时间，因为它不会复制整个列表。相反，它只是创建一个新对象，该对象包含对新头部的引用和对前一个尾部的引用。

def prepended[B >: A](elem: B): List[B] = elem :: this   // new ::(elem, this)

追加是线性时间，因为它会复制整个列表

def appended[B >: A](elem: B): CC[B] = {
  val b = iterableFactory.newBuilder[B]
  ...
  b ++= this  // copy of the entire list happens here
  b += elem
  b.result()
}

另请注意，检索 List 的最后一个元素是线性时间，因为 List 是作为单链表实现的，因此它不知道对最后一个元素的引用。

针对评论，尽管 new List 被返回，但只要您以前置方式正确使用它，List 可以是一个有效的结构。有时您必须 reverse 最后的列表才能获得所需的顺序，但这是一次性遍历。最终应该始终在特定情况下通过 sbt-jmh 来衡量性能。

还要注意不要将 Array 与 List 混淆。前者并不是真正的 Scala 集合

implicitly[Array[Int] <:< Iterable[Int]] // error

这表明 Array 不是 Scala 集合基类的子类型。 Array 是一个 Java 数组，只有在测量绝对指示它时才应使用它。

prepend 如何保持 List 的不变性，但 append 却没有？

How does prepend preserve immutability of a List but append does not?

scala

immutability