Section 41

Designing Functions that Change Structures

Sections 39 and 40 gradually introduced the idea of mutable structures. In the first of the two sections we studied the idea of changing a locally defined variable through a function. In the second one, we discussed how structures could be modified, too.

Now we need to learn when and how to use this new power. The first subsection concerns the question of why a program should modify a structure. The second reviews how the existing design recipes apply when we wish to use mutators. The third one discusses some difficult cases. The last one is dedicated to the differences between set! and structure mutators.

41.1  Why Mutate Structures

Whenever we apply a structure constructor, we create a new structure. On some occasions, this is truly what we want. Consider a function that consumes a list of personnel records and produces a list of phone book entries. The personnel records may contain information about a person's address, including the phone number, date of birth, marital status, closest relatives, and salary level. The entry for the phone book should contain the name and the phone number and nothing else. This kind of program should definitely generate a new structure from each structure in the given list.

On other occasions, though, creating a new structure doesn't correspond to our intuition. Suppose we wish to give someone a raise. The only way of accomplishing this at the moment is to create a new personnel record that contains all the old information and the new salary information. Or, suppose someone has moved and received a new phone number, and we wish to update the phone book on our PDA. Just like the program that changes a person's salary level, the program that updates the phone book would create a new phone book entry. In reality, however, we would not create a new personnel record or a new entry in the phone book. We would instead correct the existing personnel record and the existing entry in our phone book. A program should be able to perform the same kind of corrective action and, with mutators, we can indeed develop such programs.

Roughly speaking, the examples suggest two cases. First, if a structure corresponds to a physical object and the computation corresponds to a corrective action, the program may mutate the structure. Second, if a structure does not correspond to a physical object or if the computation creates a new kind of value from existing information, the program should create a new structure. These two rules are not clear-cut. We will often encounter situations where both solutions are feasible. In that case, we must consider an ease-of-programming argument. If one of the two solutions is easier to design -- often the creation of a new structure, choose it. If the decision leads to a performance bottleneck -- and only then, restructure it.

41.2  Structural Design Recipes and Mutation, Part 1

Surprisingly, programming with mutators does not require any new design recipes -- as long as the mutated fields always contain atomic values. Our receipes work perfectly fine. While the design of non-mutating programs requires the combination of values, programming with mutators requires the combination of effects. Hence the key is to add a well-formulated effect statement to a function's contract and to make up examples that illustrate the effects. We practiced both of these activities for set! expressions already in section 36. In this section we learn to adapt the design recipes and effect statements to structural mutations. To do that, we consider a short series of examples. Each illustrates how an applicable design recipe helps with the design of structure-modifying or vector-modifying functions.

The first example concerns the mutation of plain structures. Suppose we are given a structure and a data definition for personnel records:

(define-struct personnel (name address salary))
;; A personnel record (PR) is a structure: 
;; (make-personnel n a s)
;; where n is a symbol, a is a string, and s is a number. 

A function that consumes such a record is based on the following template:

(define (fun-for-personnel pr)
  ... (personnel-name pr) ...
  ... (personnel-address pr) ...
  ... (personnel-salary pr) ...)  

Consider a function for increasing the salary field:

;; increase-salary : PR number  ->  void
;; effect: to modify the salary field of a-pr by adding a-raise
(define (increase-salary a-pr a-raise) ...)

The contract specifies that the function consumes a PR and a number. The purpose statement is an effect statement, which explains how the argument of increase-salary is modified.

Developing examples for increase-salary requires the techniques of section 36. Specifcially, we must be able to compare the before and after state of some PR structure:

(local ((define pr1 (make-personnel 'Bob 'Pittsburgh 70000)))
  (begin
    (increase-salary pr1 10000)
    (= (personnel-salary pr1) 80000)))

The result of the expression is true if, and only if, increase-salary works properly for this example.

We can now use the template and the example to define the function:

;; increase-salary : PR number  ->  void
;; effect: to modify the salary field of a-pr by adding in a-raise
(define (increase-salary a-pr a-raise)
  (set-personnel-salary! a-pr (+ (personnel-salary a-pr) a-raise)))

As usual, the full definition uses only one of several subexpressions from the template, but the template reminds us of what information we can use: the arguments and their pieces; and what parts we can modify: the fields for which we have selectors.

Exercise 41.2.1.   Make up examples for increase-salary and test the function. Formulate the tests as boolean-valued expressions.    Solution

Exercise 41.2.2.   Adapt increase-salary such that it accepts only values for a-raise between 3% and 7% of the salary. It calls error otherwise.    Solution

Exercise 41.2.3.   Develop increase-percentage. The function consumes a PR and a percentage between 3% and 7%. It increases the value in the salary field of the PR by the lesser of the percentage increase or 7000.    Solution

Exercise 41.2.4.   Develop the function new-date. It consumes a cheerleader record and adds a date to the beginning of a list. Here are the relevant definitions:

(define-struct cheerleader (name dates))
;; A cheerleader is a structure: 
;; (make-cheerleader n d)
;; where n is a symbol and d is a list of symbols. 

For example, (make-cheerleader 'JoAnn '(Carl Bob Dude Adam Emil)) is a valid cheerleader record. Develop an example that shows what it means to add 'Frank as a date.    Solution

Exercise 41.2.5.   Recall the structure definitions for squares:

(define-struct square (nw length))

