Is there any special reason that to construct list in Scheme you use
(cons 1 (cons 2 (cons 3 nil)))
instead of
(cons 3 (cons 2 (cons 1 nil)))
? While the first seems more obvious because it reads in the right order, the second is the one which actually reduces in the right order. Also, it seems more natural to construct a list starting with nil and adding elements to it, not the opposite. I’ve also found the latter has properties such as being very curry friendly: (cons 1) nicely becomes a function that appends 1 to a list.
7
How do you propose the head be reached in this reversed list? If not using mutable structures the reversed list would only be performant if you made the head linear time and tail constant. But now you’ve got the exact same structure as before except you’re calling the head the tail and vice versa.
the structure is the way it is because regardless of which side you declare to be the front or the back, that particular form is the only known one with constant time readahead and constant time insert without mutation or doing amortization trickery.
you’re getting hung up on the terms thinking one side could be head or tail but those terms don’t matter, the part that counts is the structure.
1
Because appending to the end of a linked list is O(n) and appending to the front is O(1). The operation you’re looking for is called snoc and can be implemented. But inefficiently.
To see why, realize that when you append to the back of a list, if you don’t mutate anything, every single element must be copied, where as with appending to the front, you can just allocate a cons cell and have it point to the existing list, a relatively cheap operation.
3
As I mentioned in a comment in your previous question, if you want immutable linked lists, a straightforward implementation using cons cells can only have either a forward (next) pointer or a backward (previous) pointer, not both. In other words, they’re singly-linked lists.
That means that if you want to represent (1 2 3) using (cons 3 (cons 2 (cons 1 '()))), your variable would point to the “last” node (containing the 3), and you’d traverse “backwards” to get to the 2, then the 1. Using this system, it would be impossible to access the 2 node from the 1 node, so you cannot easily traverse the list in the (1 2 3) order.
3
We use the first method because it produces the correct list. The second produces a reversed list. The nil very clearly shows which element must be the last.
The order matters!
See this trivial example in Common Lisp:
(reduce #'expt (cons 1 (cons 2 (cons 3 nil))))
1
(reduce #'expt (cons 3 (cons 2 (cons 1 nil))))
9
You could use the second method if you have the language’s implementation to handle the reversed order under the hood, but then:
- the implementation would be more complicated (= more opportunity for bugs)
- performance would be affected as mentioned in other answers (some cases, such as full traversals, could have the performance hit mitigated by using more memory, i.e. creating a copy of the list in the correct direction behind the scenes then doing the work on that copy. That’s still making two traversals where just one would have been sufficient before.)
- unreliable humans would have to remember to build their lists backwards.