Por que anexar a uma lista em Scala tem complexidade de tempo O (n)?

Acabei de ler que o tempo de execução da operação de acréscimo para a List(: +) cresce linearmente com o tamanho da List.

Anexar a um Listparece ser uma operação bastante comum. Por que a maneira idiomática de fazer isso é preceder os componentes e depois reverter a lista? Também não pode ser uma falha de design, pois a implementação pode ser alterada a qualquer momento.

Do meu ponto de vista, tanto o anexo quanto o anexo devem ser O (1).

Existe alguma razão legítima para isso?

Vou expandir um pouco meu comentário. A List[T]estrutura de dados, from scala.collection.immutableé otimizada para funcionar da mesma maneira que uma lista imutável em uma linguagem de programação mais puramente funcional. Tem tempos de pré-inserção muito rápidos , e supõe-se que você estará trabalhando na cabeça por quase todo o seu acesso.

As listas imutáveis ​​passam a ter tempos de pré-inserção muito rápidos, devido ao fato de modelarem suas listas vinculadas como uma série de "células contras". A célula define um valor único e um ponteiro para a próxima célula (estilo clássico de lista vinculada individual):

Cell [Value| -> Nil]

Quando você anexa uma lista, na verdade você está apenas criando uma única célula nova, com o restante da lista existente sendo apontado:

Cell [NewValue| -> [Cell[Value| -> Nil]]

Como a lista é imutável, você pode fazer isso sem nenhuma cópia real . Não há perigo de a lista antiga mudar e fazer com que todos os valores em sua nova lista se tornem inválidos. No entanto, você perde a capacidade de ter um ponteiro mutável para o final da sua lista como um compromisso.

Isso se presta muito bem ao trabalho recursivo em listas. Digamos que você definiu sua própria versão de filter:

def deleteIf[T](list : List[T])(f : T => Boolean): List[T] = list match {
  case Nil => Nil
  case (x::xs) => f(x) match {
    case true => deleteIf(xs)(f)
    case false => x :: deleteIf(xs)(f)
  }
}

Essa é uma função recursiva que trabalha exclusivamente a partir da cabeça da lista e aproveita a correspondência de padrões por meio do extrator ::. Isso é algo que você vê muito em idiomas como Haskell.

Se você realmente deseja anexos rápidos, o Scala fornece várias estruturas de dados mutáveis ​​e imutáveis ​​para você escolher. No lado mutável, você pode investigar ListBuffer. Como alternativa, Vectorfrom scala.collection.immutabletem um tempo de acréscimo rápido.