Asp Forum - understanding the tree in SICP - exercise 2.24

chong.franklin

1/5/2016 7:46:00 AM

From SICP https://mitpress.mit.edu/sicp/full-text/book/book-Z-H-15.html#%...

<blockquote>
Exercise 2.24: Suppose we evaluate the expression (list 1 (list 2 (list 3 4))). Give the result printed by the interpreter, the corresponding box-and-pointer structure, and the interpretation of this as a tree (as in Figure 2.6).
</blockquote>

The problem is my eyes are destroyed, therefore I can see neither the box and pointer diagram nor Figure 2.6. So now I only have a guess on what this list should look like as a tree based on:

<blockquote>
Another way to think of sequences whose elements are sequences is as trees. The elements of the sequence are the branches of the tree, and elements that are themselves sequences are subtrees.
</blockquote>

Please check my tree interpretation. This is just my imagination. I'm pretty confident this is correct, but have no way of confirming it because all of the answers to the exercise I found are pictures and my screen reader can't read them.

(list 1 (list 2 (list 3 4))) - I think this is the tree itself, or the rootnode. This tree has two branches or children. 
The first branch (1) is a leaf node, so we are done at this side of the tree. 
The second branch (list 2 (list 3 4) is another tree. 
Now we focus on the subtree (list 2 (list 3 4). It has two children/branches. 
The first branch is a leafnode (2), so we're done here. 
The second branch is another tree (list 3 4). 
Now we focus on the subtree (list 3 4). It has two children branches. 
They are both leafnodes, so we're done.

Is this correct? Did I interpret the tree right?

4 Answers

Jussi Piitulainen

1/5/2016 8:26:00 AM

chong.franklin@gmail.com writes:

> From SICP https://mitpress.mit.edu/sicp/full-text/book/book-Z-H-15.html#%...
>
> <blockquote>
> Exercise 2.24: Suppose we evaluate the expression (list 1 (list 2 (list 3 4))). Give the result printed by the interpreter, the corresponding box-and-pointer structure, and the interpretation of this as a tree (as in Figure 2.6).
> </blockquote>
>
> The problem is my eyes are destroyed, therefore I can see neither the box and pointer diagram nor Figure 2.6. So now I only have a guess on what this list should look like as a tree based on:
>
> <blockquote>
> Another way to think of sequences whose elements are sequences is as trees. The elements of the sequence are the branches of the tree, and elements that are themselves sequences are subtrees.
> </blockquote>
>
> Please check my tree interpretation. This is just my imagination. I'm pretty confident this is correct, but have no way of confirming it because all of the answers to the exercise I found are pictures and my screen reader can't read them.
>
> (list 1 (list 2 (list 3 4))) - I think this is the tree itself, or the rootnode. This tree has two branches or children. 
> The first branch (1) is a leaf node, so we are done at this side of the tree. 
> The second branch (list 2 (list 3 4) is another tree. 
> Now we focus on the subtree (list 2 (list 3 4). It has two children/branches. 
> The first branch is a leafnode (2), so we're done here. 
> The second branch is another tree (list 3 4). 
> Now we focus on the subtree (list 3 4). It has two children branches. 
> They are both leafnodes, so we're done.
>
> Is this correct? Did I interpret the tree right?

I think you have that right except for one detail: where you write the
first branch as (1), and the first branch of the second branch as (2),
those should be just 1 and 2.

Figure 2.6 has its root node labeled with ((1 2) 3 4), and it has three
branches. The left branch is a subtree labeled with (1 2), and its two
branches are 1 and 2, respectively. The middle branch of the root is 3,
and the right branch is 4.

The exercise is to describe (1 (2 (3 4))), so the left branch is just 1.
A literal (1) would not be a leaf but a subtree with a branch that is 1.

I hope I managed to follow the terminology of the exercise, and I hope
this helps.

chong.franklin

1/5/2016 12:30:00 PM

On Tuesday, January 5, 2016 at 4:26:02 PM UTC+8, Jussi Piitulainen wrote:
> chong.franklin@gmail.com writes:
>
> > From SICP https://mitpress.mit.edu/sicp/full-text/book/book-Z-H-15.html#%...
> >
> > <blockquote>
> > Exercise 2.24: Suppose we evaluate the expression (list 1 (list 2 (list 3 4))). Give the result printed by the interpreter, the corresponding box-and-pointer structure, and the interpretation of this as a tree (as in Figure 2.6).
> > </blockquote>
> >
> > The problem is my eyes are destroyed, therefore I can see neither the box and pointer diagram nor Figure 2.6. So now I only have a guess on what this list should look like as a tree based on:
> >
> > <blockquote>
> > Another way to think of sequences whose elements are sequences is as trees. The elements of the sequence are the branches of the tree, and elements that are themselves sequences are subtrees.
> > </blockquote>
> >
> > Please check my tree interpretation. This is just my imagination. I'm pretty confident this is correct, but have no way of confirming it because all of the answers to the exercise I found are pictures and my screen reader can't read them.
> >
> > (list 1 (list 2 (list 3 4))) - I think this is the tree itself, or the rootnode. This tree has two branches or children. 
> > The first branch (1) is a leaf node, so we are done at this side of the tree. 
> > The second branch (list 2 (list 3 4) is another tree. 
> > Now we focus on the subtree (list 2 (list 3 4). It has two children/branches. 
> > The first branch is a leafnode (2), so we're done here. 
> > The second branch is another tree (list 3 4). 
> > Now we focus on the subtree (list 3 4). It has two children branches. 
> > They are both leafnodes, so we're done.
> >
> > Is this correct? Did I interpret the tree right?
>
> I think you have that right except for one detail: where you write the
> first branch as (1), and the first branch of the second branch as (2),
> those should be just 1 and 2.
>
> Figure 2.6 has its root node labeled with ((1 2) 3 4), and it has three
> branches. The left branch is a subtree labeled with (1 2), and its two
> branches are 1 and 2, respectively. The middle branch of the root is 3,
> and the right branch is 4.
>
> The exercise is to describe (1 (2 (3 4))), so the left branch is just 1.
> A literal (1) would not be a leaf but a subtree with a branch that is 1.
>
> I hope I managed to follow the terminology of the exercise, and I hope
> this helps.

Thanks. But what is a leaf? I thought those are things that doesn't have children?

Jussi Piitulainen

1/5/2016 1:34:00 PM

chong.franklin@gmail.com writes:

> On Tuesday, January 5, 2016 at 4:26:02 PM UTC+8, Jussi Piitulainen wrote:
>> chong.franklin@gmail.com writes:
>>
>> > From SICP https://mitpress.mit.edu/sicp/full-text/book/book-Z-H-15.html#%...
>> >
>> > <blockquote>
>> > Exercise 2.24: Suppose we evaluate the expression (list 1 (list 2 (list 3 4))). Give the result printed by the interpreter, the corresponding box-and-pointer structure, and the interpretation of this as a tree (as in Figure 2.6).
>> > </blockquote>
>> >
>> > The problem is my eyes are destroyed, therefore I can see neither the box and pointer diagram nor Figure 2.6. So now I only have a guess on what this list should look like as a tree based on:
>> >
>> > <blockquote>
>> > Another way to think of sequences whose elements are sequences is as trees. The elements of the sequence are the branches of the tree, and elements that are themselves sequences are subtrees.
>> > </blockquote>
>> >
>> > Please check my tree interpretation. This is just my imagination. I'm pretty confident this is correct, but have no way of confirming it because all of the answers to the exercise I found are pictures and my screen reader can't read them.
>> >
>> > (list 1 (list 2 (list 3 4))) - I think this is the tree itself, or the rootnode. This tree has two branches or children. 
>> > The first branch (1) is a leaf node, so we are done at this side of the tree. 
>> > The second branch (list 2 (list 3 4) is another tree. 
>> > Now we focus on the subtree (list 2 (list 3 4). It has two children/branches. 
>> > The first branch is a leafnode (2), so we're done here. 
>> > The second branch is another tree (list 3 4). 
>> > Now we focus on the subtree (list 3 4). It has two children branches. 
>> > They are both leafnodes, so we're done.
>> >
>> > Is this correct? Did I interpret the tree right?
>>
>> I think you have that right except for one detail: where you write the
>> first branch as (1), and the first branch of the second branch as (2),
>> those should be just 1 and 2.
>>
>> Figure 2.6 has its root node labeled with ((1 2) 3 4), and it has three
>> branches. The left branch is a subtree labeled with (1 2), and its two
>> branches are 1 and 2, respectively. The middle branch of the root is 3,
>> and the right branch is 4.
>>
>> The exercise is to describe (1 (2 (3 4))), so the left branch is just 1.
>> A literal (1) would not be a leaf but a subtree with a branch that is 1.
>>
>> I hope I managed to follow the terminology of the exercise, and I hope
>> this helps.
>
> Thanks. But what is a leaf? I thought those are things that doesn't have children?

More or less. For the purposes of that exercise, any list is a tree, and
any other thing is a leaf. Branches of a tree are either subtrees or
leaves. Seen this way, any thing is either a tree or a leaf but not
both. There is one tree that does not have branches, and there are lots
of trees like (() ()) that don't have leaves.

Down the page, in scale-tree in the section titled "Mapping over trees",
they also use the name "sub-tree" instead of "branch" for the components
of a tree, so now a "subtree" need not be a "tree" if trees are still
taken as disjoint from leaves. Not completely rigorous. Maybe take it so
that a tree can be either a proper list or a leaf.

chong.franklin

1/5/2016 3:48:00 PM

On Tuesday, January 5, 2016 at 9:34:00 PM UTC+8, Jussi Piitulainen wrote:
> chong.franklin@gmail.com writes:
>
> > On Tuesday, January 5, 2016 at 4:26:02 PM UTC+8, Jussi Piitulainen wrote:
> >> chong.franklin@gmail.com writes:
> >>
> >> > From SICP https://mitpress.mit.edu/sicp/full-text/book/book-Z-H-15.html#%...
> >> >
> >> > <blockquote>
> >> > Exercise 2.24: Suppose we evaluate the expression (list 1 (list 2 (list 3 4))). Give the result printed by the interpreter, the corresponding box-and-pointer structure, and the interpretation of this as a tree (as in Figure 2.6).
> >> > </blockquote>
> >> >
> >> > The problem is my eyes are destroyed, therefore I can see neither the box and pointer diagram nor Figure 2.6. So now I only have a guess on what this list should look like as a tree based on:
> >> >
> >> > <blockquote>
> >> > Another way to think of sequences whose elements are sequences is as trees. The elements of the sequence are the branches of the tree, and elements that are themselves sequences are subtrees.
> >> > </blockquote>
> >> >
> >> > Please check my tree interpretation. This is just my imagination. I'm pretty confident this is correct, but have no way of confirming it because all of the answers to the exercise I found are pictures and my screen reader can't read them.
> >> >
> >> > (list 1 (list 2 (list 3 4))) - I think this is the tree itself, or the rootnode. This tree has two branches or children. 
> >> > The first branch (1) is a leaf node, so we are done at this side of the tree. 
> >> > The second branch (list 2 (list 3 4) is another tree. 
> >> > Now we focus on the subtree (list 2 (list 3 4). It has two children/branches. 
> >> > The first branch is a leafnode (2), so we're done here. 
> >> > The second branch is another tree (list 3 4). 
> >> > Now we focus on the subtree (list 3 4). It has two children branches. 
> >> > They are both leafnodes, so we're done.
> >> >
> >> > Is this correct? Did I interpret the tree right?
> >>
> >> I think you have that right except for one detail: where you write the
> >> first branch as (1), and the first branch of the second branch as (2),
> >> those should be just 1 and 2.
> >>
> >> Figure 2.6 has its root node labeled with ((1 2) 3 4), and it has three
> >> branches. The left branch is a subtree labeled with (1 2), and its two
> >> branches are 1 and 2, respectively. The middle branch of the root is 3,
> >> and the right branch is 4.
> >>
> >> The exercise is to describe (1 (2 (3 4))), so the left branch is just 1.
> >> A literal (1) would not be a leaf but a subtree with a branch that is 1.
> >>
> >> I hope I managed to follow the terminology of the exercise, and I hope
> >> this helps.
> >
> > Thanks. But what is a leaf? I thought those are things that doesn't have children?
>
> More or less. For the purposes of that exercise, any list is a tree, and
> any other thing is a leaf. Branches of a tree are either subtrees or
> leaves. Seen this way, any thing is either a tree or a leaf but not
> both. There is one tree that does not have branches, and there are lots
> of trees like (() ()) that don't have leaves.
>
> Down the page, in scale-tree in the section titled "Mapping over trees",
> they also use the name "sub-tree" instead of "branch" for the components
> of a tree, so now a "subtree" need not be a "tree" if trees are still
> taken as disjoint from leaves. Not completely rigorous. Maybe take it so
> that a tree can be either a proper list or a leaf.

Got it, thanks.

comp.lang.lisp

understanding the tree in SICP - exercise 2.24

chong.franklin

Jussi Piitulainen

chong.franklin

Jussi Piitulainen

chong.franklin

x Login to ForumsZone