Hi,
My text book says:
(cons (list 1 2) (list 3 4))
is a list of 3 elements(1st element points to a sublist(1 2), 2nd
element is 3, 3rd element is 4). The tree structure is: under root there
are 3 nodes: under 1st node, there are 2 leaves(1 and 2), 2nd and 3rd
nodes are leaves 3 and 4.
I cannot understand it. I think under the root there are two nodes, each
node has two leaves.
Thank you very much for your help.
Shawn wrote:
> Hi,
>
> My text book says:
>
> (cons (list 1 2) (list 3 4))
>
> is a list of 3 elements(1st element points to a sublist(1 2), 2nd
> element is 3, 3rd element is 4). The tree structure is: under root there
> are 3 nodes: under 1st node, there are 2 leaves(1 and 2), 2nd and 3rd
> nodes are leaves 3 and 4.
>
> I cannot understand it. I think under the root there are two nodes, each
> node has two leaves.
The runtime structure of the result
((1 2) 3 4)
looks like this (make sure you're in a courier fort or some other mono
spaced font):
.
/ \
/ \
/ \
/ \
. .
/ \ / \
1 . 3 .
/ \ / \
2 nil 4 nil
The periods in the diagram are cons cells. A cons cell holds 2 items,
the car part and the cdr part.
An online book that goes into great detail about what Lisp's list
structures looks like is:
http://www.cs.cmu.edu/~dst/LispBook/index.html
Glenn
<·············@specastro.com> wrote:
+---------------
| Shawn wrote:
| > My text book says:
| > (cons (list 1 2) (list 3 4))
| > is a list of 3 elements...
| > I cannot understand it. ...
|
| The runtime structure of the result ((1 2) 3 4)
| looks like this (make sure you're in a courier fort or some other mono
| spaced font):
| .
| / \
| / \
| / \
| / \
| . .
| / \ / \
| 1 . 3 .
| / \ / \
| 2 nil 4 nil
+---------------
Yes, but this just confuses the OP more, I'd guess, since he probably
doesn't understand that one should read the "list structure" in the
"down & to the right" directions of your diagram. If you redraw the
periods as boxes [with the CAR on the left and CDR on the right] and
rotate the diagram 45 degrees counterclockwise, you get the more
traditional "boxes & arrows" depiction:
+---------- This is the single cell created by the CONS above.
|
| +------------+-- These were created by (LIST 3 4).
| | |
V V V
+---+---+ +---+---+ +---+---+
| * | *----->| * | *----->| * |NIL|
+-|-+---+ +-|-+---+ +-|-+---+
| | |
| 3 4
V
+---+---+ +---+---+
| * | *-----> | * |NIL| <--- These two were created by (LIST 1 2).
+-|-+---+ +-|-+---+
| |
1 2
Or, since fixnums will fit *inside* the cons cells, you can also
depict them this way:
+---+---+ +---+---+ +---+---+
| * | *----->| 3 | *----->| 4 |NIL|
+-|-+---+ +---+---+ +---+---+
|
|
V
+---+---+ +---+---+
| 1 | *-----> | 2 |NIL|
+---+---+ +---+---+
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
Shawn wrote:
> My text book says:
>
> (cons (list 1 2) (list 3 4))
>
> is a list of 3 elements(1st element points to a sublist(1
> 2), 2nd element is 3, 3rd element is 4).
> I cannot understand it. I think under the root there are
> two nodes, each node has two leaves.
Cons makes a new list whose first element is cons's first
argument and the rest of whose elements are the elements of
cons's second argument:
(cons 1 '(2)) --> (1 2)
(cons 1 '(2 3)) --> (1 2 3)
If this still doesn't make sense, see e.g.:
http://cs.gmu.edu/~sean/lisp/cons/
--
Aaron
Aaron Brown wrote:
> Cons makes a new list whose first element is cons's first
> argument and the rest of whose elements are the elements of
> cons's second argument:
I think that statement is a little imprecise. CONS makes one single
new cons cell, with the first part (the CAR) being set to the first
argument to CONS, and the second part of the cons cell (the CDR) being
set to the second argument to CONS. A list means that the CDR of each
cell points to the next cell in the list, and that the last cell in the
list has a CDR of NIL. By saying that "cons makes a new list" you're
implying CONS creates the list structure I describe above, which it
doesn't. Sorry to be a pedant here :)
Cheers
Brad
Shawn wrote:
> Hi,
>
> My text book says:
>
> (cons (list 1 2) (list 3 4))
>
> is a list of 3 elements(1st element points to a sublist(1 2), 2nd
> element is 3, 3rd element is 4). The tree structure is: under root there
> are 3 nodes: under 1st node, there are 2 leaves(1 and 2), 2nd and 3rd
> nodes are leaves 3 and 4.
>
> I cannot understand it. I think under the root there are two nodes, each
> node has two leaves.
The trick is that there is no such thing as a list, really, just cons
structures with two slots each, the car and the cdr.
In the /abstraction/ we call a "proper list", the cdr always holds
another cons cell or nil. When we speak of the length of this list
abstraction (in this case, your phrase "a list of 3 elements"), we mean
"start counting from a cons as one and follow the chain of cdr slots
counting possible other conses". That gives you three if you follow the
diagrams others have provided.
Your interpretation was "how many things are pointed to by the cons
structure returned by (cons (list 1 2)(list 3 4))?". That would be two,
where the second thing is the chain down which we continue counting when
speaking of a list.
ken
--
Cells: http://common-lisp.net/project/cells/
"I'll say I'm losing my grip, and it feels terrific."
-- Smiling husband to scowling wife, New Yorker cartoon