Добавление элементов в неизменяемый список в Scala

Question

В Scala способ добавления элементов в неизменяемый список выглядит следующим образом:

    val l = 1 :: 2 :: Nil
    l: List[Int] = List(1, 2)

Это означает, что вы сначала создаете нулевой (пустой) список, к которому добавляете 2, а затем 1. т. Е. Эти операции связаны справа. Так что, по сути, это может быть переписано более четко, например так:

    val l = (1 :: (2 :: Nil))
    l: List[Int] = List(1, 2)

Вопрос в том, что если List должен сохранять порядок вставки, и если 2 добавляется сначала в пустой список, а затем добавляется 1, то почему ответ не l: List[Int] = List(2, 1)??

Answer 1

Это потому, что элементы добавляются: первый 2 затем 1,

Из определения метода минусов:

  def ::[B >: A] (x: B): List[B] =
    new scala.collection.immutable.::(x, this)

здесь вы можете видеть, что каждый раз, когда новый экземпляр класса дела scala.collection.immutable.:: создано:

case class ::[B](val head: B, var tail: List[B]) extends List[B]

вы просто используете свой новый элемент как head для нового списка и весь предыдущий список как его tail,

Также подготовьте операцию для неизменяемого List занимает постоянное время O(1), append является линейным O(n) (из документов Scala).

Answer 2

Это просто соглашение. Списки - это в основном стеки. Наиболее эффективно получить доступ или изменить недавно добавленные элементы. С таким же успехом можно считать, что заголовок списка обычно является последним пунктом, и в этом случае предложенные вами обозначения будут уместны.

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