Workshop 4A

Workshop 4A#

Practice#

If you have not done so yet, fork the template workshop repository and clone it to your computer.

Create a folder called ws4a in your workshop repository, and in there, work in a file called DescendantsTree.java. Commit and push your work when you are done.

Design a program able to model a particular person’s tree of descendants. A person’s descendants include the children of that person (immediate descendants), the children of the children of that person (grandchildren) and so on. The program should keep track of the full name (i.e., names + surnames), gender, birth and death date (if and only if the person died) of every person in the tree of descendants (including the root of the tree).

You can assume:

1. all dates are in the same time zone, and time of day does not matter
2. the birth date of the children of any parent in the tree has to be a biologically compatible future date compared to the birth date of the parent;
3. the difference among birth dates of any two siblings is biologically compatible;
4. the death date can never be an earlier date than the birth date;
5. there cannot be two descendants with the same full name.

Design the following functions:

// [G] stands for however you want to represent gender
// [T] stands for however you represent trees of descendants
// [P] stands for however you represent predicates over people

/** 
 * Given the full name of a person (possible different from the
 * person in the root of the tree), count how many descendants of 
 * that person are there in a person's tree of descendants. 
 * Hint: first design a function that counts how many descendants
 * are there in a person's tree of descendants. 
 */
int numberOfDescendants([T] tree, String name)

/** 
 * Given a person's tree of descendants, generate a list with
 * the full names of all descendants which
 * (1) have a given gender
 * (2) are still alive;
 * (3) were born after a given date;
 * (4) have had 2 or more children born the on the same date
 * Note 1: you can develop a single higher-order function to 
 * code (1)-(4). Note 2: the order of elements in the output
 * list is not important; the output of the function is 
 * correct as long as  all the requested full names are in
 * the output list.
 */
ConsList<String> ofGender([T] tree, [G] gender)
ConsList<String> stillAlive([T] tree)
ConsList<String> bornAfter([T] tree, Date date)
ConsList<String> hadNtuplets([T] tree)

/**
 * Given a person's tree of descendants, return the name of the 
 * person that had their first children earliest in their life
 * among all parents in the tree. If more than one person fulfills
 * this criterion, return one of such people arbitrarily.
 */
String youngestAtFirstChild([T] tree)
/** 
 * Given a person's tree of descendants, returns a new tree where
 * all people with a given gender and their descendants are removed
 * from the input tree. Generalize the function such that this 
 * operation (removal of some people and all their descendants) can
 * be applied using any predicate passed as an argument to the 
 * function.
 */
[T] removeAllOfGender([T] tree, [G] gender)
[T] removeAllOf([T] tree, [P] predicate)

Follow the Design Recipe!