The matching data definition specifies that the nw field is always a posn structure and that length is a number:

A square is a structure:

Develop the function move-square!. It consumes a square, called sq, and a number, called delta. It modifies sq by adding delta to its x coordinate.

Look up the structure and data definition for circles and develop the function move-circle, which is analogous to move-square.    Solution

The second example recalls the design recipe for functions that work on unions of classes. One of our first examples of this kind concerned the class of geometric shapes. Here is the relevant data definition:

A shape is either

1. a circle, or

2. a square.

See exercise 41.2.5 or part I for the definitions of circle and square.

Following our recipe, a template for shape-processing functions consists of a two-clause cond-expression:

(define (fun-for-shape a-shape)
  (cond
    [(circle? a-shape) ... (fun-for-circle a-shape) ...]
    [(square? a-shape) ... (fun-for-square a-shape) ...]))

Each cond-clause refers to a function with the same purpose for the matching kind of shape.

So, suppose we wish to move a shape in the x direction by a fixed number of pixels. In part I, we created a new structure for this purpose. Now we can use the mutators for circle and square structures instead -- that is, the function can have an effect:

;; move-shape! : shape number  ->  void
;; effect: to move a-shape in the x direction by delta pixels
(define (move-shape! a-shape)
  (cond
    [(circle? a-shape) (move-circle a-shape delta)]
    [(square? a-shape) (move-square a-shape delta)]))

The functions move-circle and move-square are the subject of execise 41.2.5 because they consume and affect plain structures.

Exercise 41.2.6.   Make up examples for move-shape! and test the function. Formulate the tests as boolean-valued expressions!    Solution

Exercise 41.2.7.   The following structure definitions are to represent items that a music store sells:

(define-struct CD (price title artist))
(define-struct record (price antique title artist))
(define-struct DVD (price title artist to-appear))
(define-struct tape (price title artist))

Provide a data definition for the class of music items, which comprises cds, records, dvds, and tapes. The price must be a number in each case.

Develop the program inflate!, which consumes a music-item and a percentage. Its effect is to increase the price in the given structure according to the percentage.    Solution

Exercise 41.2.8.   Develop a program that keeps track of the feeding of zoo animals. Our zoo has three kinds of animals: elephants, monkeys, and spiders. Each animal has a name and two feeding times per day: morning and evening. Initially a structure that represents an animal (structure) contains false in the fields for feeding times. The program feed-animal should consume a structure that represents an animal and the name of a feeding time. It should switch the corresponding field in the animal structure to true.    Solution

The next two examples are about mutations when the underlying data definitions involve self-references. Self-references are needed if we wish to deal with data that has no size limit. Lists were the first class of such data we encountered and natural numbers the second one.

Let's first take a look at mutation of lists of structures, using the running data example of this part: the address book. An address book is a list of entries; for completeness, here are the structure and data definitions:

(define-struct entry (name number))

An entry is a structure:

An address-book is

1. the empty list, empty, or

2. (cons an-e an-ab) where an-e is an entry and an-ab is an address book.

Only the second one is self-referential, so we focus on the template for it:

;; fun-for-ab : address-book  ->  XYZ
(define (fun-for-ab ab)
  (cond
    [(empty? ab) ...]
    [else ... (fun-for-entry (first ab)) ... (fun-for-ab (rest ab)) ...]))

If we needed an auxiliary function for processing an entry, we might also wish to write out the template for structure-processing functions.

So suppose we want a function that updates an existing entry. The function consumes an address-book, a name, and a phone number. The first entry that contains the name is modified to contain the new phone number:

;; change-number! : symbol number address-book  ->  void
;; effect: to modify the first entry for name in ab so that its
;; number field is phone
(define (change-number! name phone ab) ...)

It is justified to develop this function with mutators because just as in reality, most of the address book stays the same while one entry is changed.

Here is an example:

