NOTE: This assignment is due the Tuesday night, after the exam.

This problem set continues the study of self-referential unions. Some of the problems cover functions that process two arguments from classes with complex (self-referential) data definitions. You must follow the design recipe. The graders will look for data definitions, contracts, purpose statements, examples/tests, and properly organized function definitions. For the latter, you must design templates. You do not need to include the templates with your homework, however. If you do, comment them out.

---

Problem A1:

Here is a data definition:

;; A family-tree-node is one of: 
;; - empty 
;; - (make-child father mother name date hair-color) 
;; where father and mother are family-tree-nodes, 
;; name and hair-color are symbols, and date is a number.

Use the above data definition to solve the following problems:

1. Develop the function count-older that consumes a family-tree-node and a year and returns the number of people in the tree that were born that year or earlier.
2. Develop the function search-tree-older that consumes a family-tree-node and a number and produces a list of all of the people in the tree born in that year or earlier.
3. Develop the function red-haired-ancestors? that determines whether a family-tree-node contains an ancestor with red hair on the father's side and an ancestor with red hair on the mother's side.
4. Develop the function update-father that consumes two family-tree-nodes and produces a family-tree-node that updates the father of the first tree to be the second tree.

Problem A2:

Cartesian coordinates:

1. Develop the function make-points, which combines a list of x-positions and a list of y-positions into a list of posns. Assume the lists are of equal length.
2. Develop the function make-1stQpoints, which consumes a list of x-positions and a list of y-positions and produces a list of posns that fall in the first quadrant. Assume the lists are of equal length.

Problem A3:

XML is a modern language (really, a family of languages) for encoding data. It uses "named parentheses" to group structured data, and strings for everything else. [Well, it contains a few more things than that, but this is good enough for now.] Here is an example:

     <div>
       <p><b>Problem A1</b>:</p>
  
       <blockquote>
         <p>

           XML is a modern language (really, a
           <i>family</i> of languages) for encoding
           data. It uses "<i>named parentheses</i>" to
           group structured data and strings for everything
           else. [Well, it contains a few more things than that, but
           this is good enough for now.] Here is an example:

         </p> 

         <p> Yes, this example is weird, because it is 
           self-referential but, hey, you should be used to
           this by now.  
         </p>
       </blockquote>
     </div>

Yes, this example is weird, because it is self-referential but, hey, you should be used to this by now.

You should have noticed that the example is not a complete representation of Problem A1. It misses this paragraph and it misses something in the middle. Nevertheless, it is a good example of the kind of XML you will encounter in the real world.

There are many ways to represent XML data in DrRacket. Here is one of them:

     ;; An Xexpr is one of: 
     ;;  - (cons Symbol LoXexpr)
     ;;  - String 

     ;; An LoXexpr is one of: 
     ;;  - empty 
     ;;  - (cons Xexpr LoXexpr)
  

Interpretation: An Xexpr represents a bracketed pair of "named parentheses" and whatever is in between, e.g.,

     <p>
        hello <em>world </em>
     </p>
  

becomes:

     (cons 'p
           (cons "hello "
                 (cons (cons 'em (cons "world " empty))
                       empty)))
  

Or equivalently...

   (list 'p "hello " (list 'em "world "))
  

See DrRacket documentation or the HtDP introduction to the list operator.

(Yes, S-expressions are more compact than XML and 50 years older than XML, but people don't like parentheses. They're so ugly and unreadable...)

In this context solve the following problems:

1. Translate the XML example from above into an Xexpr.
2. Design a function that counts the number of symbols in an Xexpr.
3. Design a function that counts the number of characters in an Xexpr.