Counting ALL family members in an ancestry tree above a child - Racket (*SL)

Question

Here's the data definition of a family tree (FT) from How To Design Programs

(define-struct no-parent [])
(define-struct child [father mother name date eyes])
(define NP (make-no-parent))
; An FT is one of: 
; – NP
; – (make-child FT FT String N String)

; Oldest Generation:
(define Carl (make-child NP NP "Carl" 1926 "green"))
(define Bettina (make-child NP NP "Bettina" 1926 "green"))

; Middle Generation:
(define Adam (make-child Carl Bettina "Adam" 1950 "hazel"))
(define Dave (make-child Carl Bettina "Dave" 1955 "black"))
(define Eva (make-child Carl Bettina "Eva" 1965 "blue"))
(define Fred (make-child NP NP "Fred" 1966 "pink"))

; Youngest Generation: 
(define Gustav (make-child Fred Eva "Gustav" 1988 "brown"))

I designed a function to count all the persons in a particular family tree.

The function consumes a family tree and counts the child structures in the tree by simply recurring on each parent and adding 1 to combine the function call on both the parents and returning 0 if there for no-parent

;; FT -> Natural
;; counts the child structures in an-ftree
(define (count-persons an-ftree)
  (cond
    [(no-parent? an-ftree) 0]
    [else (+ 1 (count-persons (child-father an-ftree))
             (count-persons (child-mother an-ftree)))]))

My function - when launched on Gustav - counted Fred and Eva, then Eva's parents Carl and Betrtina. It didn't reach Adam and Dave.

(check-expect (count-persons Dave) 3) ✓
(check-expect (count-persons Gustav) 7) ✗ (it's 5)

How can I (if I want to count ALL ancestors, including uncles) reach Adam and Dave when I call my function on Gustav?

tl;dr

Essentially how can traverse through all generations above? How can I get access to 'Dave' from 'Gustav' (there is no reference to them!). How to count ALL ancestors, not just parents, then their parents, and so on.

Answer 1

If you want to follow relationships in both directions, then a Tree can't completely represent the data, but a Graph can. How to Design Programs covers graphs in Traversing Graphs and A Problem with Generative Recursion.

The main difference between a normal tree representation like yours and the graph representations introduced in How to Design Programs is that a Tree node contains its sub-trees, but a Graph node only points to its relatives using unique names.

In this data definition for example, the person-info structures don't contain other person-info structures. They only contain names, where you have to look up a name in the main graph to find which person-info structure it corresponds to.

(define-struct family-graph [entries])
(define-struct person-info [name father mother children])
;; An FG (family graph) is a:
;;   (make-family-graph [Listof PersonInfo])
;; A PersonInfo is a:
;;   (make-person-info String [Maybe String] [Maybe String] [Listof String])
;; invariants:
;;  parent-has-child:
;;   If a person A has a father or mother's name B, the entry
;;   for B exists and lists A's name as a child.
;;  child-has-parent:
;;   And vice-versa, if a person A has a child's name B, the
;;   entry for B exists and lists A's name as either father
;;   or mother.

Because the structure of the graph is determined by these names, you have to be careful that if a name appears in the father, mother, or children fields, it has an entry that corresponds to it. Otherwise you wouldn't be able to look it up in the graph.

;; FG String -> PersonInfo
;; Finds the person-info structure that corresponds to the
;; given name in the fg.
(define (lookup-person-info fg name) ....)

In this family-tree graph, if an entry for a parent refers to a child, then that child should refer to the parent as well, and vice-versa. This is the reason for the parent-has-child and child-has-parent invariants. If you have any operations that extend this graph, they should preserve these invariants.

;; FG String -> FG
;; Preserves the parent-has-child and child-has-parent invariants
;; by not adding any parent-child relationships.
(define (add-unrelated-person fg name) ....)

;; FG String [Maybe String] [Maybe String] -> FG
;; Preserves parent-has-child by adding the child with the
;; given parent names. Preserves child-has-parent by
;; updating the entries for both parents, if the exist, and
;; adding new entries for parents that previously didn't
;; exist.
(define (add-child fg name father mother) ....)

The family-tree graph from your question can be constructed by calling these functions repeatedly. You could do this with a bunch of nested function calls, but it's easier to read in a let* like this:

(define Carl "Carl")
(define Bettina "Bettina")
(define Adam "Adam")
(define Dave "Dave")
(define Eva "Eva")
(define Fred "Fred")
(define Gustav "Gustav")
(define FG
  (let*
      ([fg EMPTY-FG]

       ; Oldest Generation:
       [fg (add-unrelated-person fg Carl)]
       [fg (add-unrelated-person fg Bettina)]

       ; Middle Generation:
       [fg (add-child fg Adam Carl Bettina)]
       [fg (add-child fg Dave Carl Bettina)]
       [fg (add-child fg Eva Carl Bettina)]
       [fg (add-unrelated-person fg Fred)]

       ; Youngest Generation:
       [fg (add-child fg Gustav Fred Eva)])
    fg))
;(make-family-graph 
; (list 
;   (make-person-info "Gustav" "Fred" "Eva" '())
;   (make-person-info "Fred" #false #false (list "Gustav"))
;   (make-person-info "Eva" "Carl" "Bettina" (list "Gustav"))
;   (make-person-info "Dave" "Carl" "Bettina" '())
;   (make-person-info "Adam" "Carl" "Bettina" '())
;   (make-person-info "Bettina" #false #false (list "Eva" "Dave" "Adam"))
;   (make-person-info "Carl" #false #false (list "Eva" "Dave" "Adam"))))