Exercise 2.32 of SICP

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

In order for me to understand what is going on here, I understand how powersets are constructed first and then derive this function.

This program wants to create what is called a powerset.
If S is a set of {a1,a2,a3}
\mathcal{P}(S) = \{\{\} \{a_3\} \{a_2\} \{a_2 a_3\} \{a_1\} \{a_1 a_3\} \{a_1 a_2\} \{a_1 a_2 a_3\}\}
The reasoning to construct a powerset is similar to the way the count change example is thought about.
Create a powerset for the cdr elements without using the car element, cons the car element with powerset of cdr elements. To the result append powerset of cdr elements.

When the arguments are an element and a set inject the element into every element of the set creating a new set. Append that result with the original powerset injected into.

Here is the process above in code:


It’s worth noticing that because of the let expression (subsets (cdr s)) is only called once, as opposed to twice in my earlier derivation.

Exercise 2.31 of SICP

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

> (define t (list 1
(list 2 (list 3 4) 5)
(list 6 7)))
> t
(1 (2 (3 4) 5) (6 7))
> (square-tree t)
(1 (4 (9 16) 25) (36 49))

Exercise 2.30 of SICP

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

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

> (define t (list 1
(list 2 (list 3 4) 5)
(list 6 7)))
> t
(1 (2 (3 4) 5) (6 7))
> (map-square-tree t)
(1 (4 (9 16) 25) (36 49))
> (square-tree t)
(1 (4 (9 16) 25) (36 49))

Exercise 2.29 of SICP

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 list):

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:

a. Write the corresponding selectors left-branch and right-branch, which return the branches of a mobile, and branch-length and branch-structure, which return the components of a branch.

b. Using your selectors, define a procedure total-weight that returns the total weight of a mobile.

> (define m (make-mobile (make-branch 1 2) (make-branch 3 4)))
> (total-weight m)
> (define n (make-mobile (make-branch 1 (make-mobile (make-branch 1 2) (make-bra
nch 3 4))) (make-branch 2 (make-mobile (make-branch 2 2) (make-branch 3 1)))))
> (total-weight n)

c. 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.

> (define m (make-mobile (make-branch 1 2) (make-branch 2 1)))
> (torque-balanced? m)
> (torque-balanced? n)
> (define m (make-mobile (make-branch 1 2) (make-branch 2 2)))
> (torque-balanced? m)

d. Suppose we change the representation of mobiles so that the constructors are

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

Only two changes are needed to selectors of the right side elements because (cdr (list 1 (list 2))) returns ((2)). However the nested list problem doesn’t happen with dotted pairs.

Exercise 2.28 of SICP

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

> (define x (list (list 1 2) (list 3 4)))
> (fringe x)
(1 2 3 4)
> (fringe (list x x))
(1 2 3 4 1 2 3 4)

Exercise 2.27 of SICP

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

> (define x (list (list 1 2) (list 3 4)))
> (deep-reverse x)
((4 3) (2 1))
> (define y (list (list (list 1 2)) (list 3 4)))
> y
(((1 2)) (3 4))
> (deep-reverse y)
((4 3) ((2 1)))

Exercise 2.26 of SICP

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

What result is printed by the interpreter in response to evaluating each of the following expressions:

Exercise 2.25 of SICP

Exercise 2.25: Give combinations of cars and cdrs that will pick 7 from each of the following lists:

> (define a (list 1 3 (list 5 7) 9))
> (car (cdr (car (cdr (cdr a)))))

> (define a (list (list 7)))
> (car (car a))

> (define a (list 1 (list 2 (list 3 (list 4 (list 5 (list 6 7)))))))
> (car (cdr (car (cdr (car (cdr (car (cdr (car (cdr (car (cdr a))))))))))))

Exercise 2.24 of SICP

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).

Exercise 2.23 of SICP

Exercise 2.23: The procedure for-each is similar to map. It takes as arguments a procedure and a list of elements. However, rather than forming a list of the results, for-each just applies the procedure to each of the elements in turn, from left to right. The values returned by applying the procedure to the elements are not used at all — for-each is used with procedures that perform an action, such as printing. For example,

The value returned by the call to for-each (not illustrated above) can be something arbitrary, such as true. Give an implementation of for-each.