# Section 41Designing 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 `local`ly 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-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 `square`s:

```(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:

`(make-square p s)`
where `p` is a `posn` and `s` is a number.

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 `cd`s, `record`s, `dvd`s, and `tape`s. 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:

`(make-entry n p)`
where `n` is a symbol and `p` is a number.

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 '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 `square`s, 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 `animal`s, 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:76

```;; `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)))])) ``` Figure 118:  Resetting call-buttons for an elevator

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) ...) ``` Figure 119:  Counting vowels

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)]))))) ``` Figure 120:  Another way of counting vowels

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.

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

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.

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.

```(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 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 `hand`s:

```(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 `hand`s 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`
(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
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
(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 `hand`s 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)]))) ``` Both applications of `rem!` have the shape ```(rem! (hand-next a-hand) a-hand) ``` Figure 123:  Removing the last card

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`.
In that singular case, `a-hand` shouldn't change at all. After all, there is no way to create a descending chain of cards by mutating `a-hand` or any of its embedded `hand` structures.

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.

 A hand is an interface: `'insert` :: `rank suit  ->  void` ```;; `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)) ``` Figure 124:  Encapsulation and structure mutation for hands of cards

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 `BT`s.

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

76 The notation `(vectorof X)` is analogous to `(listof X)`.

77 Scheme proper provides list mutators, and a Scheme programmer would use them to represent a hand as a list of cards.