Quirksand

SICP

SICP 2.2.1 Solutions

May 11, 2014 22:36

Ex 2.17.

This one isn’t too hard, but there is an important detail that needs to be observed. The title of the procedure is last-pair. Yet it only returns a single element from the list. The function is required to return a list, not just the last member of it. The pair in question, then, is the pair that makes up a list : one points to the final element, and the second is nil.

I wrote this two different ways, the first of which is as follows:

(define (last-pair li)
  (list (list-ref li (- (length li) 1)))
  )

This method, while short, is clearly rather inefficient if you consider how much processing it does on the list. It also raises an interesting question. Arguably the requirement for the function is worded a bit curiously, as it refers to ‘the list that contains only the last element’ (emphasis mine). Should this mean we need to somehow get the last pair as it occurs in the list that was the argument passed to the function? Or is another newly-generated list acceptable? Are they actually the same thing? Those questions are important and are considered later on in the book, but for now, I’d think any list that contains a matching value to be acceptable.

Ex 2.18.

Reversing a list is of course a common enough operation that reverse is built into just about any dialect of Scheme, and it’s also one that’s not too difficult to implement. The key idea is to have a list that can be built up by adding elements from the first list to it. By proceeding down the original list, and adding the elements to the front of the second list, you get a reversed list.

Ex 2.19.

Here we revisit an old function, and expand on its usefulness with a few new features. Figuring out how to access the lists is pretty simple. The names suggest very similar list operations, to wit: car, cdr, and null? (the version of Scheme I’m using also allows empty? as a synonym for null? when checking a list).

In this rewrite we are keeping the code similar by using a separate function to get at the data structure. Recall that in the original version of cc, there were no list structures involved. Instead, first-denomination was just a procedure that used a cond statement with an index of the coin ‘kind’.

Certainly we could get away with using even this new version with the same procedure (except-first-denomination and no-more? can be defined using math, which can practically be lifted out of the first version of cc as well). It wouldn’t give us the flexibility or simplicity of having a single list that doesn’t bother with an index. We find that separating the function allows us to work with whatever is easier underneath without having to change what’s going on at the higher level.

The second part of the question asks whether the order of the list affects the answer produced. It is true that it does not affect the answer – either way, all the combinations will be found. However, by ordering the list from largest to smallest, the correct answer is found more quickly. If we look back at the recursive tree structure discussed in 1.2.2, we find that fewer branches are created at the top when the larger denominations appear first. Going with the smaller denominations first means many more branches that will branch to false solutions will be created. In the solutions file I ran a test of the time taken to calculate it, and it came out roughly 4 times longer for the example values.

Ex 2.20.

This exercise is essentially here to introduce and use the dotted-tail notation. It’s pretty easy to do, as long as you consider the external and internal usage separately. Internal to the procedure we simply have two arguments, one of which will be a list. Externally (that is to say, when calling the procedure) we give it as many arguments as we like. Whatever doesn’t fit past the ‘signature’ ends up being collected as a list, no matter how many are in it. Note that the list can be empty, which allows for optional arguments if we so desire.

As for the parity checker itself. Again we’re building a second list. This time we’re only adding elements to the list if they pass a particular test. My implementation is perhaps a bit more abstract than necessary (by assigning the predicate even? or odd? to checker), but it does end up shorter at the top level. In the end we top off the list by adding our first argument back to it (something implied by the problem statement and made clear by the examples).

Ex 2.21.

Now we start to see some useful ways to iterate over a list. The first version of square-list again just builds up a new list after stepping through each element in the list. Solving 2.20 and this one show the pattern that map implements by taking care of this common task for you.

Ex 2.22.

The second part of this problem suggests the answer to the first part. The cons statement is putting the newly-computed value at the head of the list, but taking the items for computation in order from the start of the list. This is effectively the same way we created the reverse procedure, and as a result, the answer list comes back in the wrong order.

Unfortunately we find that simply reversing this statement doesn’t do what we’d like either. This is because of the nature of lists and how cons works.

To use a simple notation, consider a pair as [a . b] (bear in mind all elements are pointers, as described at the start of section 2 in the text). When a pair is an member of a list, it is of the form [item . list], where the second element of the pair (i.e. the cdr) is another list. If all we do is reverse the arguments to cons, we build it as [list . item]. That produces a simple pair in which the first element is a list. The second routine doesn’t build a list; it embeds the results in a series of pairs. In this case only the innermost is of the form [list . item], as the rest are actually [pair . item] .

Ex 2.23.

As I mentioned in the preview for the exercises, for-each will be very useful to save time in iterating over a set of test values (and in many cases within other procedures as well). Implementing it is almost the same as map, except that we don’t need to hang on to the list. When moving down the list we’d like to first do one thing and ignore its result, and then do the next one and so on down the list. An internal procedure handles these steps for us, although conceivably this could be built even more like map (or a similar iterative procedure) as long as the returned result is the arbitrarily chosen value, and we ensure that the execution of each procedure is handled in the correct order.

Solutions 2.2.1