计算 child 以上的祖先树中的所有家庭成员 - 球拍 (*SL)
Counting ALL family members in an ancestry tree above a child - Racket (*SL)
的家谱 (FT) 的数据定义
(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"))
我设计了一个函数来计算特定家谱中的所有人。
该函数使用家谱并计算树中的 child 结构，方法是简单地在每个 parent 上重复并加 1 以组合对两个 parent 的函数调用如果有 no-parent
，则返回 0
;; 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)))]))
我的功能 - 当在 Gustav 上启动时 - 计算 Fred 和 Eva，然后是 Eva 的 parent Carl 和 Betrtina。它没有到达 Adam 和 Dave。
(check-expect (count-persons Dave) 3) ✓
(check-expect (count-persons Gustav) 7) ✗ (it's 5)
当我在 Gustav 上调用我的函数时，我如何（如果我想计算所有祖先，包括叔叔）到达 Adam 和 Dave？
tl;博士
本质上如何遍历上面的所有世代？我怎样才能从 'Gustav' 访问 'Dave'（没有对它们的引用！）。如何计算所有祖先，而不仅仅是 parents，然后是他们的 parents，等等。
如果你想在两个方向上都遵循关系，那么树不能完全代表数据，但图可以。如何设计程序涵盖了 Traversing Graphs and A Problem with Generative Recursion.
中的图表
像您这样的普通树表示与如何设计程序中介绍的图形表示之间的主要区别在于，树节点 包含 它的 sub-trees，但是图节点仅指向其使用唯一名称的亲属。
例如，在此数据定义中，person-info 结构不包含其他 person-info 结构。它们只包含[=36=]名称，您必须在主图中查找名称才能找到它对应的person-info结构。
(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.
因为图表的结构是由这些名称决定的，所以您必须注意，如果名称出现在 father、mother 或 children 字段中，则它有一个对应的条目。否则您将无法在图表中查找它。
;; FG String -> PersonInfo
;; Finds the person-info structure that corresponds to the
;; given name in the fg.
(define (lookup-person-info fg name) ....)
在此 family-tree 图中，如果 parent 的条目引用 child，则 child 应引用 parent 作为好吧，还有 vice-versa。这就是 parent-has-child 和 child-has-parent 不变量的原因。如果您有任何扩展此图的操作，它们应该保留这些不变量。
;; 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) ....)
您问题中的 family-tree 图可以通过重复调用这些函数来构造。你可以用一堆嵌套的函数调用来做到这一点，但这样的 let* 更容易阅读：
(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"))))
(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"))
我设计了一个函数来计算特定家谱中的所有人。
该函数使用家谱并计算树中的 child 结构，方法是简单地在每个 parent 上重复并加 1 以组合对两个 parent 的函数调用如果有 no-parent
，则返回 0;; 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)))]))
我的功能 - 当在 Gustav 上启动时 - 计算 Fred 和 Eva，然后是 Eva 的 parent Carl 和 Betrtina。它没有到达 Adam 和 Dave。
(check-expect (count-persons Dave) 3) ✓
(check-expect (count-persons Gustav) 7) ✗ (it's 5)
当我在 Gustav 上调用我的函数时，我如何（如果我想计算所有祖先，包括叔叔）到达 Adam 和 Dave？
tl;博士
本质上如何遍历上面的所有世代？我怎样才能从 'Gustav' 访问 'Dave'（没有对它们的引用！）。如何计算所有祖先，而不仅仅是 parents，然后是他们的 parents，等等。
如果你想在两个方向上都遵循关系，那么树不能完全代表数据，但图可以。如何设计程序涵盖了 Traversing Graphs and A Problem with Generative Recursion.
中的图表像您这样的普通树表示与如何设计程序中介绍的图形表示之间的主要区别在于，树节点 包含 它的 sub-trees，但是图节点仅指向其使用唯一名称的亲属。
例如，在此数据定义中，person-info 结构不包含其他 person-info 结构。它们只包含[=36=]名称，您必须在主图中查找名称才能找到它对应的person-info结构。
(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.
因为图表的结构是由这些名称决定的，所以您必须注意，如果名称出现在 father、mother 或 children 字段中，则它有一个对应的条目。否则您将无法在图表中查找它。
;; FG String -> PersonInfo
;; Finds the person-info structure that corresponds to the
;; given name in the fg.
(define (lookup-person-info fg name) ....)
在此 family-tree 图中，如果 parent 的条目引用 child，则 child 应引用 parent 作为好吧，还有 vice-versa。这就是 parent-has-child 和 child-has-parent 不变量的原因。如果您有任何扩展此图的操作，它们应该保留这些不变量。
;; 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) ....)
您问题中的 family-tree 图可以通过重复调用这些函数来构造。你可以用一堆嵌套的函数调用来做到这一点，但这样的 let* 更容易阅读：
(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"))))