The representation of sequences in terms of listslinked lists generalizes naturally to represent sequences whose elements may themselves be sequences. For example, we can regard the object ((1 2) 3 4) [[1, [2, None]], [3, [4, None]]] constructed by

Original	Python
(cons (list 1 2) (list 3 4))	pair(llist(1, 2), llist(3, 4))

as a listlinked list of three items, the first of which is itself a listlinked list, (1 2). Indeed, this is suggested by the form in which the result is printed by the interpreter. [1, [2, None]]. Figure 2.9 Figure 2.10 shows the representation of this structure in terms of pairs.

Original		Python
Figure 2.9 Structure formed by (cons (list 1 2) (list 3 4)).		Figure 2.10 Structure formed by pair(llist(1, 2), llist(3, 4)).

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. Figure 2.11 Figure 2.12 shows the structure in figure 2.9 figure 2.10 viewed as a tree.

Original		Python
Figure 2.11 The list structure in figure 2.9 viewed as a tree.		Figure 2.12 The linked-list structure in figure 2.10 viewed as a tree.

Recursion is a natural tool for dealing with tree structures, since we can often reduce operations on trees to operations on their branches, which reduce in turn to operations on the branches of the branches, and so on, until we reach the leaves of the tree. As an example, compare the length length procedure function of section 2.2.1 with the count-leaves count_leaves procedure, function, which returns the total number of leaves of a tree:

Original	Python
(define x (cons (list 1 2) (list 3 4)))	x = pair(llist(1, 2), llist(3, 4))

Original	Python
(length x) 3	print(length(x)) 3

Original	Python
(count-leaves x) 4	print(count_leaves(x)) 4

Original	Python
(list x x) (((1 2) 3 4) ((1 2) 3 4))	print_llist(llist(x, x)) llist(llist(llist(1, 2), 3, 4), llist(llist(1, 2), 3, 4))

Original	Python
(length (list x x)) 2	print(length(llist(x, x))) 2

Original	Python
(count-leaves (list x x)) 8	print(count_leaves(llist(x, x))) 8

To implement count-leaves, count_leaves, recall the recursive plan for computing length: length:

• Length The length of a listlinked list x is 1 plus length the length of the cdr tail of x.
• Length The length of the empty listlinked list is 0.

Count-leaves The function count_leaves is similar. The value for the empty listlinked list is the same:

• Count-leaves count_leaves of the empty listlinked list is 0.

But in the reduction step, where we strip off the car head of the listlinked list, we must take into account that the car head may itself be a tree whose leaves we need to count. Thus, the appropriate reduction step is

• Count-leaves count_leaves of a tree x is count-leaves count_leaves of the car head of x plus count-leaves count_leaves of the cdr tail of x.

Finally, by taking cars heads we reach actual leaves, so we need another base case:

• Count-leaves count_leaves of a leaf is 1.

To aid in writing recursive procedures functions on trees, Scheme our Python environment provides the primitive predicate pair?, is_pair, which tests whether its argument is a pair. Here is the complete procedure:[1]function:[2]

Original	Python
(define (count-leaves x) (cond ((null? x) 0) ((not (pair? x)) 1) (else (+ (count-leaves (car x)) (count-leaves (cdr x))))))	def count_leaves(x): return (0 if is_none(x) else 1 if not is_pair(x) else count_leaves(head(x)) + count_leaves(tail(x)))

