Why does using cons to create a pair of two lists produce a list and two elements?

Question

I've started learning Scheme, for fun mostly, and because I've never used a functional language before. I chose Scheme because I wanted to read SICP for a long time.

Anyway, I'm currently learning about lists, and before that I learned about cons, car and cdr. And there's an example that creates a list of lists with cons, like this :

(cons (list 1 2) (list 3 4))

The resulting list is ((1 2) 3 4), which doesn't make sense to me, I would expect ((1 2)(3 4)) to be the result (a list made out of two lists). Why does it behave like that? I realize that if I were to use car, I would get (1 2), and cdr I'd get (3 4) becaue cdr always returns "the rest", but I don't understand why the list isn't made of two lists?

Answer 1

You get a list with (1 2) as the first element (the car) and (3 4) as the rest (the cdr) because the first argument to cons is the first element of the list and the second argument is a list containing the remaining items.

This closely resembles the structure of a list: each node of a (proper) list contains an element and a list containing all other element. cons creates one such node.

If the second argument to cons would become the second element of the list, how would you create a list with three arguments? You'd have to make cons variardic at which point, it'd just be another name for list.

If you want to create a list of lists use (list (list 1 2) (list 3 4)).

Answer 2

(list (list 1 2)
      (list 3 4))

is the same as

(cons (list 1 2)
      (cons (list 3 4)
            '()))

Which results in

((1 2) (3 4))

which can also be written as

((1 . (2 . ()))
 . 
 ((3 . (4 . ()))
  .
  ()))

Answer 3

list A:  [  |      ]
          1   [ | ]
               2 /

list B:  [  |      ]
          3   [ | ]
               4 /

======================

(cons A B)

[           |           ]
 [  |     ]   [  |     ]
  1  [ | ]     3  [ | ]
      2 /          4 / 

A graphic representation of the inner structures can help us to visualize the problem.

And this will help some more:

[           |           ]
     X        [  |     ]
               3  [ | ]
                   4 / 

Do you see the pattern? The above is the list (X 3 4). That's the reason (cons A B) draws only the car part as a separate list and not the cdr.

Answer 4

Because a cons-cell is not a list of two elements, the two are often confused. If (a . b) is a cons cell, then (a . (b . ())) is a list of two elements. Any list safe the empty list specifically is a cons cell whose car field contains the first element and whose cdr field contains the list which contains the remaining elements. A list is thus simply a binary tree whose right-most leaf is the special constant () or nil depending on your dialect.

Which is why (cons 0 '(1 2 3)) evaluates to (0 1 2 3) and not (0 (1 2 3)) we create a cons cell whose car is 0, and whose cdr is (1 2 3), so a list (0 1 2 3).