Concatenação da lista Scala, ::: vs ++

362

Existe alguma diferença entre :::e ++para concatenar listas no 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

A partir da documentação , parece ++ser mais geral, enquanto :::é Listespecífico. O último é fornecido porque é usado em outras linguagens funcionais?

list scala concatenation Luigi Plinge
fonte
4
Também :::é um operador de prefixo, como todos os métodos iniciados com:
Ben Jackson
3
As respostas delineiam a maneira como o scala foi desenvolvido em torno das listas e da uniformidade do operador no Scala (ou a falta deste último). É um pouco lamentável que algo tão simples tenha uma longa cauda de minúcias para confundir e desperdiçar o tempo de qualquer aluno do Scala. Eu gostaria que fosse nivelado em 2.12.
matanster

Respostas:

321

Legado. A lista foi originalmente definida para aparência de idiomas funcionais:

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

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

Obviamente, Scala desenvolveu outras coleções, de maneira ad-hoc. Quando o 2.8 foi lançado, as coleções foram redesenhadas para reutilização máxima de código e API consistente, para que você possa usar ++para concatenar quaisquer duas coleções - e até iteradores. A List, no entanto, conseguiu manter seus operadores originais, além de um ou dois que foram preteridos.

Daniel C. Sobral
fonte
19
Então, é uma prática recomendada evitar o :::favor do ++agora? Também use em +:vez de ::?
Luigi Plinge
37
::é útil devido à correspondência de padrões (consulte o segundo exemplo de Daniel). Você não pode fazer isso com+:
paradigmático
11
@ Luigi Se você estiver usando em Listvez de Seq, também poderá usar Listmétodos idiomáticos . Por outro lado, dificultará a mudança para outro tipo, se você desejar fazer isso.
Daniel C. Sobral
2
Acho bom que você tenha operações idiomáticas da lista (como ::e :::) e operações mais gerais que são comuns a outras coleções. Eu não abandonaria nenhuma das operações do idioma.
Giorgio
21
@paradigmatic Scala 2.10 possui extratores :+e +:objetos.
0__
97

Sempre use :::. Há duas razões: eficiência e segurança do tipo.

Eficiência

x ::: y ::: zé mais rápido que x ++ y ++ z, porque :::é associativo correto. x ::: y ::: zé analisado como x ::: (y ::: z), o que é algoritmicamente mais rápido que (x ::: y) ::: z(o último requer O (| x |) mais etapas).

Digite segurança

Com :::você só pode concatenar dois Lists. Com ++você, você pode anexar qualquer coleção a List, o que é terrível:

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

++Também é fácil misturar-se com +:

scala> List(1, 2, 3) + "ab"
res1: String = List(1, 2, 3)ab
ZhekaKozlov
fonte
9
Ao concatenar apenas 2 listas, não há diferença, mas no caso de 3 ou mais, você tem um bom argumento, e eu o confirmei com uma referência rápida. No entanto, se você estiver preocupado com eficiência, x ::: y ::: zdeve ser substituído por List(x, y, z).flatten. pastebin.com/gkx7Hpad
Luigi Plinge
3
Por favor, explique por que a concatenação associativa esquerda requer mais etapas de O (x). Eu pensei que os dois trabalham para O (1).
Pacman
6
As listas do @pacman são vinculadas individualmente; para anexar uma lista à outra, é necessário fazer uma cópia da primeira lista que possui a segunda no final. A concatenação é, portanto, O (n) com relação ao número de elementos na primeira lista. O comprimento da segunda lista não afeta o tempo de execução, portanto, é melhor anexar uma lista longa a uma curta, em vez de anexar uma lista curta a uma longa.
puhlen
11
As listas de @pacman Scala são imutáveis . É por isso que não podemos apenas substituir o último link ao concatenar. Nós devemos criar uma nova lista do zero.
ZhekaKozlov
4
@pacman A complexidade é sempre linear em relação ao comprimento xe y( znunca é iterada em nenhum caso; portanto, não afeta o tempo de execução, é por isso que é melhor anexar uma lista longa a uma curta, do que o contrário), mas complexidade assintótica não conta a história toda. x ::: (y ::: z)itera ye acrescenta z, depois itera xe acrescenta o resultado de y ::: z. xe ysão iterados uma vez. (x ::: y) ::: zitera xe acrescenta y, depois itera o resultado de x ::: ye acrescenta z. yainda é iterado uma vez, mas xé iterado duas vezes neste caso.
puhlen
84

:::funciona apenas com listas, enquanto ++pode ser usado com qualquer travável. Na implementação atual (2.9.0), ++recai novamente :::se o argumento também for a List.

paradigmático
fonte
4
Portanto, é muito fácil usar os arquivos ::: e ++ trabalhando com a lista. Isso potencialmente pode colocar uma bagunça no código / estilo.
S28 /
24

Um ponto diferente é que a primeira frase é analisada como:

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

Enquanto o segundo exemplo é analisado como:

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

Portanto, se você estiver usando macros, tome cuidado.

Além disso, ++para duas listas está chamando, :::mas com mais sobrecarga porque está solicitando um valor implícito para ter um construtor de Lista para Lista. Mas as marcas de microbench não provaram nada de útil nesse sentido, acho que o compilador otimiza essas chamadas.

Micro-benchmarks após o aquecimento.

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

Como Daniel C. Sobrai disse, você pode anexar o conteúdo de qualquer coleção a uma lista usando ++, enquanto que :::você só pode concatenar listas.

Mikaël Mayer
fonte
20
Por favor, poste suas marcas não muito simplistas e eu votarei nelas.
Mikaël Mayer 12/05