Now that we have some understanding of the pointer structure of lists, and how to change them, the next few sections present concrete applications. This section (and the next) will cover data structures that can be created by allowing lists to be mutated. Something hinted at near the end of this exercise set is that this approach can provide a great savings in (processing) time, since these changes leave most of the list intact, and don’t require scanning the whole list.

This set of exercises also concerns the way data is presented, irrespective of its internal structure. As such, it’s not as easy to test directly for correctness, since there may be multiple ways of printing out the same data. Furthermore, the ability to even look at what’s being ‘printed’ isn’t an easy thing to do in testing. When we print we would normally use display, which only shows it on screen, not to the testing program. While there are ways to deal with this, in this section some testing results will need to be verified visually, and may depend on the specific implementation. You can thus print out the data in whatever way you see fit.

Since we are again dealing with mutable lists, I’m continuing to use RSR5 Scheme. For DrRacket’s R5RS (and possibly other Scheme implementations of R5RS), there is no error procedure defined. In order to have one that works reasonably similar to the one in the text, it needs to be defined in a special way. This is done at the top of the file and must be uncommented if you want to use it. A few other definitions (such as true and false) are included as an additional convenience.

In addition to the list of operations that the text supplies for testing, I have created a brief set of common operations that exercise queues. Since we’re also trying to avoid having the interpreter print out results we don’t care about, the test operations are defined as a set sequence, which is the simplest way to suppress the output of intermediate steps. Putting it in a procedure also allows us to easily repeat the test when the implementation is altered. Bear in mind that these tests are not set up to handle exceptions, and will still halt the execution of the entire file when an error occurs.

There’s one aspect to the testing that is not meant to be a problem to solve, but just raised as a question: what happens when a queue is printed that includes a queue as one of its elements? I don’t consider it necessary to handle this case in the solutions, but it’s worth it to consider the ways in which this problem could be solved, especially as the text goes on to cover other data structures.

The last exercise involves another type of data structure. It’s one that’s difficult to test in parts, and has the potential to require quite complex tests. I have provided a sequence of steps that should at least run through the basic implementation, but it is by no means comprehensive. As with the regular queue, it may be necessary to suppress the output of intermediate steps (especially in light of the advisory note in the exercise). I took a different approach to the testing here: the sequences use begin blocks that conclude with a quoted statement (similar to the text’s common use of 'done). This should ensure that they only output innocuous text descriptions. The extent of the testing is also limited to just looking at the front and rear, or checking if the deque is empty, since those operations comprise the interface required by the exercise; we should not be testing the internal structure.

Exercises 3.3.2.