Cons in scheme explanation

问题:

(cons 1 2) gives us (1 . 2).

(cons 3 4) gives us (3 . 4).

So why does (cons (cons 1 2) (cons 3 4)) give us ((1 . 2) 3 . 4)? Why isn't it ((1 . 2) (3 . 4))?

回答1:

Well, it wouldn't be ((1 . 2) (3 . 4)) because that would be a list containing two elements, each a cons pair. I'm guessing what you meant was: why isn't it ((1 . 2) . (3 . 4))?

Well, actually the following two expressions are equivalent:

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

This has to do with how Scheme's dotted notation works in tandem with its representation of proper lists. Remember that this:

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

...would simply be printed as this:

(1 2 3 4)

However, this:

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

...would be printed like this:

(1 2 3 . 4)

Note that Scheme tries to use the simplified list notation as long as it can—it only falls back to explicitly dotting things once it reaches a pair which doesn't have a pair or the empty list as its cdr element.

Therefore, in your original example, the second element of that cons pair is a pair, so Scheme uses the list notation. That lets it drop the second set of parentheses and the extra dot, yielding the result you encountered.