Exercise 2.24 Suppose we evaluate the expression (list 1 (list 2 (list 3 4))). llist(1, llist(2, llist(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.11). figure 2.12).

Solution

1. Original	Python
   	[1, [[2, [[3, [4, None]], None]], None]]

2. 

3. 

Exercise 2.25 Give combinations of cars heads and cdrs tails that will pick 7 from each of the following lists: linked lists, given in linked-list notation:

Original	Python
(1 3 (5 7) 9) ((7)) (1 (2 (3 (4 (5 (6 7))))))	llist(1, 3, llist(5, 7), 9) llist(llist(7)) llist(1, llist(2, llist(3, llist(4, llist(5, llist(6, 7))))))

Solution

• head(tail(head(tail(tail(the_first_list)))))
• head(head(the_second_list))
• head(tail(head(tail(head(tail(head(tail(head( tail(head(tail(the_third_list))))))))))))

Exercise 2.26 Suppose we define x and y to be two listslinked lists:

Original	Python
(define x (list 1 2 3)) (define y (list 4 5 6))	x = llist(1, 2, 3) y = llist(4, 5, 6)

What result is printed by the interpreter in response to evaluating each of the following expressions: What is the result of evaluating each of the following expressions, in box notation and linked-list notation?

Original	Python
(append x y)	append(x, y)

Original	Python
(cons x y)	pair(x, y)

Original	Python
(list x y)	llist(x, y)

Solution

1. Original	Python
   	print([1, [2, [3, [4, [5, [6, None]]]]]])

2. Original	Python
   	print([[1, [2, [3, None]]], [4, [5, [6, None]]]])

3. Original	Python
   	print([[1, [2, [3, None]]], [[4, [5, [6, None]]], None]])

Exercise 2.27 Modify your reverse reverse procedure function of exercise 2.18 to produce a deep-reverse deep_reverse procedure function that takes a listlinked list as argument and returns as its value the listlinked list with its elements reversed and with all sublists deep-reversed as well. For example,

Original	Python
(define x (list (list 1 2) (list 3 4)))	x = llist(llist(1, 2), llist(3, 4))

Original	Python
x ((1 2) (3 4))	print_llist(x) llist(llist(1, 2), llist(3, 4))

Original	Python
(reverse x) ((3 4) (1 2))	print_llist(reverse(x)) llist(llist(3, 4), llist(1, 2))

Original	Python
(deep-reverse x) ((4 3) (2 1))	print_llist(deep_reverse(x)) llist(llist(4, 3), llist(2, 1))

Solution

Original	Python
	def deep_reverse(items): return (None if is_none(items) else append(deep_reverse(tail(items)), pair(deep_reverse(head(items)), None)) if is_pair(items) else items)

Exercise 2.28 Write a procedure function fringe fringe that takes as argument a tree (represented as a listlinked list) and returns a listlinked list whose elements are all the leaves of the tree arranged in left-to-right order. For example,

Original	Python
(define x (list (list 1 2) (list 3 4)))	x = llist(llist(1, 2), llist(3, 4))

Original	Python
(fringe x) (1 2 3 4)	print_llist(fringe(x)) llist(1, 2, 3, 4)

Original	Python
(fringe (list x x)) (1 2 3 4 1 2 3 4)	print_llist(fringe(llist(x, x))) llist(1, 2, 3, 4, 1, 2, 3, 4)

Solution

Original	Python
	def fringe(x): return (None if is_none(x) else append(fringe(head(x)), fringe(tail(x))) if is_pair(x) else llist(x))

Exercise 2.29 A binary mobile consists of two branches, a left branch and a right branch. Each branch is a rod of a certain length, from which hangs either a weight or another binary mobile. We can represent a binary mobile using compound data by constructing it from two branches (for example, using listllist):

Original	Python
(define (make-mobile left right) (list left right))	def make_mobile(left, right): return llist(left, right)

A branch is constructed from a length (which must be a number) together with a structure, which may be either a number (representing a simple weight) or another mobile:

Original	Python
(define (make-branch length structure) (list length structure))	def make_branch(length, structure): return llist(length, structure)

1. Write the corresponding selectors left-branch left_branch and right-branch, right_branch, which return the branches of a mobile, and branch-length branch_length and branch-structure, branch_structure, which return the components of a branch.
2. Using your selectors, define a procedure function total-weight total_weight that returns the total weight of a mobile.
3. A mobile is said to be balanced if the torque applied by its top-left branch is equal to that applied by its top-right branch (that is, if the length of the left rod multiplied by the weight hanging from that rod is equal to the corresponding product for the right side) and if each of the submobiles hanging off its branches is balanced. Design a predicate that tests whether a binary mobile is balanced.
4. Suppose we change the representation of mobiles so that the constructors are

   Original	Python
   (define (make-mobile left right) (cons left right)) (define (make-branch length structure) (cons length structure))	def make_mobile(left, right): return pair(left, right) def make_branch(length, structure): return pair(length, structure)

   How much do you need to change your programs to convert to the new representation?

Solution

1. def left_branch(m): return head(m) def right_branch(m): return head(tail(m)) def branch_length(b): return head(b) def branch_structure(b): return head(tail(b))
2. def is_weight(x): return is_number(x) def total_weight(x): return (x if is_weight(x) else total_weight(branch_structure( left_branch(x))) + total_weight(branch_structure( right_branch(x))))
3. def is_balanced(x): return (is_weight(x) or (is_balanced(branch_structure(left_branch(x))) and is_balanced(branch_structure(right_branch(x))) and total_weight(branch_structure(left_branch(x))) * branch_length(left_branch(x)) == total_weight(branch_structure(right_branch(x))) * branch_length(right_branch(x))))
4. With this alternative representation, the selector functions for mobile and branch need to change as follows: def left_branch(m): return head(m) def right_branch(m): return tail(m) def branch_length(b): return head(b) def branch_structure(b): return tail(b)

Mapping over trees

Just as map is a powerful abstraction for dealing with sequences, map together with recursion is a powerful abstraction for dealing with trees. For instance, the scale-tree scale_tree procedure, function, analogous to scale-list scale_linked_list of section 2.2.1, takes as arguments a numeric factor and a tree whose leaves are numbers. It returns a tree of the same shape, where each number is multiplied by the factor. The recursive plan for scale-tree scale_tree is similar to the one for count-leaves: count_leaves:

Original	Python
(define (scale-tree tree factor) (cond ((null? tree) nil) ((not (pair? tree)) (* tree factor)) (else (cons (scale-tree (car tree) factor) (scale-tree (cdr tree) factor)))))	def scale_tree(tree, factor): return (None if is_none(tree) else tree * factor if not is_pair(tree) else pair(scale_tree(head(tree), factor), scale_tree(tail(tree), factor)))

Original	Python
(scale-tree (list 1 (list 2 (list 3 4) 5) (list 6 7)) 10) (10 (20 (30 40) 50) (60 70))	print_llist(scale_tree(llist(1, llist(2, llist(3, 4), 5), llist(6, 7)), 10)) llist(10, llist(20, llist(30, 40), 50), llist(60, 70))

Another way to implement scale-tree scale_tree is to regard the tree as a sequence of sub-trees and use map. map. We map over the sequence, scaling each sub-tree in turn, and return the listlinked list of results. In the base case, where the tree is a leaf, we simply multiply by the factor:

Original	Python
(define (scale-tree tree factor) (map (lambda (sub-tree) (if (pair? sub-tree) (scale-tree sub-tree factor) (* sub-tree factor))) tree))	def scale_tree(tree, factor): return map(lambda sub_tree: (scale_tree(sub_tree, factor) if is_pair(sub_tree) else sub_tree * factor), tree)

Many tree operations can be implemented by similar combinations of sequence operations and recursion.

Exercise 2.30 Define a procedure Declare a function square-tree square_tree analogous to the square-list square_linked_list procedure function of exercise 2.21. That is, square-tree square_tree should behave as follows:

Original	Python
(square-tree (list 1 (list 2 (list 3 4) 5) (list 6 7))) (1 (4 (9 16) 25) (36 49))	print_llist(square_tree(llist(1, llist(2, llist(3, 4), 5), llist(6, 7)))) llist(1, llist(4, llist(9, 16), 25), llist(36, 49)))

