Scala列表拼接，::: vs ++

Question

:::和++在Scala中连接列表是否有区别？

scala> List(1,2,3) ++ List(4,5)
res0: List[Int] = List(1, 2, 3, 4, 5)

scala> List(1,2,3) ::: List(4,5)
res1: List[Int] = List(1, 2, 3, 4, 5)

scala> res0 == res1
res2: Boolean = true

根据文档，看起来++更通用，而:::则更专门为List设计。后者是否提供是因为它在其他函数式语言中被使用了吗？

- Luigi Plinge

---

::: 也是一个前缀操作符，就像所有以 : 开头的方法一样。 - Ben Jackson

这些回答基本上勾勒出了Scala是如何围绕列表和运算符统一性（或缺乏后者）而发展的。很遗憾，一个如此简单的东西会有这么长的琐碎细节，会让任何学习Scala的人感到困惑和浪费时间。我希望在2.12版本中可以解决这个问题。 - matanster

Answer 1

遗留问题。List 最初被定义成函数式语言的样子：

1 :: 2 :: Nil // a list
list1 ::: list2  // concatenation of two lists

list match {
  case head :: tail => "non-empty"
  case Nil          => "empty"
}

当然，Scala还以临时的方式演进出其他集合类型。在2.8版发布时，集合被重新设计为最大程度地重用代码并保持一致的API，因此您可以使用 ++ 来连接任何两个集合 - 甚至是迭代器。但是，List保留了其原始运算符，除了不再建议使用其中的一两个。

- Daniel C. Sobral

---

现在是不是最佳实践是避免使用 ::: 而改用 ++？同时使用 +: 代替 ::？ - Luigi Plinge

由于模式匹配（参见丹尼尔的第二个示例），::非常有用。使用 +: 无法完成这项任务。 - paradigmatic

我认为同时拥有列表惯用操作（如::和:::）和其他集合通用操作是很好的。我不会从语言中删除任何一个操作。 - Giorgio

Scala 2.10拥有: +和: +对象提取器。 - 0__

@samthebest 你可以在模式匹配中使用 +:。除非你有审美偏好，否则在模式匹配或其他地方使用 :: 没有任何理由。 - lutzh

Answer 2

始终使用:::。有两个原因：效率和类型安全。

效率

x ::: y ::: z比x ++ y ++ z更快，因为:::是右结合的。 x ::: y ::: z被解析为x ::: (y ::: z)，这比(x ::: y) ::: z算法上更快（后者需要O（|x|）更多步骤）。

类型安全

使用:::，您只能将两个List连接起来。而使用++，可以将任何集合附加到List，这非常糟糕：

scala> List(1, 2, 3) ++ "ab"
res0: List[AnyVal] = List(1, 2, 3, a, b)

++ 也很容易与 + 搞混：

scala> List(1, 2, 3) + "ab"
res1: String = List(1, 2, 3)ab

- ZhekaKozlov

---

当连接两个列表时，没有区别，但是在连接三个或更多列表时，你的观点是正确的，并且我通过快速基准测试进行了确认。然而，如果你担心效率问题，应该将 x:::y:::z 替换为 List(x, y, z).flatten。http://pastebin.com/gkx7Hpad - Luigi Plinge

左结合串联需要更多的O(x)步骤是因为在左结合中，需要对每个字符串进行顺序拼接，而右结合串联只需要将两个字符串连接起来。虽然这两种操作在大O表示法下都为O(1)，但左结合串联需要更多的操作来完成整个字符串的拼接过程。 - pacman

列表是单向链接的，如果要将一个列表附加到另一个列表上，则需要复制第一个列表，并在结尾处附加第二个列表。因此，相对于第一个列表中元素的数量，连接操作的时间复杂度为O(n)。第二个列表的长度不影响运行时间，所以最好将长列表附加到短列表而不是将短列表附加到长列表。 - puhlen

@pacman Scala的列表是不可变的。这就是为什么我们在进行连接时不能仅仅替换最后一个链接。我们必须从头开始创建一个新的列表。 - ZhekaKozlov

@pacman 复杂度始终与 x 和 y 的长度成线性关系（在任何情况下都不会迭代 z，因此对运行时间没有影响，这就是为什么将长列表附加到短列表比反过来更好的原因）。但渐进复杂度并不能说明全部情况。x ::: (y ::: z) 迭代 y 并附加 z，然后迭代 x 并附加 y ::: z 的结果。x 和 y 都被迭代一次。(x ::: y) ::: z 迭代 x 并附加 y，然后迭代 x ::: y 的结果并附加 z。y 仍然被迭代一次，但在这种情况下 x 被迭代两次。 - puhlen

Answer 3

::: 仅适用于列表，而++ 可用于任何可遍历对象。在当前2.9.0版本的实现中，如果参数也是一个List， ++ 会回退到:::。

- paradigmatic

---

使用 ::: 和 ++ 操作符处理列表非常简单，但这可能会在代码/风格上造成混乱。 - ses

Answer 4

一个不同的观点是，第一句话被解析为：

scala> List(1,2,3).++(List(4,5))
res0: List[Int] = List(1, 2, 3, 4, 5)

第二个示例将被解析为:

scala> List(4,5).:::(List(1,2,3))
res1: List[Int] = List(1, 2, 3, 4, 5)

如果您正在使用宏，那么您应该小心。

此外，对于两个列表的++操作会调用:::，但是由于它要求从List到List的构建器具有隐式值，因此会增加更多开销。但是微基准测试没有证明任何有用的东西，我想编译器会优化这种调用。

在预热后进行微基准测试。

scala>def time(a: => Unit): Long = { val t = System.currentTimeMillis; a; System.currentTimeMillis - t}
scala>def average(a: () => Long) = (for(i<-1 to 100) yield a()).sum/100

scala>average (() => time { (List[Int]() /: (1 to 1000)) { case (l, e) => l ++ List(e) } })
res1: Long = 46
scala>average (() => time { (List[Int]() /: (1 to 1000)) { case (l, e) => l ::: List(e ) } })
res2: Long = 46

正如Daniel C. Sobrai所说，您可以使用++将任何集合的内容附加到列表中，而使用:::只能连接列表。

- Mikaël Mayer

---

请提供您不是过于简单的微基准测试，我会投票支持它们。 - Mikaël Mayer