In the preceding section, we developed data representations of family trees, Web pages, and Scheme expressions. Developing functions for these data definitions was based on one and the same design recipe. If we wish to develop more realistic representations of Web pages or Scheme expressions, or if we wish to study descendant family trees rather than ancestor trees, we must learn to describe classes of data that are interrelated. That is, we must formulate several data definitions at once where the data definitions not only refer to themselves, but also refer to other data definitions.
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 40 represents the same family as that of figure 35, but drawn from the descendant perspective.

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:
(definestruct 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:
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.A parent is a structure:where
(makeparent loc n d e)
loc
is a list of children,n
ande
are symbols, andd
is a number.
Since it is impossible to define the class of parents without knowing what a list of children is, let's start from the latter:
This second definition looks standard, but it suffers from the same problem as the one forA list of children is either
empty
or
(cons p loc)
wherep
is a parent andloc
is a list of children.
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:
(makeparent loc n d e)
loc
is a list of children, n
and e
are symbols, and d
is a number.
A listofchildren 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 40 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 14.1, 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 (makeparent empty 'Gustav 1988 'brown)) (makeparent (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 41 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 36 (see page 19), which represents the same family as an ancestor tree.
Let us now study the development of blueeyeddescendant?
, the
natural companion of blueeyedancestor?
. It consumes a
parent
structure and determines whether it or any of its
descendants has blue eyes:
;;blueeyeddescendant? : parent > boolean
;; to determine whetheraparent
or any of its descendants (children, ;; grandchildren, and so on) have'blue
in theeyes
field (define (blueeyeddescendant? aparent) ...)
Here are three simple examples, formulated as tests:
(boolean=? (blueeyeddescendant? Gustav) false) (boolean=? (blueeyeddescendant? Eva) true) (boolean=? (blueeyeddescendant? Bettina) true)
A glance at figure 40 explains the answers in each case.
According to our rules, the template for blueeyeddescendant?
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 (blueeyeddescendant? aparent) ... (parentchildren aparent) ... ... (parentname aparent) ... ... (parentdate aparent) ... ... (parenteyes aparent) ... )
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 condexpression
that compares (parenteyes aparent)
to 'blue
:
(define (blueeyeddescendant? aparent) (cond [(symbol=? (parenteyes aparent) 'blue) true] [else ... (parentchildren aparent) ... ... (parentname aparent) ... ... (parentdate aparent) ...]))
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
(parentchildren aparent)
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 blueeyed 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:
;;blueeyedchildren? : listofchildren > boolean
;; to determine whether any of the structures onaloc
is blueeyed ;; or has any blueeyed descendant (define (blueeyedchildren? aloc) ...)
Using blueeyedchildren?
we can complete the definition of
blueeyeddescendant?
:
(define (blueeyeddescendant? aparent) (cond [(symbol=? (parenteyes aparent) 'blue) true] [else (blueeyedchildren? (parentchildren aparent))]))
That is, if aparent
doesn't have blue eyes, we just look through
the list of its children.
Before we can test blueeyeddescendant?
, we must define the
function on our wish list. To make up examples and tests for
blueeyedchildren?
, we use the listofchildren definitions in
figure 41:
(not (blueeyedchildren? (list Gustav)))
(blueeyedchildren? (list Adam Dave Eva))
Gustav doesn't have blue eyes and doesn't have any recorded descendants.
Hence, blueeyedchildren?
produces false
for (list
Gustav)
. In contrast, Eva
has blue eyes, and therefore
blueeyedchildren?
produces true
for the second list of
children.
Since the input for blueeyedchildren?
is a list, the template is
the standard pattern:
(define (blueeyedchildren? aloc) (cond [(empty? aloc) ...] [else ... (first aloc) ... ... (blueeyedchildren? (rest aloc)) ...]))
Next we consider the two cases. If blueeyedchildren?
'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
(blueeyedchildren? (rest aloc))
, which determines whether
any of the structures on aloc
is blueeyed or has any blueeyed
descendant.
Fortunately we already have a function that determines whether a
parent
structure or any of its descendants has blue eyes:
blueeyeddescendant?
. This suggests that we check whether
(blueeyeddescendant? (first aloc))
holds and, if so, blueeyedchildren?
can produce true
. If
not, the second expression determines whether we have more luck with the
rest of the list.
Figure 42 contains the complete definitions for both
functions: blueeyeddescendant?
and blueeyedchildren?
.
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
condexpressions.

Exercise 15.1.1.
Evaluate (blueeyeddescendant? Eva)
by hand. Then evaluate
(blueeyeddescendant? Bettina)
.
Solution
Exercise 15.1.2.
Develop the function howfarremoved
. It determines how far a
blueeyed 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 at least one its 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 countdescendants
, which consumes a parent
and produces the number of descendants, including the parent.
Develop the function countproperdescendants
, 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 eyecolors
, 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
The recipe for designing functions on mutually referential data definitions generalizes that for selfreferential data. Indeed, it offers only two pieces of additional advice. First, we must create several templates simultaneously, one for each data definition. Second, we must annotate templates with selfreferences and CROSSREFERENCES, that is, references among different templates. Here is a more detailed explanation of the differences:
In the above example, we needed two interrelated definitions:


The first one concerns parents and another one for list of children. The
first (unconditionally) defines a parent in terms of symbols, numbers, and
a list of children, that is, it contains a crossreference to the second
definition. This second definition is a conditional definition. Its first
clause is simple; its second clause references both the definition for
parent
s and listofchildren
.
Here are the templates for our running example:
The funparent
template is unconditional because the data
definition for parent
s does not contain any clauses. It contains
a crossreference to the second template: to process the
children
field of a parent
structure. By the same rules,
funchildren
is conditional. The second cond
clause
contains one selfreference, for the rest
of the list, and one
crossreference for the first
item of the list, which is a
parent
structure.
A comparison of the data definitions and the templates shows how analogous the two are. To emphasize the similarity in selfreferences and crossreferences, the data definitions and templates have been annotated with arrows. It is easy to see how corresponding arrows have the same origin and destination in the two pictures.
cond
clause that does not contain
selfreferences to the template and crossreferences to other templates.
The results are typically easy to formulate for such templates or
cond
clauses.The rest of this step proceeds as before. When we deal with other clauses or functions, we remind ourselves what each expression in the template computes, assuming that all functions already work as specified in the contracts. Then we decide how to combine these pieces of data into a final answer. As we do that, we must not forget the guidelines concerning the composition of complex functions (sections 7.3 and 12).
Figure 43 summarizes the extended design recipe.

With mutually referential data definitions we can represent Web pages in a more accurate manner than in section 14.3. Here is the basic structure definition:
(definestruct wp (header body))
The two fields contain the two essential pieces of data in a Web page: a
header
and a body
. The data definition specifies that a
body is a list of words and Web pages:
A Webpage (short: WP) is a structure:
(makewp h p)
h
is a symbol and p
is a (Web) document.
A (Web) document is either
empty
,
(cons s p)
where s
is a symbol and p
is a document, or
(cons w p)
where w
is a Web page and p
is a document.
Exercise 15.3.1.
Develop the function size
, which consumes a Web page and produces
the number of symbols (words) it contains.
Solution
Develop the function wptofile
. The function consumes a Web page
and produces a list of symbols. The list contains all the words in a body
and all the headers of embedded Web pages. The bodies of immediately
embedded Web pages are ignored.
Solution
Exercise 15.3.3.
Develop the function occurs
. It consumes a symbol and a Web page
and determines whether the former occurs anywhere in the latter, including
the embedded Web pages.
Solution
Exercise 15.3.4.
Develop the program find
. The function consumes a Web page and a
symbol. It produces false
, if the symbol does not occur in the body
of the page or its embedded Web pages. If the symbol occurs at least once,
it produces a list of the headers that are encountered on the way to the
symbol.
Hint: Define an auxiliary like find
that produces only
true
when a Web page contains the desired word. Use it to define
find
. Alternatively, use boolean?
to determine whether a
natural recursion of find
produced a list or a boolean. Then
compute the result again. We will discuss this second technique, called
backtracking, in the intermezzo at the end of this
part.
Solution