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.
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 clearcut. We will often encounter situations where both solutions are feasible. In that case, we must consider an easeofprogramming 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.
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 nonmutating programs
requires the combination of values, programming with mutators requires the
combination of effects. Hence the key is to add a wellformulated 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
structuremodifying or vectormodifying functions.
The first example concerns the mutation of plain structures. Suppose we are given a structure and a data definition for personnel records:
(definestruct personnel (name address salary)) ;; A personnel record (PR) is a structure: ;;(makepersonnel n a s)
;; wheren
is a symbol,a
is a string, ands
is a number.
A function that consumes such a record is based on the following template:
(define (funforpersonnel pr) ... (personnelname pr) ... ... (personneladdress pr) ... ... (personnelsalary pr) ...)
Consider a function for increasing the salary field:
;;increasesalary : PR number > void
;; effect: to modify the salary field ofapr
by addingaraise
(define (increasesalary apr araise) ...)
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 increasesalary
is modified.
Developing examples for increasesalary
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 (makepersonnel 'Bob 'Pittsburgh 70000))) (begin (increasesalary pr1 10000) (= (personnelsalary pr1) 80000)))
The result of the expression is true
if, and only if,
increasesalary
works properly for this example.
We can now use the template and the example to define the function:
;;increasesalary : PR number > void
;; effect: to modify the salary field ofapr
by adding inaraise
(define (increasesalary apr araise) (setpersonnelsalary! apr (+ (personnelsalary apr) araise)))
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 increasesalary
and test the
function. Formulate the tests as booleanvalued
expressions.
Solution
Exercise 41.2.2.
Adapt increasesalary
such that it accepts only values for
araise
between 3% and 7% of the salary. It calls error
otherwise.
Solution
Exercise 41.2.3.
Develop increasepercentage
. 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 newdate
. It consumes a cheerleader
record and adds a date to the beginning of a list. Here are the relevant
definitions:
(definestruct cheerleader (name dates)) ;; A cheerleader is a structure: ;;(makecheerleader n d)
;; wheren
is a symbol andd
is a list of symbols.
For example, (makecheerleader '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:
(definestruct square (nw length))
The matching data definition specifies that the nw
field is always
a posn
structure and that length
is a number:
(makesquare p s)
p
is a posn
and s
is a number.
Develop the function movesquare!
. 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 movecircle
, which is analogous to
movesquare
.
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 circle
, or
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 twoclause condexpression:
(define (funforshape ashape) (cond [(circle? ashape) ... (funforcircle ashape) ...] [(square? ashape) ... (funforsquare ashape) ...]))
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:
;;moveshape! : shape number > void
;; effect: to moveashape
in the x direction bydelta
pixels (define (moveshape! ashape) (cond [(circle? ashape) (movecircle ashape delta)] [(square? ashape) (movesquare ashape delta)]))
The functions movecircle
and movesquare
are the subject
of execise 41.2.5 because they consume and affect plain
structures.
Exercise 41.2.6.
Make up examples for moveshape!
and test the function. Formulate
the tests as booleanvalued expressions!
Solution
Exercise 41.2.7. The following structure definitions are to represent items that a music store sells:
(definestruct CD (price title artist)) (definestruct record (price antique title artist)) (definestruct DVD (price title artist toappear)) (definestruct 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 musicitem
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 feedanimal
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 selfreferences. Selfreferences 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:
(definestruct entry (name number))
(makeentry n p)
n
is a symbol and p
is a number.
the empty list, empty
, or
(cons ane anab)
where ane
is an entry and
anab
is an address book.
Only the second one is selfreferential, so we focus on the template for it:
;; funforab : addressbook > XYZ
(define (funforab ab)
(cond
[(empty? ab) ...]
[else ... (funforentry (first ab)) ... (funforab (rest ab)) ...]))
If we needed an auxiliary function for processing an entry
, we
might also wish to write out the template for structureprocessing
functions.
So suppose we want a function that updates an existing entry. The function
consumes an addressbook
, a name, and a phone number. The first
entry
that contains the name is modified to contain the new phone
number:
;;changenumber! : symbol number addressbook > void
;; effect: to modify the firstentry
forname
inab
so that its ;; number field isphone
(define (changenumber! 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 (makeentry 'Adam 1) (makeentry 'Chris 3) (makeentry 'Eve 2))) (begin (changenumber! 'Chris 17 ab) (= (entrynumber (second ab)) 17))
The definition introduces ab
, an addressbook
with three
items. The beginexpression first changes ab
by
associating 'Chris
with 17
; then it compares the phone
number of the second item on ab
with 17
. If
changenumber!
functions properly, the result of the
beginexpression 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:
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.
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 condexpression:
(cond [(symbol=? (entryname (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 (changenumber! name phone ab) (cond [(empty? ab) (error 'changenumber! "name not in list")] [else (cond [(symbol=? (entryname (first ab)) name) (setentrynumber! (first ab) phone)] [else (changenumber! 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 containsdoll?
from
section 9.3 and contains?
from
exercise 9.3.3.
Exercise 41.2.9.
Define testchangenumber
. The function consumes a name, a phone
number, and an address book. It uses changenumber!
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 changenumber!
with at least three different
examples.
Solution
Exercise 41.2.10.
Develop movesquares
. 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 xcomponent of its
position.
Solution
Exercise 41.2.11.
Develop the function allfed
. 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 forall
, which abstracts
movesquares
and allfed
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 ftdescendants
. It consumes a descendant
family tree (see section 15.1) based on the following
structure definition:
(definestruct parent (children name date eyes nodescendants))
The last field in a parent
structure is originally 0
.
The function ftdescendants
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 selfreferential 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
callstatus
, and that a field in callstatus
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}
;;callstatus : (vectorof boolean)
;; to keep track of the floors from which calls have been issued (define callstatus (vector true true true false true true true false)) ;;reset : > void
;; effect: to set all fields incallstatus
tofalse
(define (reset) ...)
The first definition specifies callstatus
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! callstatus (buildvector (vectorlength callstatus) (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:
;;resetaux : (vectorof boolean) N > void
;; effect: to set the fields ofv
with index in [0
,i
) tofalse
(define (resetaux v i) (cond [(zero? i) ...] [else ... (resetaux 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:
(resetaux callstatus 0)
leaves callstatus
unchanged, because the purpose statement says to change all indices in
[0
,0
) and there are none;
(resetaux 1)
changes callstatus
so that
(vectorref callstatus 0)
is false
, because 0
is the only natural number in [0
, 1
);
(resetaux callstatus (vectorlength callstatus))
sets all
fields of callstatus
to false
.
The last example implies that we can define reset
with
(resetaux callstatus (vectorlength callstatus))
.
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:
If (zero? i)
holds, the function has no effect and produces
(void)
.
Otherwise i
is positive. In that case, the natural recursion
sets all fields in callstatus
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
beginexpression that sequences the natural recursion and the
additional vectorset!
.
Figure 118 puts everything together. The second clause in the
definition of resetaux
changes the vector at index (sub1
i)
and then uses the natural recursion. Its result is the result of the
beginexpression.
Exercise 41.2.14.
Use the examples to develop tests for resetaux
. Formulate the
tests as booleanvalued expressions.
Solution
Exercise 41.2.15.
Develop the following variant of reset
:
;;resetinterval : N N > void
;; effect: to set all fields in [from
,to
] tofalse
;; assume:(<= from to)
holds (define (resetinterval from to) ...)
Use resetinterval
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 ofv
to the corresponding fields ofpos
;; ;; assumption:pos
andv
have equal length (define (move! pos v) ...)
Justify why the use of a vectormodifying function is appropriate to model the movement of an object. Solution
Exercise 41.2.17.
Develop the function vecforall
, which abstracts
resetaux
and the auxiliary vectorprocessing 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
vecforall
is (void)
; its effect is to apply
f
to each index and corresponding value in vec
:
;;vecforall : (N X > void) (vectorof X) > void
;; effect: to applyf
to all indices and values invec
;; equation: ;;(vecforall f (vector v0 ... vN))
;; = ;;(begin (f N vN) ... (f 0 v0) (void))
(define (vecforall f vec) ...)
Use vecforall
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:
;;countvowels : (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 inchars
;; the resulting vector lists the counts in the lexicographic order (define (countvowels 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:
(countvowels '(a b c d e f g h i)) = (vector 1 1 1 0 0) (countvowels '(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 listprocessing function:
(define (countvowels chars) (cond [(empty? chars) ...] [else ... (first chars) ... (countvowels (rest chars)) ... ]))

To fill the gaps in the template, we consider each of the two clauses:
If (empty? chars)
is true
, the result is a vector
of five 0
's. After all, there are no vowels in an empty list.
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:
;;countavowel : letter
;;(vector number number number number number) > void
;; effect: to modifycounts
at the appropriate place ifl
is a vowel, (define (countavowel 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
countavowel
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 nonrecursive structure mutations.
Exercise 41.2.18.
Develop the function countavowel
. Then test the complete
countvowels
program.
Solution
Exercise 41.2.19.
At the end of intermezzo 5, we could have defined countvowels
as
shown in figure 120. This version does not use
vectorset!
, but constructs the vector directly using
buildvector
.

Measure the performance difference between countvowelsbv
and
countvowels
. 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 countvowelsbv
and
countvowels
. Does the explanation reflect the measured
difference? What does this suggest concerning the vectorset!
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 countchildren
. 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
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 selfreferential 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:
;;createhand : rank suit > hand
;; to create a singlecard hand fromr
ands
(define (createhand r s) (makehand 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:
;;addatend! : rank suit hand > void
;; effect : to add a card withr
as rank ands
as suit at the end (define (addatend! rank suit ahand) ...)
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 (createhand 13 SPADES))
If we were to evaluate the following expression
(addatend! 1 DIAMONDS hand0)
in the context of this definition, hand0
becomes a hand with two
cards: a spades13 followed by a diamonds1. Figure 122
depicts the change of hand0; the top half displays the initial state of
hand0
, the lower half displays the state after
addatend!
has added a card. If we furthermore evaluate
(addatend! 2 CLUBS hand0))
in this context, hand0
becomes a hand with three cards. The last
one is a clubs2. In terms of an evaluation, the definition of
hand0
should change to
(define hand0 (makehand 13 SPADES (makehand 1 DIAMONDS (makehand 2 CLUBS empty))))
after both additions have been carried out.
Given that the rank
and suit
argument to
addatend!
are atomic values, the template must be based on the
data definition for hand
s:
(define (addatend! rank suit ahand) (cond [(empty? (handnext ahand)) ... (handrank ahand) ... (handsuit ahand) ...] [else ... (handrank ahand) ... (handsuit ahand) ... ... (addatend! rank suit (handnext ahand)) ...]))
The template consists of two clauses, which check the content of the
next
field of ahand
. It is recursive in the second
clause, because the data definition for hand
s is selfreferential
in that clause. In short, the template is completely conventional.
The next step is to consider how the function should affect ahand
in each clause:
In the first case, ahand
's next
field is
empty
. In that case, we can modify the next
field so that
it contains the new card:
(setnexthand! ahand (makehand 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
ahand
value.
In the second case, the natural recursion adds a new card to the end
of ahand
. Indeed, because the given ahand
isn't the
last one in the chain, the natural recursion does everything that needs to
be done.
Here is the complete definition of addatend!
:
;;addatend! : rank suit hand > void
;; effect: to add a card withv
as rank ands
as suit at the end ofahand
(define (addatend! rank suit ahand) (cond [(empty? (handnext ahand)) (sethandnext! ahand (makehand rank suit empty))] [else (addatend! rank suit (handnext ahand))]))
It closely resembles the listprocessing functions we designed in
part II. This should come as no surprise, because
addatend!
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 (createhand 13 SPADES)) (begin (addatend! 1 DIAMONDS hand0) (addatend! 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 booleanvalued expressions. Solution
Exercise 41.3.2.
Develop the function lastcard
. 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 addatend!
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:
(definestruct child (name social father mother))
and a data definition:
A familytreenode (short: ftn) is either
false
, or
(makechild 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 addftn!
. It consumes a family tree
aft
, a social security number ssc
, a symbol
anc
, and a child
structure. Its effect is to modify that
structure in aft
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 addftn!
mutates the mother
field. If the respective fields already contain a child
structure,
addftn!
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: setchildfather!
or
setchildmother!
. Modify addftn!
accordingly.
Solution
Exercise 41.3.4.
Develop an implementation of a hand with createhand
and
addatend!
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
addatend!
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 addatend!
:
;;removelast! : hand > void
;; effect : to remove the last card inahand
, unless it is the only one (define (removelast! ahand) ...)
The effect is restricted because a hand must always contain one card.
We can also adapt the example for addatend!
without difficulty:
(define hand0 (createhand 13 SPADES)) (begin (addatend! 1 DIAMONDS hand0) (addatend! 2 CLUBS hand0) (removelast! hand0) (removelast! hand0))
The resulting value is void
. The effect of the computation is to
return hand0
in its initial state.
The template for removelast!
is the same as that for
addatend!
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:
Recall that the first clause represents the case when ahand
's
next
field is empty
. In contrast to the situation with
addatend!
, it is not clear what we need to do now. According to the
effect statement, we must do one of two things:
If ahand
is the last item in a chain that consists of more
than one hand
structure, it must be removed.
If ahand
is the only structure that removelast!
consumed, the function should have no effect.
But we can't know whether ahand
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 accumulatorbased design recipe.
Once we have recognized the need for an accumulatorstyle function, we encapsulate the template in a localexpression and add an accumulator argument to its definition and applications:
(define (removelast! ahand0)
(local (;; accumulator
...
(define (rem! ahand accumulator)
(cond
[(empty? (handnext ahand))
... (handrank ahand) ... (handsuit ahand) ...]
[else ... (handrank ahand) ... (handsuit ahand) ...
... (rem! (handnext ahand) ... accumulator ...) ...])))
... (rem! ahand0 ...) ...))
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 removelast!
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 ahand
is not the only
hand
structure in ahand0
. Second, rem!
must be
enabled to remove ahand
from ahand0
. For the first
goal, rem!
's first application should be in a context where we
know that ahand0
contains more than one card. This argument
suggests a condexpression for the body of the localexpression:
(cond [(empty? (handnext ahand)) (void)] [else (rem! ahand0 ...)])
For the second goal, rem!
's accumulator argument should always
represent the hand
structure that precedes ahand
in
ahand0
. Then rem!
can remove ahand
by
modifying the predecessor's next
field:
(sethandnext! 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 predecessorof:ahand
to emphasize the relationship to the parameter proper. The first
application of rem!
in the body of the localexpression hands it the
second hand
structure in ahand0
. The second argument is
ahand0
, which establishes the desired relationship.

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:
;;sortedinsert! : rank suit hand > void
;; assume:ahand
is sorted by rank, in descending order ;; effect: to add a card withr
as rank ands
as suit at the proper place (define (sortedinsert! r s ahand) ...)
The function assumes that the given hand
is already sorted. The
assumption naturally holds if we always use createhand
to create
a hand and sortedinsert!
to insert cards.
Suppose we start with the same hand as above for addatend!
:
(define hand0 (createhand 13 SPADES))
If we evaluate (sortedinsert! 1 DIAMONDS hand0)
in this context,
hands0
becomes
(makehand 13 SPADES (makehand 1 DIAMONDS empty))
If we now evaluate (sortedinsert! 2 CLUBS hand0)
in addition,
we get
(makehand 13 SPADES (makehand 2 CLUBS (makehand 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 (sortedinsert! r s ahand) (cond [(empty? (handnext ahand)) ... (handrank ahand) ... (handsuit ahand) ...] [else ... (handrank ahand) ... (handsuit ahand) ... ... (sortedinsert! r s (handnext ahand)) ...]))
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 condexpression:
(cond [(>= (handrank ahand) r (handrank (handnext ahand))) ...] [else ...])
The first condition expresses in Scheme what we just discussed. In
particular, (handrank ahand)
picks the rank of the first card in
ahand
and (handrank (handnext ahand))
picks the rank
of the second one. The comparison determines whether the three ranks are
properly ordered.
Each case of this new condexpression deserves its own analysis:
If (>= (handrank ahand) r (handrank (handnext ahand)))
is true, then the new card must go between the two cards that are currently
linked. That is, the next
field of ahand
must be changed
to contain a new hand
structure. The new structure consists of
r
, s
, and the original value of ahand
's
next
field. This yields the following elaboration of the
condexpression:
(cond [(>= (handrank ahand) r (handrank (handnext ahand))) (sethandnext! ahand (makehand r s (handnext ahand)))] [else ...])
If (>= (handrank ahand) r (handrank (handnext ahand)))
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 sortedinsert!
.
Putting all the pieces together yields a partial function definition:
(define (sortedinsert! r s ahand) (cond [(empty? (handnext ahand)) ... (handrank ahand) ... (handsuit ahand) ...] [else (cond [(>= (handrank ahand) r (handrank (handnext ahand))) (sethandnext! ahand (makehand r s (handnext ahand)))] [else (sortedinsert! r s (handnext ahand))])]))
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
(handrank ahand)
and compute something based on the outcome of
this comparison:
(cond [(>= (handrank ahand) r) ...] [else ...])
Clearly, if the comparison expression evaluates to true
, the
function must mutate the next
field of ahand
and add a
new hand
structure:
(cond [(>= (handrank ahand) r) (sethandnext! ahand (makehand 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 ahand
, the new card should
be inserted between the predecessor of ahand
and ahand
.
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 ifIn that singular case,sortedinsert!
consumes a rankr
that is larger than all the values in therank
fields ofahand
.
ahand
shouldn't change at all. After all,
there is no way to create a descending chain of cards by mutating
ahand
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 (makehand 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.

We're stuck. It is impossible to define sortedinsert!
, 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 localexpression.
Figure 124 displays the complete function definition. It
follows the pattern of section 39. The function itself
corresponds to createhand
, though instead of producing a
structure the new createhand
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
thehand
, the hidden state variable. If so, the manager just
changes thehand
; if not, it uses insertaux!
, 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 thehand
that have a given
rank. The function should produce a list of suits.
Solution
Exercise 41.3.7.
Reformulate createhand
in figure 124 such that the
manager uses a single set!expression and sortedinsert
does not use
any structure mutation.
Solution
Exercise 41.3.8. Recall the definition of a binary tree from section 14.2:
A binarytree (short: BT) is either
false
or
(makenode 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
(definestruct node (ssn name left right))
A binary tree is a binarysearchtree
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 insertbst!
. 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 removebst!
, 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 accumulatorstyle 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.
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 translatecircle
and
translaterectangle
of exercises 6.6.2
and 6.6.8, respectively, into
structuremutating functions. Adapt movecircle
from
section 6.6 and moverectangle
from
exercise 6.6.12 so that they use these new
functions.
Solution
Exercise 41.4.2.
Adapt the function movepicture
from exercise 10.3.6 to
use the structuremutating functions from
exercise 41.4.1.
Solution
Exercise 41.4.3.
Use Scheme's foreach
function (see Help Desk) to abstract where
possible in the functions of
exercise 41.4.2.
Solution