Why it is `(cons 1 (cons 2 (cons 3 nil)))` and not `(cons 3 (cons 2 (cons 1 nil)))` for [1,2,3]

data structuresfunctional programminglistscheme

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.

Best Answer

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.

Related Solutions

Functional Programming – Why Are Cons Lists Associated with Functional Programming?

The most important factor is that you can prepend to an immutable singly linked list in O(1) time, which allows you to recursively build up n-element lists in O(n) time like this:

// Build a list containing the numbers 1 to n:
foo(0) = []
foo(n) = cons(n, foo(n-1))

If you did this using immutable arrays, the runtime would be quadratic because each cons operation would need to copy the whole array, leading to a quadratic running time.

Functional style encourages immutability, so also data sharing; an array is easier to share "partially" than a linked list

I assume by "partially" sharing you mean that you can take a subarray from an array in O(1) time, whereas with linked lists you can only take the tail in O(1) time and everything else needs O(n). That is true.

However taking the tail is enough in many cases. And you have to take into account that being able to cheaply create subarrays doesn't help you if you have no way of cheaply creating arrays. And (without clever compiler optimizations) there is no way to cheaply build-up an array step-by-step.

Difference Between Lists Constructed by Quote and Cons in Scheme

Quote

Quote returns data which you should not modify, and which may share structure between themselves. E.g. if you have a file which contains

(define l1 '(1 2 3))
(define l2 '(4 2 3))

then the compiler is permitted to allocate l1 and l2 in a way that they share their common tail (cdr l1) and (cdr l2) and/or in the read-only memory.

Modification of such lists is undefined behavior. Do not do it.

`list`

list and cons create fresh objects (different from everything which already exist), they allocate and populate memory. You own them - you can modify them as much as you want.

Your case

Both your set-car! calls are wrong - you are modifying read-only data and thus triggering undefined behavior (i.e., you are lucky your computer did not blow up in your face :-).

Specifically, in the first case, ls1, you get what you would get if you did the right thing, i.e.,

(define ls1
  (cons (cons 1 2)
        (cons 1 2)))

while in the second case the implementation allocated only one cons cell (1 . 2) and re-used it in creating ls2, i.e., you see what you would see if you evaluate the following (legal) code:

(define ls2
  (let ((l (cons 1 2)))
    (cons l l)))

If there were print-circle in scheme, you could see the data re-use:

[1]> (let ((l (cons 1 2)))
        (cons l l)) 
((1 . 2) 1 . 2)
[2]> (setq *print-circle* t)
T
[3]> (let ((l (cons 1 2)))
        (cons l l)) 
(#1=(1 . 2) . #1#)

Binding

x is bound to a value means that the name x refers to the object, the same way in all languages.

The difference in Lisp/Scheme is what the object is.

Here it is the first cons cell of the list - as you have probably seen many times, a (linked) list is a chain of cons cell, where car contains the value and cdr contains the next cons cell in the list.