Конкатенация списка Scala, ::: vs ++

362

Есть ли разница между :::и ++для объединения списков в 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-специфичный. Предоставляется ли последний, потому что он используется в других функциональных языках?

Луиджи Плинге
источник
4
Также :::является префиксным оператором, как и все методы, начинающиеся с:
Бен Джексон
3
Ответы в значительной степени очерчивают способ эволюции scala вокруг списков и единообразия операторов в Scala (или его отсутствия). Немного прискорбно, что у чего-то такого простого есть такой длинный хвост мелочей, чтобы запутать и потратить время любого ученика Scala. Я хотел бы, чтобы это было выровнено в 2.12.
matanster

Ответы:

321

Наследие. Первоначально список был определен как выглядящий на функциональных языках:

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, так что вы можете использовать их ++для объединения любых двух коллекций - и даже итераторов. Список, однако, должен сохранить свои оригинальные операторы, кроме одного или двух, которые устарели.

Даниэль С. Собрал
источник
19
Так лучше ли сейчас избегать :::в пользу ++? Также используйте +:вместо ::?
Луиджи Плиндж
37
::полезно из-за сопоставления с образцом (см. второй пример Дэниела). Вы не можете сделать это с+:
парадигматическим
1
@Luigi Если вы используете Listвместо Seq, вы можете использовать идиоматические Listметоды. С другой стороны, будет сложнее перейти на другой тип, если вы когда-нибудь захотите это сделать.
Даниэль С. Собрал
2
Я считаю, что хорошо, что есть и идиоматические операции со списком (например, ::и :::), и более общие операции, которые являются общими для других коллекций. Я бы не бросил ни одну операцию из языка.
Джорджио
21
@paradigmatic Scala 2.10 имеет :+и +:экстракторы объектов.
0
97

Всегда используйте :::. Есть две причины: эффективность и безопасность типов.

КПД

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
источник
9
При объединении только 2 списков нет никакой разницы, но в случае 3 или более у вас есть хорошая точка зрения, и я подтвердил это быстрым тестом. Однако, если вы беспокоитесь об эффективности, x ::: y ::: zследует заменить на List(x, y, z).flatten. pastebin.com/gkx7Hpad
Луиджи Плиндж
3
Пожалуйста, объясните, почему левая ассоциативная конкатенация требует больше O (x) шагов. Я думал, что они оба работают на O (1).
pacman
6
@pacman Списки связаны по отдельности, чтобы добавить один список в другой, вам нужно сделать копию первого списка, в конце которого прикреплен второй. Следовательно, конкатенация равна O (n) относительно количества элементов в первом списке. Длина второго списка не влияет на время выполнения, поэтому лучше добавлять длинный список в короткий, а не добавлять короткий в длинный.
Пухлен
1
Списки @pacman Scala неизменны . Вот почему мы не можем просто заменить последнюю ссылку при выполнении конкатенации. Мы должны создать новый список с нуля.
Жека Козлов,
4
@pacman Сложность всегда линейна относительно длины xи y( zникогда не повторяется ни в коем случае, поэтому не влияет на время выполнения, поэтому лучше добавлять длинный список в короткий, чем наоборот), но асимптотическая сложность не рассказывает всей истории. x ::: (y ::: z)повторяет yи добавляет z, затем повторяет xи добавляет результат y ::: z. xи yоба повторяются один раз. (x ::: y) ::: zповторяет xи добавляет y, затем повторяет результат x ::: yи добавляет z. yвсе еще повторяется один раз, но xповторяется дважды в этом случае.
Пухлен
84

:::работает только со списками, в то время как ++может использоваться с любым перемещаемым. В текущей реализации (2.9.0) ++возвращается значение, :::если аргумент также является List.

образцовый
источник
4
Так что очень легко использовать и ::: и ++, работая со списком. Это потенциально может привести к путанице в коде / стиле.
ses
24

Другое дело, что первое предложение анализируется как:

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)

Поэтому, если вы используете макросы, вам следует позаботиться.

Кроме того, ++для двух списков вызывается, :::но с большими накладными расходами, потому что он запрашивает неявное значение для построения компоновщика из списка в список. Но микробенчмарки не доказали ничего полезного в этом смысле, я думаю, что компилятор оптимизирует такие вызовы.

Микро-эталоны после прогрева.

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

Как сказал Даниэль С. Собрай, вы можете добавлять содержимое любой коллекции в список, используя ++, тогда как :::вы можете только объединять списки.

Микаэль Майер
источник
20
Пожалуйста, опубликуйте свои не слишком упрощенные микробенчмарки, и я буду голосовать за них.
Микаэль Майер