Past exam of the year 1 of the computer science course of the University of Oxford / 2003 / Functional programming, data structures and algorithms, procedural programming, and digital hardware / 3 / b

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