A string data type suffices for a name, an algebraic data type for the recorded sex, and a triple of integers for a date. Use a constructor for Person so that selectors are unambiguous in Haskell:
type Name = String
data Sex = Female | Male deriving (Eq, Show)
data Date = Date { day :: Int, month :: Int, year :: Int }
  deriving (Eq, Show)
data Person = Person { name :: Name, sex :: Sex, born :: Date }
  deriving (Eq, Show)
type BirthCertificate = (Person, Person, Person)
type Database = [BirthCertificate]
Dates have the precondition that their fields form a valid calendar date. This simple database representation assumes the triple of identifying fields distinguishes the recorded individuals; a production database would normally add a stable identifier to distinguish namesakes. The two constructors for Sex model the two recorded values used by this exercise. In mathematical notation,
(1)
Extract the two recorded parents from every matching certificate, and use duplicate removal so that repeated certificates do not repeat an individual. This helper is shared by the remaining Haskell definitions:
unique :: Eq a => [a] -> [a]
unique [] = []
unique (x:xs) = x : unique [y | y <- xs, y /= x]

parents :: Database -> Person -> [Person]
parents db p = unique [q | (baby,mother,father) <- db,
                          baby == p, q <- [mother,father]]
A person need not have a certificate of their own to appear in the output: a parental field is already evidence of the relationship. The resulting list preserves first occurrence order, with mother before father in each certificate. Its set of entries is
(1)
A matching mother or father field identifies a child. In Haskell:
children :: Database -> Person -> [Person]
children db p = unique [baby | (baby,mother,father) <- db,
                              mother == p || father == p]
Duplicate removal handles repeated certificates and children recorded in more than one matching row. Thus
(1)
The displayed set describes membership; the implementation returns its entries as a list in first certificate order.
Treat brothers as male individuals sharing at least one recorded parent, including half-brothers. Derive a sibling helper and then select the recorded sex:
siblings :: Database -> Person -> [Person]
siblings db p = unique [q | parent <- parents db p,
                           q <- children db parent, q /= p]

brothers :: Database -> Person -> [Person]
brothers db p = [q | q <- siblings db p, sex q == Male]
The exclusion q /= p prevents a male individual from being his own brother. Duplicate removal is needed because a full brother can be found through both parents. The membership condition is
(1)
If the intended convention is full brothers only, replace the shared-parent condition by a common mother and a common father in the recorded certificates. The definition above states the convention explicitly rather than silently discarding half-brothers.
Use first cousins: the children of the siblings of a recorded parent. This includes cousins through a parent's half-sibling under the convention above. In Haskell:
cousins :: Database -> Person -> [Person]
cousins db p = unique [q | parent <- parents db p,
                          auntOrUncle <- siblings db parent,
                          q <- children db auntOrUncle, q /= p]
Selecting siblings of parents avoids the mistake of returning all people with a common grandparent, which would also return ordinary siblings. The explicit exclusion of p is harmless on an ordinary consistent pedigree and prevents a self-result in unusual records. Multiple relationship paths give just one output entry after duplicate removal. Thus
(1)
An individual can have any number of children, so use a rose tree, with one list of child trees at each root:
data DescendantTree = Desc Person [DescendantTree]
  deriving Show

descendants :: Database -> Person -> DescendantTree
descendants db p = Desc p (map (descendants db) (children db p))
The root records p, its immediate child trees record children db p, and recursion repeats the same construction at each generation. An individual with no recorded children produces Desc p []. For a finite database whose parent-child directed graph is acyclic, every recursive descent advances along a path that cannot revisit a vertex, so the construction terminates. On inconsistent cyclic records it can unfold indefinitely; finiteness of the database alone is insufficient for termination.
Two branches may contain the same descendant, as happens when relatives have a child. This is appropriate for the requested tree unfolding; it preserves both lines of descent rather than silently choosing one. The concise constructor equation is
(1)

Ancestors (10)

  1. Functional programming, data structures and algorithms, procedural programming, and digital hardware
  2. 2003
  3. Past exam of the year 1 of the computer science course of the University of Oxford
  4. Year 1 of the computer science course of the University of Oxford
  5. Computer science course of the University of Oxford
  6. Undergraduate course of the University of Oxford
  7. Course of the University of Oxford
  8. University of Oxford
  9. List of universities
  10. Home

View article source

Discussion (0) New discussion

There are no discussions about this article yet.

Articles by others on the same topic (0)

There are currently no matching articles.
See all articles in the same topic Create my own version