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 , we even encountered self-referential data definitions involving structures in structures. On occasion, processing such classes of data may also require mutations of structure fields that contain structures. In this section, we work through one such example.

Figure: Playing with cards

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

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

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

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

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

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

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

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

Let's start with examples:

(define hand0 (create-hand 13 SPADES))

(add-at-end! 1 DIAMONDS hand0)

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

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

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

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

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

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

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

   The newly created hand structure is now the one that contains empty in its next field, that is, it is the new end of the a-hand value.
2. In the second case, the natural recursion adds a new card to the end of a-hand. Indeed, because the given a-hand isn't the last one in the chain, the natural recursion does everything that needs to be done.

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

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

Evaluate the following program by hand:

(define hand0 (create-hand 13 SPADES))

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

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))

A family-tree-node (short: ftn) is either false, or (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 , 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) ...) 

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

(define hand0 (create-hand 13 SPADES))

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

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

1. Recall that the first clause represents the case when a-hand's next field is empty. In contrast to the situation with add-at-end!, it is not clear what we need to do now. According to the effect statement, we must do one of two things:
   1. If a-hand is the last item in a chain that consists of more than one hand structure, it must be removed.
   2. If a-hand is the only structure that remove-last! consumed, the function should have no effect.
   But we can't know whether a-hand is the last item in a long chain of hands or the only one. We have lost knowledge that was available at the beginning of the evaluation!

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) ...    ...) ...]))) 
    ... (rem! a-hand0 ...) ...)) 

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 ...)]) 

 
(set-hand-next! accumulator empty) 

Now the pieces of the design puzzle fall into place. The complete definition of the function is in figure . 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: 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) ...) 

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

(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 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 ...]) 

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

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

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

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

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: 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  displays the complete function definition. It follows the pattern of section . 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  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  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  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 :

A binary-tree (short: BT) is either false or (make-node soc pn lft rgt) where soc is a number, pn is a symbol, and lft and rgt are BTs.

The required structure definition is

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

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