Define square-tree Declare square_tree both directly (i.e., without using any higher-order procedures) functions) and also by using map and recursion.

Solution

Directly: def square_tree(tree): return (None if is_none(tree) else square(tree) if not is_pair(tree) else pair(square_tree(head(tree)), square_tree(tail(tree)))) [1, [[4, [[9, [16, None]], [25, None]]], [[36, [49, None]], None]]] The version using map: def square_tree(tree): return map(lambda sub_tree: (square(sub_tree) if not is_pair(sub_tree) else square_tree(sub_tree)), tree) [1, [[4, [[9, [16, None]], [25, None]]], [[36, [49, None]], None]]]

Exercise 2.31 Abstract your answer to exercise 2.30 to produce a procedure function tree-map tree_map with the property that square-tree could be defined as square_tree could be declared as

Original	Python
(define (square-tree tree) (tree-map square tree))	def square_tree(tree): return tree_map(square, tree)

Solution

def tree_map(f, tree): return map(lambda sub_tree: (None if is_none(sub_tree) else tree_map(f, sub_tree) if is_pair(sub_tree) else f(sub_tree)), tree) [1, [[4, [[9, [16, None]], [25, None]]], [[36, [49, None]], None]]]

Exercise 2.32 We can represent a set as a listlinked list of distinct elements, and we can represent the set of all subsets of the set as a listlinked list of listslinked lists. For example, if the set is (1 2 3), llist(1, 2, 3), then the set of all subsets is (() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3)). llist(None, llist(3), llist(2), llist(2, 3), llist(1), llist(1, 3), llist(1, 2), llist(1, 2, 3)) Complete the following definition of a procedure declaration of a function that generates the set of subsets of a set and give a clear explanation of why it works:

Original	Python
(define (subsets s) (if (null? s) (list nil) (let ((rest (subsets (cdr s)))) (append rest (map ?? rest)))))	def subsets(s): if is_none(s): return llist(None) else: rest = subsets(tail(s)) return append(rest, map($\langle{}$??$\rangle$, rest))

Solution

Original	Python
	def subsets(s): if is_none(s): return llist(None) else: rest = subsets(tail(s)) return append(rest, map(lambda x: pair(head(s), x), rest)) [ None, [ [3, None], [ [2, None], [ [2, [3, None]], [ [1, None], [ [1, [3, None]], [ [1, [2, None]], [[1, [2, [3, None]]], None] ] ] ] ] ] ] ]

The argument starts in a similar way as the argument for the function cc in section 1.2.2: A subset either contains the first element $e$ of the given set, or it doesn't. If it doesn't, the problem becomes strictly smaller: Compute all subsets of the tail of the listlinked list that represents the given set. If it does, it must result from adding $e$ to a subset that doesn't contain $e$. In the end, we need to append both listslinked lists of subsets to obtain the listlinked list of all subsets.