SICP 2.2.2 Solutions
July 2, 2014 21:13
The interpreter expression is easy to generate. As a box-and-pointer diagram, here’s what it is:
One quick check that can be done using a box-and-pointer diagrams is to count the number of lists. We know from the expression that, with three parenthesized statements, three lists must be present. On a box-and-pointer diagram, a list will be a horizontal sequence of boxes, terminating in a ‘null’ slashed box. We see that much, so we aren’t far off. The additional labels on each list are also helpful to double-check each sub-section of the list (while the text shows such labels with pointer arrows, I’d rather only have one on the very first label, since the other references don’t exist as such in the expression statement.)
The tree representation is certainly simpler, but isn’t that much different than the box-and-pointer. There are just some details removed. It’s less explicit about the underlying data structure, so it’s not as if the box-and-pointer diagrams have no place.
This exercise doesn’t have much to it, once you’ve already solved it. Hopefully using the testing function made it easier to find out what was right and what was wrong. One thing to point out is that any expression to find a (numeric or similar) value necessarily begins with
cdr will always return a list.
Again, not much to talk about here. If any of these are difficult to follow, putting together the box-and-pointer diagrams may help to develop an understanding of the difference between lists and pairs.
It’s not hard to build this on the pattern of the original
reverse from 2.18. There simply needs to be an extra condition to check if the current item being ‘moved’ is itself a list. In that case, we recursively run
deep-reverse on that list. In my procedure, I used the
list? predicate, which I don’t think is mentioned in the text, but is quite useful here. For the tests I put in,
pair? would also work, although passing in an actual non-list pair might result in errors.
This is similar to the previous problem. We’re still looking for list elements within lists and going into them (a ‘deep’ procedure), so it has the same conditional structure as
deep-reverse. The difference is in how the result is formed. This time I went with
append to join sub-lists together, ensuring that the left-to-right order is preserved. In the last statement of the condition, where the final fringe values are found, they need to be wrapped in a list. That way the procedure above them doesn’t need to care whether it operated on a fringe element or a section of the tree.
Now we’re applying the techniques we’ve used so far to working with data structures. In part a, we need to pull out the right element from a list using
cdr, as in 2.25. Parts b and c are both procedures that traverse the structure, in much the same way as 2.27 and 2.28.
I’ll compare how I did this one to my solution for
fringe in the previous exercise.
total-weight in such a way as to make use of another procedure,
branch-weight. Using this procedure and the selectors for the mobile structure allows
total-weight to be written very simply: it is the sum of the branch-weight of the left branch and the branch-weight of the right branch.
Taking the two mutually recursive routines together, the procedure is still quite similar to
fringe. We test to see if we’re at an endpoint of the structure or if we’re at a node that can go ‘deeper’. If it’s an endpoint, we get its value (using
branch-weight), and if not, we recurse until complete. Fringe also deals with trees of indeterminate ‘width’ and so needs to check for the end of the list;
total-weight does not need this as a mobile can only have a left or right branch.
Part c ends up using
branch-weight as well, in determining the moment for a particular branch. That again allows the heart of the
balanced? predicate to be one expression, using an internally defined
The mobile is balanced if the left branch and right branch are both balanced, and the moment from the left branch is equal to the moment from the right branch. That’s nearly the same as the exercise’s description of what a balanced mobile is (other than that I called it ‘moment’ instead of ‘torque’).
In case it isn’t clear at this point, using recursive data structures (like most trees, where each node is effectively a tree itself) naturally gives rise to recursive procedures for working with them. They often end up being at least superficially similar to each other in several aspects.
In part d the constructors are changed, and we need to see what else has to change around them. Ideally, only the selectors would need changing, as that is the point of having them in the first place. My additional predicates
is-branch? end up changing too; if you’ve created the other procedures in such a way that they don’t ‘know’ about the internal mobile structure and interact using only constructors and selectors, they ought to remain unchanged as well.
The first way to define
square-tree is the by-now-familiar method of a
cond statement testing whether we’re at an ‘internal node’ of the tree or a ‘leaf [node]’. In the former case, we recurse (constructing the new tree from subtrees), and in the latter we process it.
map, some of the same structure can be seen. The test that we pass to map is the same – figure out if this node is internal or a leaf, and process accordingly. With map, we don’t need to bother with constructing the output tree, or checking when we’ve finished, as those are handled automatically.
tree-map after making
square-tree with a map is quite easy. Just look through
square-map for all the times we call
sqr in the case of Racket), and replace them with a named argument. If
square is passed as that argument, then the result will be the same. The only other thing is to have the arguments to
tree-map in the right order, so that they match the procedure’s ‘signature’ given in the text.
As the routine suggests,
rest is the set of subsets of the ‘rest’ of the list, that is, the
cdr. Assuming we have all of those properly created, then we can create all subsets that include the element at the head of the list (in other words, the
s) by adding the head to each member of
rest. We can do that by creating a new set (i.e. list) using
cons and our head element. Our routine to pass to
lambda(x) (cons (car s) x).
It’s important in this case that the null set (empty list) be used as the base to add elements to, otherwise we could not build up the subsets from individual elements. Once we’ve created our new set that includes an element, it is appended to our current group, and that becomes the new
rest as we move up the list (backing out of calls to
subsets in the
For illustration, the
rest set would develop as shown below for the list
(1 2 3). The vertical bar is used as a marker to distinguish the newly added subsets from the ‘old’ set.