0

Since in Scala lists are actually build like (here for List(1,2,3)) this:

[ 1 , [ 2, [ 3 , Nill ] ] ]          // (pseudo-code)

it is more efficient to pretend new elements and that is why :: is right associative (all explained in https://stackoverflow.com/a/1162980/4533188) - to be better readable (here 1 :: 2 :: 3). That answers my question, why it's good to have right association in the first place. But why didn't the designers of Lists simply construct them like

[ Nill , [ 3, [ 2 , 1 ] ] ]          // (pseudo-code)

internally and use conventional left association?

Here in a graphic what my pseudo-code is supposed to mean (since it does not show the "links" of the linked list):

enter image description here

Community
  • 1
  • 1
Make42
  • 12,236
  • 24
  • 79
  • 155
  • 1
    Because traversing the list in front-to-back order would have to either be O(n²) or build an intermediate `reverse` of the list. – sjrd May 03 '16 at 15:09
  • 1
    Your example is invalid (type-wise). Did you mean `[[[Nill, 3], 2], 1]`? – Bergi May 03 '16 at 15:38
  • No, I think I meant, what I wrote. In fact it is an abbreviation, since it should be a tree-like structure. – Make42 May 03 '16 at 16:13
  • @Bergi: I added a graphic. – Make42 May 03 '16 at 16:21
  • @Make42: But what would the type of `Cons` (`::`) be? The first instance contains two lists (`Nill` and the reference), the second contains a number and a list, and the third contains two numbers. That can't work. If you really meant a tree, then you should draw one, with proper nodes and leafs. – Bergi May 03 '16 at 17:16
  • @Bergi: They way I drew the structure, is the way Martin Odersky drew it in one of his lectures. I am not an expert on the topic - that is how he described it. – Make42 May 03 '16 at 17:19
  • @Make42: The first one, yes. The second one, no. – Bergi May 03 '16 at 17:23
  • Ok, true, you're right. – Make42 May 03 '16 at 17:35
  • @Bergi: You asked what its type would be. Isn't `Nil` (like `Nothing`) one of those classes that inherit from every class? If so there would not be an issue of the type. – Make42 May 07 '16 at 14:59
  • @Make42: No, it is an instance of `List[Nothing]` (so that it can be the last part of every list regardless of its type). – Bergi May 07 '16 at 21:05

1 Answers1

2

Because an append-list wouldn't be immutable (or you'd have to copy it in its entirety on each change).

See https://en.wikipedia.org/wiki/Linked_list for mre.

Rich
  • 15,048
  • 2
  • 66
  • 119