0

这是来自How To Design Programs的家谱 (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"))

我设计了一个函数来计算特定家谱中的所有人。

该函数通过简单地在每个父节点上重复并加 1 以组合对父节点的函数调用并在没有父节点时返回 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 的父母 Carl 和 Betrtina。它没有到达亚当和戴夫。

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

在此处输入图像描述

当我在 Gustav 上调用我的函数时，我如何（如果我想计算所有祖先，包括叔叔）联系到 Adam 和 Dave？

在此处输入图像描述

tl;博士

本质上如何可以遍历上面的所有世代？如何从“Gustav”访问“Dave”（没有提及他们！）。如何计算所有的祖先，不仅仅是父母，然后是他们的父母，等等。

4

1 回答 1

1

如果你想跟踪两个方向的关系，那么 Tree 不能完全表示数据，但 Graph 可以。How to Design Programs 涵盖了Traversing Graphs和A Problem with Generative Recursion中的图。

像您这样的普通树表示与如何设计程序中介绍的图表示之间的主要区别在于，树节点包含其子树，但图节点仅使用唯一名称指向其亲属。

例如，在此数据定义中，person-info结构不包含其他person-info结构。它们只包含名称，您必须在主图中查找名称以找到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) ....)

在这个家谱图中，如果父项的条目引用了一个子项，那么该子项也应该引用父项，反之亦然。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) ....)

您问题中的家谱图可以通过重复调用这些函数来构建。你可以用一堆嵌套的函数调用来做到这一点，但这样更容易阅读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"))))
于 2018-07-22T21:58:13.017 回答