In SICP exercise 2.26 using DrScheme, why does cons return a list, instead of a pair of lists?

Question

In SICP exercise 2.26, this Scheme code is given:

(define x (list 1 2 3))
(define y (list 4 5 6))

Then this cons call is given:

(cons x y)

I expected a pair of lists would result, ((1 2 3) (4 5 6)) but the interpreter gives, ((1 2 3) 4 5 6) ...a list with 4 elements, the first being a list. Why is y treated differently? I've tried looking up other SICP answers for an explanation, but couldn't find something satisfactory. So could any Scheme/Lisp experts please shed some light on this aspect of cons? Thanks in advance for any insight.

Answer 1

'((1 2 3) 4 5 6) is actually a pair of lists. Here's another way to write it:

'((1 2 3) . (4 5 6))

However, the printer avoids dotted pair notation whenever it can, so you get the first representation instead. The rule is:

'(x . (xs ...))
=>
'(x xs ...)

For any x and xs. Here, your x = '(1 2 3) and xs = '(4 5 6), so you get ((1 2 3) 4 5 6).

---

To see how cons and dotted-pair notation is related, let's shorten the problem to just '(1) and '(6). The lowest level way to build a pair of them is this:

(cons (cons 1 '()) (cons 6 '()))

Here, '() is nil, or the empty list. If we translate this literally to dotted-pair notation, we get this:

'((1 . ()) . (6 . ()))

But because the printer collapses dotted-pair notation whenever possible, you get this instead:

'((1 . ()) . (6 . ()))
=>
'((1) . (6))    ; <-- x=1, xs=nothing; x=6, xs=nothing
=>
'((1) 6) ; <-- x=1, xs=6

Answer 2

cons uses the first argument as head of the list, and the second as tail.

You give it a first list (1 2 3), which will constitute the head of the resulting list and a second list (4 5 6), to be used as tail of the list. Thus, you end with ((1 2 3) 4 5 6).

Thing of lists as left-to-right combs, ending with empty list (represented as o here), and see how they combine.

 X=      Y=
 /\      /\
1 /\  + 4 /\    
 2 /\    5 /\  
  3  o    6  o

You then build:

 /\
X  Y

Obtaining:

  /\
 /\ \
1 /\ \
 2 /\ \
  3  o/\
     4 /\
      5 /\
       6  o

which is ((1 2 3) 4 5 6 when represented with parenthesis. And this is a pair of lists.

Answer 3

hey, i think you could think of it in this way;

whenever there is a nil, there must be a pair of parenthesis, as follow:

(cons 1 (cons 2 nil))--> (list 1 2)

(let ((x (list 1 2 3)) (y (list 4 5 6))))

1.(cons x y)--> (cons (cons 1 (cons 2 (cons 3 nil))) (cons 4 (cons 5 (cons 6 nil)))) here, the first nil stands for an end of a pair which could be expressed by parenthesis; whereas the second nil stands for the end of the whole pair which use another pair of parenthesis; so, ((1 2 3) 4 5 6)

2.(list x y)-> (cons x (cons y nil); as we know the x contain a nil, so it must be (1 2 3); the second part contains two nils, so ((1 2 3) (4 5 6));

the inner most nil means the outer most parenthesis;

Hope it can help.

Answer 4

I found the diagrams in the Emacs Lisp tutorial particularly helpful when learning Lisp.