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