Lists of Structures, Lists in Structures

Next: Designing Functions for Mutually Up: Mutually Referential Data Definitions Previous: Mutually Referential Data Definitions

Lists of Structures, Lists in Structures

When we build a family tree retroactively, we often start from the child's perspective and proceed from there to parents, grandparents, etc. As we construct the tree, we write down who is whose child rather than who is whose parents. We build a descendant family tree.

Drawing a descendant tree proceeds just like drawing an ancestor tree, except that all arrows are reversed. Figure represents the same family as that of figure , but drawn from the descendant perspective.

Figure: A descendant family tree

Representing these new kinds of family trees and their nodes in a computer requires a different class of data than do the ancestor family trees. This time a node must include information about the children instead of the two parents. Here is a structure definition:

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

The last three fields in a parent structure contain the same basic information as a corresponding child structure, but the contents of the first one poses an interesting question. Since a parent may have an arbitrary number of children, the children field must contain an undetermined number of nodes, each of which represents one child.

The natural choice is to insist that the children field always stands for a list of parent structures. The list represents the children; if a person doesn't have children, the list is empty. This decision suggests the following data definition:

A parent is a structure: (make-parent loc n d e)
where loc is a list of children, n and e are symbols, and d is a number.

Unfortunately, this data definition violates our criteria concerning definitions. In particular, it mentions the name of a collection that is not yet defined: list of children.

Since it is impossible to define the class of parents without knowing what a list of children is, let's start from the latter:

A list of children is either

empty or
(cons p loc) where p is a parent and loc is a list of children.

This second definition looks standard, but it suffers from the same problem as the one for parents. The unknown class it refers to is that of the class of parents, which cannot be defined without a definition for the list of children, and so on.

The conclusion is that the two data definitions refer to each other and are only meaningful if introduced together:

A parent is a structure:

(make-parent loc n d e) where loc is a list of children, n and e are symbols, and d is a number.
A list-of-children is either

empty or
(cons p loc) where p is a parent and loc is a list of children.

When two (or more) data definitions refer to each other, they are said to be MUTUALLY RECURSIVE or MUTUALLY REFERENTIAL.

Now we can translate the family tree of figure into our Scheme data language. Before we can create a parent structure, of course, we must first define all of the nodes that represent children. And, just as in section , the best way to do this is to name a parent structure before we reuse it in a list of children. Here is an example:

(define Gustav (make-parent empty 'Gustav 1988 'brown))

(make-parent (list Gustav) 'Fred 1950 'yellow)

To create a parent structure for Fred, we first define one for Gustav so that we can form (list Gustav), the list of children for Fred.

Figure contains the complete Scheme representation for our descendant tree. To avoid repetitions, it also includes definitions for lists of children. Compare the definitions with figure (see page ), which represents the same family as an ancestor tree.

;; Youngest Generation:
(define Gustav (make-parent empty 'Gustav 1988 'brown))

(define Fred&Eva (list Gustav))

;; Middle Generation: 
(define Adam (make-parent empty 'Adam 1950 'yellow)) 
(define Dave (make-parent empty 'Dave 1955 'black)) 
(define Eva (make-parent Fred&Eva 'Eva 1965 'blue)) 
(define Fred (make-parent Fred&Eva 'Fred 1966 'pink))

(define Carl&Bettina (list Adam Dave Eva))

;; Oldest Generation: 
(define Carl (make-parent Carl&Bettina 'Carl 1926 'green)) 
(define Bettina (make-parent Carl&Bettina 'Bettina 1926 'green))

Figure: A Scheme representation of the descendant family tree

Let us now study the development of blue-eyed-descendant?, the natural companion of blue-eyed-ancestor?. It consumes a parent structure and determines whether it or any of its descendants has blue eyes:

;; blue-eyed-descendant? : ftn -> boolean
;; to determine whether a-parent or any of its descendants (children,  
;; grandchildren, and so on) have 'blue in the eyes field 
(define (blue-eyed-descendant? a-parent) ...)

Here are three simple examples, formulated as tests:

(boolean=? (blue-eyed-descendant? Gustav) false)
(boolean=? (blue-eyed-descendant? Eva) true) 
(boolean=? (blue-eyed-descendant? Bettina) true)

A glance at figure

explains the answers in each case.

According to our rules, the template for blue-eyed-descendant? is simple. Since its input is a plain class of structures, the template contains nothing but selector expressions for the fields in the structure:

(define (blue-eyed-descendant? a-parent)
  ... (parent-children a-parent) ... 
  ... (parent-name a-parent) ... 
  ... (parent-date a-parent) ... 
  ... (parent-eyes a-parent) ... )

The structure definition for parent specifies four fields so there are four expressions.

The expressions in the template remind us that the eye color of the parent is available and can be checked. Hence we add a cond-expression that compares (parent-eyes a-parent) to 'blue:

