schemeracketracket-student-languages

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


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)

enter image description here

; 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)

enter image description here

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

enter image description here

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.


Solution

  • 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"))))