(define ab
  (list
    (make-entry 'Adam 1)
    (make-entry 'Chris 3)
    (make-entry 'Eve 2)))

(begin
  (change-number! 'Chris 17 ab)
  (= (entry-number (second ab)) 17))

The definition introduces ab, an address-book with three items. The begin-expression first changes ab by associating 'Chris with 17; then it compares the phone number of the second item on ab with 17. If change-number! functions properly, the result of the begin-expression is true. An even better test would ensure that nothing else in ab changes.

The next step is to develop the function definition, using the template and the examples. Let's consider each case separately:

1. If ab is empty, name doesn't occur in it. Unfortunately, the purpose statement doesn't specify what the function should compute in this case, and there is indeed nothing sensible the function can do. To be safe, we use error to signal that no matching entry was found.

2. If ab contains a first entry, it might or might not contain name. To find out, the function must distinguish the two cases with a cond-expression:

   (cond
     [(symbol=? (entry-name (first ab)) name) ...]
     [else ...])
   

   In the first subcase, the function must modify the structure. In the second, name can occur only in (rest ab), which means the function must mutate some entry in the rest of the list. Fortunately, the natural recursion accomplishes just that.

Putting everything together, we get the following definition:

(define (change-number! name phone ab)
  (cond
    [(empty? ab) (error 'change-number! "name not in list")]
    [else (cond
            [(symbol=? (entry-name (first ab)) name)
             (set-entry-number! (first ab) phone)]
            [else 
             (change-number! name phone (rest ab))])]))

The only unique aspect of this function is that it uses a structure mutator in one of the cases. Otherwise it has the familiar recursive shape: a cond with two clauses and a natural recursion. It is especially instructive to compare the function with contains-doll? from section 9.3 and contains? from exercise 9.3.3.

Exercise 41.2.9.   Define test-change-number. The function consumes a name, a phone number, and an address book. It uses change-number! to update the address book, and then ensures that it was changed properly. If so, it produces true; if not, it produces an error message. Use this new function to test change-number! with at least three different examples.    Solution

Exercise 41.2.10.   Develop move-squares. It consumes a list of squares, as defined above, and a number delta. The function modifies each on the list by adding delta to the x-component of its position.    Solution

Exercise 41.2.11.   Develop the function all-fed. It consumes a list of animals, as defined in exercise 41.2.8, and modifies them so that their field for morning feedings is switched to true.    Solution

Exercise 41.2.12.   Develop the function for-all, which abstracts move-squares and all-fed from exercises 41.2.10 and 41.2.11. It consumes two values: a function that consumes structures and produces (void); and a list of structures. Its result is (void).    Solution

Exercise 41.2.13.   Develop the function ft-descendants. It consumes a descendant family tree (see section 15.1) based on the following structure definition:

(define-struct parent (children name date eyes no-descendants))

The last field in a parent structure is originally 0. The function ft-descendants traverses the tree and modifies these slots so that they contain the total number of descendants of the corresponding family member. Its result is the number of total descendants of the given tree.    Solution

Natural numbers make up another class of values that requires a self-referential description. Recursion on natural numbers per se isn't useful in conjunction with mutation, but recursion on natural numbers as indices into vectors is useful when a problem's data representation involves vectors.

Let's start with a snippet of an elevator control program. An elevator control program must know at which floor people have pressed the call buttons. We assume that the elevator hardware can mutate some status vector of booleans. That is, we assume that the program contains a vector, call it call-status, and that a field in call-status is true if someone has pushed the call button at the corresponding floor.

One important elevator operation is to reset all the buttons. For example, an operator may have to restart the elevator after it has been out of service for a while. We start the development of reset by restating the known facts in a Scheme outline:⁷⁶

;; call-status : (vectorof boolean)
;; to keep track of the floors from which calls have been issued 
(define call-status (vector true true true false true true true false))

;; reset :  ->  void
;; effect: to set all fields in call-status to false
(define (reset) ...)

The first definition specifies call-status as a state variable, but of course we use each slot in the vector as a state value, not the entire variable. The second part consists of three pieces: a contract, an effect statement, and a header for the function reset, which implements the informally specified service.

While it is possible to implement the service as

(define (reset)
  (set! call-status
    (build-vector (vector-length call-status) (lambda (i) false))))

this trivial solution is clearly not what we want because it creates a new vector. Instead, we want a function that modifies each field of the existing vector. Following the suggestions of intermezzo 5, we develop an auxiliary function with the following template:

;; reset-aux : (vectorof boolean) N  ->  void
;; effect: to set the fields of v with index in [0, i) to false
(define (reset-aux v i) 
  (cond
    [(zero? i) ...]
    [else ... (reset-aux v (sub1 i)) ...]))

That is, the auxiliary function consumes not only the vector but also an interval bound. The shape of the template is based on the data definition of the latter.

The effect statement suggests the following examples:

1. (reset-aux call-status 0) leaves call-status unchanged, because the purpose statement says to change all indices in [0,0) and there are none;

2. (reset-aux 1) changes call-status so that (vector-ref call-status 0) is false, because 0 is the only natural number in [0, 1);

3. (reset-aux call-status (vector-length call-status)) sets all fields of call-status to false.

The last example implies that we can define reset with (reset-aux call-status (vector-length call-status)).

Equipped with examples, we can turn our attention to the definition. The key is to remember that the additional argument must be interpreted as an index into the vector. Keeping the example and the guideline in mind, let's look at each of the two cases separately:

1. If (zero? i) holds, the function has no effect and produces (void).

2. Otherwise i is positive. In that case, the natural recursion sets all fields in call-status with an index in [0,(sub1 i)) to false. Furthermore, to complete the task, the function must set the vector field with index (sub1 i) to false. The combination of the two effects is achieved with a begin-expression that sequences the natural recursion and the additional vector-set!.

Figure 118 puts everything together. The second clause in the definition of reset-aux changes the vector at index (sub1 i) and then uses the natural recursion. Its result is the result of the begin-expression.

;; call-status : (vectorof boolean)
;; to keep track of the floors from which calls have been issued 
(define call-status (vector true true true false true true true false))

;; reset :  ->  void
;; effect: to set all fields in call-status to false
(define (reset)
  (reset-aux call-status (vector-length call-status)))

;; reset-aux : (vectorof boolean) N  ->  void
;; effect: to set the fields of v with index in [0, i) to false
(define (reset-aux v i)
  (cond
    [(zero? i) (void)]
    [else (begin
	    (vector-set! v (sub1 i) false)
	    (reset-aux v (sub1 i)))]))

Exercise 41.2.14.   Use the examples to develop tests for reset-aux. Formulate the tests as boolean-valued expressions.    Solution

Exercise 41.2.15.   Develop the following variant of reset:

;; reset-interval : N N  ->  void
;; effect: to set all fields in [from, to] to false
;; assume: (<= from to) holds 
(define (reset-interval from to) ...)

Use reset-interval to define reset.    Solution

Exercise 41.2.16.   Suppose we represent the position of an object with a vector and the velocity of an object with a second vector. Develop the function move!, which consumes a position vector and an equally long velocity vector. It modifies the position vector by adding in the numbers of the speed vector, field by field:

;; move! : (vectorof number) (vectorof number)  ->  void
;; effect: to add the fields of v to the corresponding fields of pos 
;; 
;; assumption: pos and v have equal length
(define (move! pos v) ...)

Justify why the use of a vector-modifying function is appropriate to model the movement of an object.    Solution

Exercise 41.2.17.   Develop the function vec-for-all, which abstracts reset-aux and the auxiliary vector-processing function for move! from exercise 41.2.16. It consumes two values: a function f and a vector vec. The function f consumes indices (N) and vector items. The result of vec-for-all is (void); its effect is to apply f to each index and corresponding value in vec:

;; vec-for-all : (N X  ->  void) (vectorof X)  ->  void
;; effect: to apply f to all indices and values in vec
;; equation: 
;; (vec-for-all f (vector v-0 ... v-N)) 
;; = 
;; (begin (f N v-N) ... (f 0 v-0) (void))
(define (vec-for-all f vec) ...)

Use vec-for-all to define vector*!, which consumes a number s and a vector of numbers and modifies the vector by multiplying each field's value with s.    Solution

The last example covers the common situation when we wish to compute several numeric values at once and place them in a vector. In section 37 we saw that the use of effects is on occasion useful to communicate several results. In the same manner, it is sometimes best to create a vector and to modify it within the same function. Consider the problem of counting how many times each vowel occurs in a list of letters:

;; count-vowels : (listof letter) 
;;           ->  (vector number number number number number)
;; where a letter is a symbol in 'a ... 'z
;; to determine how many times the five vowels occur in chars
;; the resulting vector lists the counts in the lexicographic order
(define (count-vowels chars) ...)

The choice of vector as a result is appropriate because the function must combine five values into one and each of the values is equally interesting.

Using the purpose statement, we can also come up with examples:

  (count-vowels '(a b c d e f g h i))
= (vector 1 1 1 0 0)

  (count-vowels '(a a i u u))
= (vector 2 0 1 0 2)

Given that the input is a list, the natural choice for the template is that for a list-processing function:

(define (count-vowels chars)
  (cond
    [(empty? chars) ...]
    [else ... (first chars) ... (count-vowels (rest chars)) ... ]))

;; count-vowels : (listof letter) 
;;           ->  (vector number number number number number)
;; where a letter is a symbol in 'a ... 'z
;; to determine how many times the five vowels occur in chars
;; the resulting vector lists the counts in the lexicographic order
(define (count-vowels chars)
  (cond
    [(empty? chars) (vector 0 0 0 0 0)]
    [else
     (local ((define count-rest (count-vowels (rest chars))))
       (begin
         (count-a-vowel (first chars) count-rest)
         count-rest))]))

;; count-a-vowel : letter (vector number number number number number)  ->  void
;; effect: to modify counts at the appropriate place if l is a vowel, 
;; none otherwise
(define (count-a-vowel l counts) 
  ...)

To fill the gaps in the template, we consider each of the two clauses:

1. If (empty? chars) is true, the result is a vector of five 0's. After all, there are no vowels in an empty list.

2. If chars isn't empty, the natural recursion counts how many vowels and which ones occur in (rest chars). To get the correct result, we also have to check whether (first chars) is a vowel, and depending on the outcome, increase one of the vector fields. Since this kind of task is a separate, repeated task, we leave it to an auxiliary function:

   ;; count-a-vowel : letter
   ;;      (vector number number number number number)  ->  void
   ;; effect: to modify counts at the appropriate place if l is a vowel, 
   (define (count-a-vowel l counts) 
     ...)
   

   In other words, the second clause first counts the vowels in the rest of the list. This computation is guaranteed to yield a vector according to the purpose statement. Let's call this vector counts. Then, it uses count-a-vowel to increase the appropriate field in counts, if any. The result is counts, after the first letter on the list has been counted.

Figure 119 contains the complete definition of the main function. Defining the auxiliary function follows the recipe for non-recursive structure mutations.

Exercise 41.2.18.   Develop the function count-a-vowel. Then test the complete count-vowels program.    Solution

Exercise 41.2.19.   At the end of intermezzo 5, we could have defined count-vowels as shown in figure 120. This version does not use vector-set!, but constructs the vector directly using build-vector.

(define (count-vowels-bv chars)
  (local ((define (count-vowel x chars)
            (cond
              [(empty? chars) 0]
              [else (cond
                      [(symbol=? x (first chars))
                       (+ (count-vowel x (rest chars)) 1)]
                      [else (count-vowel x (rest chars))])])))
    (build-vector 5 (lambda (i) 
                      (cond
                        [(= i 0) (count-vowel 'a chars)]
                        [(= i 1) (count-vowel 'e chars)]
                        [(= i 2) (count-vowel 'i chars)]
                        [(= i 3) (count-vowel 'o chars)]
                        [(= i 4) (count-vowel 'u chars)])))))

Measure the performance difference between count-vowels-bv and count-vowels. Hint: Define a function that generates a large list of random letters (with, say, 5,000 or 10,000 items).

Explain the performance difference between count-vowels-bv and count-vowels. Does the explanation reflect the measured difference? What does this suggest concerning the vector-set! operation?    Solution

Exercise 41.2.20.   Develop histogram. The function consumes a list of grades between 0 and 100; it produces a vector of size 101 where each slot contains the number of grades at that level.    Solution

Exercise 41.2.21.   Develop count-children. The function consumes a descendant family tree, which is a family tree that leads from a family member to the descendants. It produces a vector with six fields. The first five slots contain the number of family members that have that many children; the sixth field contains the number of family members that have five or more children.    Solution

41.3  Structural Design Recipes and Mutation, Part 2

In the preceding sections, we studied structure mutation for fields that contain atomic data. We know, however, that structures can contain structures. Starting in section 14.1, we even encountered self-referential data definitions involving structures in structures. On occasion, processing such classes of data may also require mutations of structure fields that contain structures. In this section, we work through one such example.

Figure 121:  Playing with cards

Suppose we wish to simulate a card game as a program. Each card has two important characteristics: its suit and its rank. A player's collection of cards is called a hand. For now we also assume that every player has at least one card, that is, a hand is never empty.

Figure 121 contains a screen shot of DrScheme with structure and data definitions for manipulating cards and hands. The program fragment does not introduce separate classes of cards and hands, but a single structure and a single data definition for hands. A hand consists of a hand structure, which contains a rank, a suit, and a next field. The data definition shows that the next field may contain two kinds of values: empty, which means that there are no other cards, and a hand structure, which contains the remainder of the cards. From a global perspective, a hand forms a chain of cards; only the last one contains empty in the next field.⁷⁷

At first, a player has no cards. Picking up the first card creates a hand. Others cards are then inserted into the existing hand as needed. This calls for two functions: one for creating a hand and another one for inserting a card into a hand. Because a hand exists only once and corresponds to a physical object, it is natural to think of the second function as one that modifies an existing value rather than building a new one. For now, we accept this premise and explore its consequences.

Creating a hand is a simple act and easy to implement as a function:

;; create-hand : rank suit  ->  hand
;; to create a single-card hand from r and s
(define (create-hand r s)
  (make-hand r s empty))

The function consumes the properties of a card; it creates a hand with one card and no others.

(define hand0 (create-hand 13 spades)) rank suit next 13 empty (add-at-end! diamonds 1 hand0) rank suit next 13 rank suit next 13 empty Figure 122:  Building a hand

Adding a card to the end of a hand is a more difficult task. To simplify our life a bit, let's say that a player always adds new cards to the end of the hand. In this case we must process an arbitrarily large value, which means we need a recursive function. Here are the contract, effect statement, and header:

;; add-at-end! : rank suit hand  ->  void
;; effect : to add a card with r as rank and s as suit at the end 
(define (add-at-end! rank suit a-hand) ...)

These specifications say that the function has the invisible value as the result and that it communicates with the rest of the program exclusively through its effects.

Let's start with examples:

(define hand0 (create-hand 13 SPADES))

If we were to evaluate the following expression

(add-at-end! 1 DIAMONDS hand0)

in the context of this definition, hand0 becomes a hand with two cards: a spades-13 followed by a diamonds-1. Figure 122 depicts the change of hand0; the top half displays the initial state of hand0, the lower half displays the state after add-at-end! has added a card. If we furthermore evaluate

(add-at-end! 2 CLUBS hand0))

in this context, hand0 becomes a hand with three cards. The last one is a clubs-2. In terms of an evaluation, the definition of hand0 should change to

(define hand0 
  (make-hand 13 SPADES
    (make-hand 1 DIAMONDS
      (make-hand 2 CLUBS empty))))

after both additions have been carried out.

Given that the rank and suit argument to add-at-end! are atomic values, the template must be based on the data definition for hands:

(define (add-at-end! rank suit a-hand)
  (cond
    [(empty? (hand-next a-hand)) 
     ... (hand-rank a-hand) ... (hand-suit a-hand) ...]
    [else ... (hand-rank a-hand) ... (hand-suit a-hand) ...
     ... (add-at-end! rank suit (hand-next a-hand)) ...]))

The template consists of two clauses, which check the content of the next field of a-hand. It is recursive in the second clause, because the data definition for hands is self-referential in that clause. In short, the template is completely conventional.

The next step is to consider how the function should affect a-hand in each clause:

1. In the first case, a-hand's next field is empty. In that case, we can modify the next field so that it contains the new card:

   (set-next-hand! a-hand (make-hand rank suit empty))
   

   The newly created hand structure is now the one that contains empty in its next field, that is, it is the new end of the a-hand value.

2. In the second case, the natural recursion adds a new card to the end of a-hand. Indeed, because the given a-hand isn't the last one in the chain, the natural recursion does everything that needs to be done.

Here is the complete definition of add-at-end!:

;; add-at-end! : rank suit hand  ->  void
;; effect: to add a card with v as rank and s as suit at the end of a-hand
(define (add-at-end! rank suit a-hand)
  (cond
    [(empty? (hand-next a-hand))
     (set-hand-next! a-hand  (make-hand rank suit empty))]
    [else (add-at-end! rank suit (hand-next a-hand))]))

It closely resembles the list-processing functions we designed in part II. This should come as no surprise, because add-at-end! processes values from a class that closely resembles the data definition of lists and the design recipes are formulated in a general manner.

Exercise 41.3.1.   Evaluate the following program by hand:

(define hand0 (create-hand 13 SPADES))

(begin
  (add-at-end! 1 DIAMONDS hand0)
  (add-at-end! 2 CLUBS hand0)
  hand0)

Test the function with this example.

Make up two other examples. Recall that each example consists of an initial hand, cards to be added, and a prediction of what the result should be. Then test the function with the additional examples. Formulate the tests as boolean-valued expressions.    Solution

Exercise 41.3.2.   Develop the function last-card. It consumes a hand and produces a list with the last card's rank and suit. How can we use this function to test the add-at-end! function?    Solution

Exercise 41.3.3.   Suppose a family tree consists of structures that record the name, social security number, and parents of a person. Describing such a tree requires a structure definition:

(define-struct child (name social father mother))

and a data definition:

A family-tree-node (short: ftn) is either

1. false, or

2. (make-child name socsec f m) where name is a symbol, socsec is a number, and f and m are ftns.

For now, we assume that everyone has a social security number and that social security numbers are unique.

Following our convention from part III, false represents a lack of knowledge about someone's father or mother. As we find out more information, though, we can add nodes to our family tree.

Develop the function add-ftn!. It consumes a family tree a-ft, a social security number ssc, a symbol anc, and a child structure. Its effect is to modify that structure in a-ft whose social security number is ssc. If anc is 'father, it modifies the father field to contain the given child structure; otherwise, anc is the symbol 'mother and add-ftn! mutates the mother field. If the respective fields already contain a child structure, add-ftn! signals an error.

Using Functions as Arguments: Instead of accepting 'father and 'mother for anc, the function could also accept one of the two structure mutators: set-child-father! or set-child-mother!. Modify add-ftn! accordingly.    Solution

Exercise 41.3.4.   Develop an implementation of a hand with create-hand and add-at-end! services using encapsulated state variables and function definitions. Use set! expression but no structure mutators.    Solution

Not all mutator functions are as easily designed as the add-at-end! function. Indeed, in some cases things don't even work out at all. Let's consider two additional services. The first one removes the last card in a hand. Its contract and effect statement are variations on those for add-at-end!:

;; remove-last! : hand  ->  void
;; effect : to remove the last card in a-hand, unless it is the only one
(define (remove-last! a-hand) ...)

The effect is restricted because a hand must always contain one card.

We can also adapt the example for add-at-end! without difficulty:

(define hand0 (create-hand 13 SPADES))

(begin
  (add-at-end! 1 DIAMONDS hand0)
  (add-at-end! 2 CLUBS hand0)
  (remove-last! hand0)
  (remove-last! hand0))  

The resulting value is void. The effect of the computation is to return hand0 in its initial state.

The template for remove-last! is the same as that for add-at-end! because both functions process the same class of values. So the next step is to analyze what effects the function must compute for each case in the template:

1. Recall that the first clause represents the case when a-hand's next field is empty. In contrast to the situation with add-at-end!, it is not clear what we need to do now. According to the effect statement, we must do one of two things:

   1. If a-hand is the last item in a chain that consists of more than one hand structure, it must be removed.

   2. If a-hand is the only structure that remove-last! consumed, the function should have no effect.

   But we can't know whether a-hand is the last item in a long chain of hands or the only one. We have lost knowledge that was available at the beginning of the evaluation!

The analysis of the first clause suggests the use of an accumulator. We tried the natural route and discovered that knowledge is lost during an evaluation, which is the criterion for considering a switch to an accumulator-based design recipe.

Once we have recognized the need for an accumulator-style function, we encapsulate the template in a local-expression and add an accumulator argument to its definition and applications:

(define (remove-last! a-hand0)
  (local (;; accumulator ... 
	  (define (rem! a-hand accumulator)
	    (cond
	      [(empty? (hand-next a-hand)) 
	       ... (hand-rank a-hand) ... (hand-suit a-hand) ...]
	      [else ... (hand-rank a-hand) ... (hand-suit a-hand) ...
	       ... (rem! (hand-next a-hand) ... accumulator ...) ...])))
    ... (rem! a-hand0 ...) ...))

The questions to ask now are what the accumulator represents and what its first value is.

The best way to understand the nature of accumulators is to study why the plain structural design of remove-last! failed. Hence we return to the analysis of our first clause in the template. When rem! reaches that clause, two things should have been accomplished. First, rem! should know that a-hand is not the only hand structure in a-hand0. Second, rem! must be enabled to remove a-hand from a-hand0. For the first goal, rem!'s first application should be in a context where we know that a-hand0 contains more than one card. This argument suggests a cond-expression for the body of the local-expression:

(cond
  [(empty? (hand-next a-hand)) (void)]
  [else (rem! a-hand0 ...)])

For the second goal, rem!'s accumulator argument should always represent the hand structure that precedes a-hand in a-hand0. Then rem! can remove a-hand by modifying the predecessor's next field:

(set-hand-next! accumulator empty)

Now the pieces of the design puzzle fall into place. The complete definition of the function is in figure 123. The accumulator parameter is renamed to predecessor-of:a-hand to emphasize the relationship to the parameter proper. The first application of rem! in the body of the local-expression hands it the second hand structure in a-hand0. The second argument is a-hand0, which establishes the desired relationship.

;; remove-last! : hand  ->  void
;; effect : to remove the last card in a-hand0, unless it is the only one
(define (remove-last! a-hand0)
  (local (;; predecessor-of:a-hand represents the predecessor of
	  ;; a-hand in the a-hand0 chain 
	  (define (rem! a-hand predecessor-of:a-hand)
	    (cond
	      [(empty? (hand-next a-hand))
	       (set-hand-next! predecessor-of:a-hand empty)]
	      [else (rem! (hand-next a-hand) a-hand)])))
    (cond
      [(empty? (hand-next a-hand0)) (void)]
      [else (rem! (hand-next a-hand0) a-hand0)])))

(rem! (hand-next a-hand) a-hand)

It is now time to revisit the basic assumption about the card game that the cards are added to the end of a hand. When human players pick up cards, they hardly ever just add them to the end. Instead, many use some special arrangement and maintain it over the course of a game. Some arrange hands according to suits, others according to rank, and yet others according to both criteria.

Let's consider an operation for inserting a card into a hand based on its rank:

;; sorted-insert! : rank suit hand  ->  void
;; assume: a-hand is sorted by rank, in descending order
;; effect: to add a card with r as rank and s as suit at the proper place
(define (sorted-insert! r s a-hand) ...)

The function assumes that the given hand is already sorted. The assumption naturally holds if we always use create-hand to create a hand and sorted-insert! to insert cards.

Suppose we start with the same hand as above for add-at-end!:

(define hand0 (create-hand 13 SPADES))

If we evaluate (sorted-insert! 1 DIAMONDS hand0) in this context, hands0 becomes

(make-hand 13 SPADES
  (make-hand 1 DIAMONDS empty))

If we now evaluate (sorted-insert! 2 CLUBS hand0) in addition, we get

(make-hand 13 SPADES
  (make-hand 2 CLUBS
    (make-hand 1 DIAMONDS empty)))

for hand0. This value shows what it means for a chain to be sorted in descending order. As we traverse the chain, the ranks get smaller and smaller independent of what the suits are.

Our next step is to analyze the template. Here is the template, adapted to our present purpose:

(define (sorted-insert! r s a-hand)
  (cond
    [(empty? (hand-next a-hand)) 
     ... (hand-rank a-hand) ... (hand-suit a-hand) ...]
    [else ... (hand-rank a-hand) ... (hand-suit a-hand) ...
      ... (sorted-insert! r s (hand-next a-hand)) ...]))

The key step of the function is to insert the new card between two cards such that first card's rank is larger than, or equal to, r and r is larger than, or equal to, the rank of the second. Because we only have two cards in the second clause, we start by formulating the answer for the second clause. The condition we just specified implies that we need a nested cond-expression:

(cond
  [(>= (hand-rank a-hand) r (hand-rank (hand-next a-hand))) ...]
  [else ...])

The first condition expresses in Scheme what we just discussed. In particular, (hand-rank a-hand) picks the rank of the first card in a-hand and (hand-rank (hand-next a-hand)) picks the rank of the second one. The comparison determines whether the three ranks are properly ordered.

Each case of this new cond-expression deserves its own analysis:

1. If (>= (hand-rank a-hand) r (hand-rank (hand-next a-hand))) is true, then the new card must go between the two cards that are currently linked. That is, the next field of a-hand must be changed to contain a new hand structure. The new structure consists of r, s, and the original value of a-hand's next field. This yields the following elaboration of the cond-expression:

   (cond
     [(>= (hand-rank a-hand) r (hand-rank (hand-next a-hand)))
      (set-hand-next! a-hand (make-hand r s (hand-next a-hand)))]
     [else ...])
   

2. If (>= (hand-rank a-hand) r (hand-rank (hand-next a-hand))) is false, the new card must be inserted at some place in the rest of the chain. Of course, the natural recursion accomplishes just that, which finishes the analysis of the second clause of sorted-insert!.

Putting all the pieces together yields a partial function definition:

(define (sorted-insert! r s a-hand)
  (cond
    [(empty? (hand-next a-hand)) 
     ... (hand-rank a-hand) ... (hand-suit a-hand) ...]
    [else 
      (cond
	[(>= (hand-rank a-hand) r (hand-rank (hand-next a-hand)))
	 (set-hand-next! a-hand (make-hand r s (hand-next a-hand)))]
	[else (sorted-insert! r s (hand-next a-hand))])]))

The only remaining gaps are now in the first clause.

The difference between the first and the second cond-clause is that there is no second hand structure in the first clause so we cannot compare ranks. Still, we can compare r and (hand-rank a-hand) and compute something based on the outcome of this comparison:

(cond
  [(>= (hand-rank a-hand) r) ...]
  [else ...])

Clearly, if the comparison expression evaluates to true, the function must mutate the next field of a-hand and add a new hand structure:

(cond
  [(>= (hand-rank a-hand) r) 
   (set-hand-next! a-hand (make-hand r s empty))]
  [else ...])

The problem is that we have nothing to mutate in the second clause. If r is larger than the rank of a-hand, the new card should be inserted between the predecessor of a-hand and a-hand. But that kind of situation would have been discovered by the second clause. The seeming contradiction suggests that the dots in the second clause are a response to a singular case:

The dots are evaluated only if sorted-insert! consumes a rank r that is larger than all the values in the rank fields of a-hand.

At first glance, we can overcome the problem with a set! expression that changes the definition of hand0:

(set! hand0 (make-hand r s hand0))

This fix doesn't work in general though, because we can't assume that we know which variable definition must be modified. Since expressions can be abstracted over values but not variables, there is also no way to abstract over hand0 in this set!-expression.

;; create-hand : rank suit  ->  hand
;; to create a hand from the rank and suit of a single card
(define (create-hand rank suit)
  (local ((define-struct hand (rank suit next))
	  
          (define the-hand (make-hand rank suit empty))
	  
          ;; insert-aux! : rank suit hand  ->  void
          ;; assume: hand is sorted by rank in descending order
          ;; effect: to add a card with r as rank and s as suit
          ;; at the proper place
          (define (insert-aux! r s a-hand)
            (cond
              [(empty? (hand-next a-hand)) 
               (set-hand-next! a-hand (make-hand r s empty))]
              [else (cond
                      [(>= (hand-rank a-hand)
			   r
			   (hand-rank (hand-next a-hand)))
                       (set-hand-next! a-hand
			 (make-hand r s (hand-next a-hand)))]
                      [else (insert-aux! r s (hand-next a-hand))])]))
	  
	  ... ;; other services as needed
	  
          (define (service-manager msg)
            (cond
              [(symbol=? msg 'insert!) 
               (lambda (r s)
                 (cond
                   [(> r (hand-rank the-hand))
                    (set! the-hand (make-hand r s the-hand))]
                   [else (insert-aux! r s the-hand)]))]
              [else (error 'managed-hand "message not understood")])))
    service-manager))

We're stuck. It is impossible to define sorted-insert!, at least as specified above. The analysis suggests a remedy, however. If we introduce a single variable that always stands for the current hand structure, we can use a combination of assignments and structure mutators to insert a new card. The trick is not to let any other part of the program refer to this variable or even change it. Otherwise a simple set! won't work, as argued before. In other words, we need a state variable for each hand structure, and we need to encapsulate it in a local-expression.

Figure 124 displays the complete function definition. It follows the pattern of section 39. The function itself corresponds to create-hand, though instead of producing a structure the new create-hand function produces a manager function. At this point, the manager can deal with only one message: 'insert; all other messages are rejected. An 'insert message first checks whether the new rank is larger than the first one in the-hand, the hidden state variable. If so, the manager just changes the-hand; if not, it uses insert-aux!, which may now assume that the new card belongs into the middle of the chain.

Exercise 41.3.5.   Extend the definition in figure 124 with a service for removing the first card of a given rank, even if it is the only card.    Solution

Exercise 41.3.6.   Extend the definition in figure 124 with a service for determining the suits of those cards in the-hand that have a given rank. The function should produce a list of suits.    Solution

Exercise 41.3.7.   Reformulate create-hand in figure 124 such that the manager uses a single set!-expression and sorted-insert does not use any structure mutation.    Solution

Exercise 41.3.8.   Recall the definition of a binary tree from section 14.2:

A binary-tree (short: BT) is either

1. false or

2. (make-node soc pn lft rgt)
   where soc is a number, pn is a symbol, and lft and rgt are BTs.

The required structure definition is

(define-struct node (ssn name left right))

A binary tree is a binary-search-tree if every node structure contains a social security number that is larger than all those in the left subtree and smaller than all those in the right subtree.

Develop the function insert-bst!. The function consumes a name n, a social security number s, and a bst. It modifies the bst so that it contains a new node with n and s while maintaining it as a search tree.

Also develop the function remove-bst!, which removes a node with a given social security number. It combines the two subtrees of the removed node by inserting all the nodes from the right tree into the left one.    Solution

The discussion in this subsection and the exercises suggest that adding or removing items from linked structures is a messy task. Dealing with an item in the middle of the linked structures is best done with accumulator-style functions. Dealing with the first structure requires encapsulation and management functions. In contrast, as exercise 41.3.7 shows, a solution without mutators is much easier to produce than a solution based on structure mutation. And the case of cards and hands, which deals with at most 52 structures, is equally efficient. To decide which of the two approaches to use requires a better understanding of algorithmic analysis (see intermezzo 5) and of the language mechanisms and program design recipes for encapsulating state variables.

41.4  Extended Exercise: Moving Pictures, a Last Time

In sections 6.6, 7.4, 10.3, and 21.4 we studied how to move pictures across a canvas. A picture is a list of shapes; a shape is one of several basic geometric shapes: circles, rectangles, etc. Following our most basic design principle -- one function per concept -- we first defined functions for moving basic geometric shapes, then for mixed classes of shapes, and finally for lists of shapes. Eventually we abstracted over related functions.

The functions for moving basic shapes create a new shape from an existing shape. For example, the function for moving a circle consumes a circle structure and produces a new circle structure. If we think of the circle as a painting with a round frame and the canvas as a wall, however, creating a new shape for each move is inappropriate. Instead, we should change the shape's current position.

Exercise 41.4.1.   Turn the functions translate-circle and translate-rectangle of exercises 6.6.2 and 6.6.8, respectively, into structure-mutating functions. Adapt move-circle from section 6.6 and move-rectangle from exercise 6.6.12 so that they use these new functions.    Solution

Exercise 41.4.2.   Adapt the function move-picture from exercise 10.3.6 to use the structure-mutating functions from exercise 41.4.1.    Solution

Exercise 41.4.3.   Use Scheme's for-each function (see Help Desk) to abstract where possible in the functions of exercise 41.4.2.    Solution