Lab 8 — Ancestor Trees

Skills: 6

The goal of this lab will be to practice on trees.

Given Data Definition

data AncTree:
  | noInfo
  | person(
      name :: String,
      birthyear :: Number,
      eye :: String,
      mother :: AncTree,
      father :: AncTree
    )
end

Examples

alice-tree = person("Alice", 1922, "brown", noInfo, noInfo)
bob-tree = person("Bob", 1922, "brown", noInfo, robert-tree)
charlie-tree = person("Charlie", 1945, "brown", alice-tree, bob-tree)
dave-tree = person("Dave", 1946, "green", noInfo, noInfo)
emily-tree = person("Emily", 1971, "blue", charlie-tree, dave-tree)

Problem 1

Design a function count-eye-color that counts how many people in a tree have a given eye color.

Problem 2

Design a function max-generations that finds the maximum number of generations in the tree (counting from the root person).

Problem 3

Design a function oldest-person that finds the name of the oldest person in the tree (the person with the smallest birth year). If the tree is empty, raise the error "Empty tree".

Problem 4

Design a function names-starting-with that returns a list of all names in the tree that start with a given letter (case-insensitive).

Problem 5

In some families -- maybe including yours -- people want to be able to understand how they're related to others in their family. Family trees can be useful for that purpose. They represent familial relationships in certain ways. For example, a node might represent an ancestor, and a child represents ... well, a child or a descendant.

Often, but not always, family trees show both (a) legally-recognized relationships and (b) relationships in which the children are directly genetically related to their parents. That means that people who don’t meet both conditions (a) and (b) might not be included in a family tree.

Deciding whom to put in a family tree has emotional and psychological consequences; it also reflects political and legal stakes. For example: determining citizenship (who can apply for residency or citizenship based on family relationships?), finances (whose debts are you responsible for paying?), medical decision-making authority (what decisions can someone make on someone else's behalf?), and inheritance (who will automatically inherit if there is no will?) all depend on definitions of who counts as "family" or "relatives". And in many places, ideas about what a family is, and about which familial relations should be openly acknowledged and documented, are changing.

Part A

If you had to design a data definition for a family tree, then what kinds of relations do you think it should represent? In other words, what counts as "being part of the same family"? Please include a justification of your answer in two or three sentences.

Part B

Given your answer to the previous question, what would you name the nodes and the children in your tree? Explain your answer in two or three sentences.