(define (blue-eyed-descendant? a-parent)
  (cond 
    [(symbol=? (parent-eyes a-parent) 'blue) true] 
    [else 
      ... (parent-children a-parent) ... 
      ... (parent-name a-parent) ... 
      ... (parent-date a-parent) ...]))

The answer is true if the condition holds. The else clause contains the remaining expressions. The name and date field have nothing to do with the eye color of a person, so we can ignore them. This leaves us with

(parent-children a-parent)

an expression that extracts the list of children from the parent structure.

If the eye color of some parent structure is not 'blue, we must clearly search the list of children for a blue-eyed descendant. Following our guidelines for complex functions, we add the function to our wish list and continue from there. The function that we want to put on a wish list consumes a list of children and checks whether any of these or their grandchildren has blue eyes. Here are the contract, header, and purpose statement:

;; blue-eyed-children? : list-of-children -> boolean
;; to determine whether any of the structures on aloc is blue-eyed 
;; or has any blue-eyed descendant 
(define (blue-eyed-children? aloc) ...)

Using blue-eyed-children? we can complete the definition of blue-eyed-descendant?:

(define (blue-eyed-descendant? a-parent)
  (cond 
    [(symbol=? (parent-eyes a-parent) 'blue) true] 
    [else (blue-eyed-children? (parent-children a-parent))]))

That is, if a-parent doesn't have blue eyes, we just look through the list of its children.

Before we can test blue-eyed-descendant?, we must define the function on our wish list. To make up examples and tests for blue-eyed-children?, we use the list-of-children definitions in figure :

(not (blue-eyed-children? (list Gustav)))

(blue-eyed-children? (list Adam Dave Eva))

Gustav doesn't have blue eyes and doesn't have any recorded descendants. Hence, blue-eyed-children? produces false for (list Gustav). In contrast, Eva has blue eyes, and therefore blue-eyed-children? produces true for the second list of children.

Since the input for blue-eyed-children? is a list, the template is the standard pattern:

(define (blue-eyed-children? aloc)
  (cond 
    [(empty? aloc) ...] 
    [else 
      ... (first aloc) ... 
      ... (blue-eyed-children? (rest aloc)) ...]))

Next we consider the two cases. If blue-eyed-children?'s input is empty, the answer is false. Otherwise we have two expressions:

(first aloc), which extracts the first item, a parent structure, from the list; and
(blue-eyed-children? (rest aloc)), which determines whether any of the structures on aloc is blue-eyed or has any blue-eyed descendant.

Fortunately we already have a function that determines whether a parent structure or any of its descendants has blue eyes: blue-eyed-descendant?. This suggests that we check whether

(blue-eyed-descendant? (first aloc))

holds and, if so, blue-eyed-children? can produce true. If not, the second expression determines whether we have more luck with the rest of the list.

Figure contains the complete definitions for both functions: blue-eyed-descendant? and blue-eyed-children?. Unlike any other group of functions, these two functions refer to each other. They are MUTUALLY RECURSIVE. Not surprisingly, the mutual references in the definitions match the mutual references in data definitions. The figure also contains a pair of alternative definitions that use or instead of nested cond-expressions.

;; blue-eyed-descendant? : ftn -> boolean
;; to determine whether a-parent any of the descendants (children,  
;; grandchildren, and so on) have 'blue in the eyes field 
(define (blue-eyed-descendant? a-parent) 
  (cond 
    [(symbol=? (parent-eyes a-parent) 'blue) true] 
    [else (blue-eyed-children? (parent-children a-parent))]))

;; blue-eyed-children? : list-of-children -> boolean 
;; to determine whether any of the structures in aloc is blue-eyed 
;; or has any blue-eyed descendant 
(define (blue-eyed-children? aloc) 
  (cond 
    [(empty? aloc) false] 
    [else 
      (cond 
        [(blue-eyed-descendant? (first aloc)) true] 
        [else (blue-eyed-children? (rest aloc))])]))

;; blue-eyed-descendant? : ftn -> boolean
;; to determine whether a-parent any of the descendants (children,  
;; grandchildren, and so on) have 'blue in the eyes field 
(define (blue-eyed-descendant? a-parent) 
  (or (symbol=? (parent-eyes a-parent) 'blue) 
      (blue-eyed-children? (parent-children a-parent))))

;; blue-eyed-children? : list-of-children -> boolean 
;; to determine whether any of the structures in aloc is blue-eyed 
;; or has any blue-eyed descendant 
(define (blue-eyed-children? aloc) 
  (cond 
    [(empty? aloc) false] 
    [else (or (blue-eyed-descendant? (first aloc)) 
              (blue-eyed-children? (rest aloc)))]))

Figure: Two programs for finding a blue-eyed descendant

Exercises Exercise 15.1.1

Evaluate (blue-eyed-descendant? Eva) by hand. Then evaluate (blue-eyed-descendant? Bettina). Solution

Exercise 15.1.2

Develop the function how-far-removed. It determines how far a blue-eyed descendant, if one exists, is removed from the given parent. If the given parent has blue eyes, the distance is 0; if eyes is not blue but some of the structure's children's eyes are, the distance is 1; and so on. If no descendant of the given parent has blue eyes, the function returns false when it is applied to the corresponding family tree. Solution

Exercise 15.1.3

Develop the function count-descendants, which consumes a parent and produces the number of descendants, including the parent.

Develop the function count-proper-descendants, which consumes a parent and produces the number of proper descendants, that is, all nodes in the family tree, not counting the parent. Solution

Exercise 15.1.4

Develop the function eye-colors, which consumes a parent and produces a list of all eye colors in the tree. An eye color may occur more than once in the list.

Hint: Use the Scheme operation append, which consumes two lists and produces the concatenation of the two lists. Solution

Next: Designing Functions for Mutually Up: Mutually Referential Data Definitions Previous: Mutually Referential Data Definitions

PLT