Assignment 6

Due Date : 11/6 @ 11:59pm

Note

For each function that you design you are expected to follow the Design Recipe in the same way as we did in class. Failure to show all your work for each step will cost you points.

Problem 1

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 2

1. Design the function swap that consumes a list of symbols los and two symbols s1 and s2. The function returns a the list lst with all occurrences of s1 replaced with s2 and all occurrences of s2 replaced with s1, e.g., (swap 'a 'd (list a b c d)) returns (list d b c a)
2. Design the function product, that consumes sos1 and sos2 each a list of symbols without repetitions, returns a list of 2-lists that represents the Cartesian product of sos1 and sos2. The 2-lists may appear in any order.

    > (product (list a b c) (list x y))
   (list (list a x) (list a y) (list b x) (list b y) (list c x) (list c y))
                   

3. Design the function flatten that consumes a list of lists of numbers Lof[Lof[Number]] and returns a single list that contains all the numbers (put differently remove the inner lists).

    > (flatten (list (list 1 2) (list 4 5) (list 10 19)))
   (list 1 2 4 5 10 19) 
   

Problem 3

Given the following data definition

;; An ATOM is one of: 
;; -- Symbol
;; -- String 
;; -- Number


;; ---------------------------------------------------------
;; An SEXP (S-expression) is one of: 
;; -- empty 
;; -- (cons ATOM SEXP)
;; -- (cons SEXP SEXP)

Design the following functions

1. count-symbols consumes an SEXP and returns the total number of elements in SEXP that are Symbols.
2. sum-numbers consumes an SEXP and returns the summation of all elements in SEXP that are Numbers.
3. replace consumes an SEXP and two ATOMs a1 and a2 and replaces all occurrences of a1 in SEXP with a2. For example,

    > (replace (list (list 'a 'b) (list 1 3 )) 'a 'b) 
   (list (list 'b 'b) (list 1 3))
   
   > (replace (list (list 'a 'b) (list 1 3)) 1 2) 
   (list (list 'a 'b) (list 2 3))
   

   Our are not allowed to use the eq? build in function.