Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Is ((1 2) 3) the same as ((1 2) . 3)?

Tags:

scheme

racket

I've been given an assignment in Scheme (using DrRacket) that asks me to create the list ((1 2) 3) using cons, from the components 1, 2, 3 and ()

I've managed to get as far as ((1 2) . 3) using:

(cons (cons '1 (cons '2 '())) '3)

However, is that the same thing?

like image 246
karoma Avatar asked Oct 07 '13 11:10

karoma


4 Answers

Note: this is cannibalized from my answer to Recursive range in Lisp adds a period? The question is different (so not a duplicate), but the background explanation of how lists are constructed from cons cells, and how they're printed is the same. The end is a bit different.

A list in Scheme is either the empty list () (also known as nil in some Lisps), or a cons cell whose car (also known as first) is an element of the list and whose cdr (also known as rest) is either the rest of the list (i.e., another list), or an atom that terminates the list. The conventional terminator is the empty list (); lists terminated by () are said to be "proper lists". Lists terminated by any other atom are called "improper lists". The list (1 2 3 4 5) contains the elements 1, 2, 3, 4, and 5, and is terminated by (). You could construct it by

(cons 1 (cons 2 (cons 3 (cons 4 (cons 5 ())))))

Now, when the system prints a cons cell, the general case is to print it by

(car . cdr)

For instance, the result of (cons 1 2) is printed as

(1 . 2)

Since lists are built of cons cells, you can use this notation for lists too:

'(1 2 3 4 5)                      ; ==
'(1 . (2 . (3 . (4 . (5 . ())))))

That's rather clunky, though, so most lisps (all that I know of) have a special case for printing cons cells: if the cdr is a list (either another cons cell, or ()), then don't print the ., and don't print the surrounding parenthesis of the cdr (which it would otherwise have, since it's a list).

With this understanding of lists and cons cells, we can consider the specific cases ((1 2) 3) and ((1 2) . 3). Let's break each of these down into the cons cells.

((1 2) 3)                              ; ==
((1 . (2 . ()) . (3 . ()))             ; ==
(cons (cons 1 (cons 2 ()) (cons 3 ()))  
((1 2) . 3)                   ; ==           
((1 . (2 . ())) . 3)          ; ==
(cons (cons 1 (cons 2 ())) 3)

The last lines in each case are different, so ((1 2) 3) and ((1 2) . 3) are not the same.

like image 190
Joshua Taylor Avatar answered Nov 08 '22 16:11

Joshua Taylor


No, as others have mentioned, ((1 2) 3) is the same as ((1 2) 3 . ()), which of course you can build using (cons '3 '()) instead of the literal '3:

(cons (cons '1 (cons '2 '())) (cons '3 '()))
like image 20
Justin Ethier Avatar answered Nov 08 '22 16:11

Justin Ethier


No.

The "top-level" element of (A . B) is a single cons cell: (cons A B). The car of the cons cell is A and the cdr is B. In a proper list, the cdr elements are always either () or other nonempty proper lists.

In contrast, (A B) is a two-element list, with one cons cell for each element: (cons A (cons B ()))

like image 32
svk Avatar answered Nov 08 '22 16:11

svk


They are different. ((1 2) 3) is a '() terminated list while ((1 2) . 3) is just a "pair". Try replacing '3 with (cons '3 '())

like image 1
hugomg Avatar answered Nov 08 '22 16:11

hugomg