DrRacket与累加器的相互递归函数

Question

  (define-struct person (name house kids))

;;一个人是(make-person String String ListOfPerson(;;插播。一个人，有名字，房子和孩子名单。

  (define P0  (make-person "Draco"      "Slytherin"  empty))
  (define P1  (make-person "Nymphadora" "Hufflepuff" empty))
  (define P2  (make-person "Sirius"     "Griffindor" empty))
  (define P3  (make-person "Regulus"    "Slytherin"  empty))
  (define P4  (make-person "Bellatrix"  "Slytherin"  empty))
  (define P5  (make-person "Andromeda"  "Slytherin"  (list P1)))
  (define P6  (make-person "Narcissa"   "Slytherin"  (list P0)))
  (define P7  (make-person "Walburga"   "Slytherin"  (list P2 P3)))
  (define P8  (make-person "Alphard"    "Slytherin"  empty))
  (define P9  (make-person "Cygnus"     "Slytherin"  (list P4 P5 P6)))
  (define P10 (make-person "Irma"       "Slytherin"  (list P7 P8 P9)))

原始结构化引用

   ;; Person -> Natural
   ;; Count number of people in a tree
   (check-expect (count P0) 1)
   (check-expect (count P5) 2)
   (check-expect (count P10) 11)
(define (count p)  
  (local 
    [(define (count/person p)
       (add1 (count/lop (person-kids p))))
     (define (count/lop lop)
       (cond [(empty? lop) 0]
             [else
              (+ (count/person (first lop))
                 (count/lop (rest lop)))]))]
    (count/person p)))

这是解决方案

(define (count p)  
  (local 
    [(define (count/person p result todo)
       (count/lop (add1 result)
                  (append (person-kids p) todo)))
     (define (count/lop result todo)
       (cond [(empty? todo) result]
             [else
              (count/person (first todo) 
                            result
                            (rest todo))]))])
  (count/person p 0 empty))
;; Accumulator result is Natural
;; Invariant: the total computed so far
;; Accumulator todo is (listof Person)
;; Invariant: persons not yet visited by count/person

我

很难理解这是如何从最初的正常相互参考解决方案中得出的，任何人都可以向我解释一下吗？

Answer 1

您的解决方案不遵循基本设计配方。以下是尝试制定直接解决方案的尝试：

(define-struct person (kids))
; sum : list-of-numbers -> number
(define (sum xs)
  (cond
    [(empty? xs) 0]
    [else        (+ (first xs) (sum (rest xs)))]))
; count : person -> number
(define (count p)
  (cond 
    [(empty? (person-kids p)) 1]             ; p is 1 person, 0 kids
    [else (+ 1                               ; p is 1 person and 
             (sum (map count                 ; we must sum over the
                       (person-kids p))))])) ; count of each kid

在如何设计程序的第 30 章和第 31 章中，您可以阅读有关从此样式到累加器样式(您的解决方案使用(的转换。转换的详细信息在第 31.3 节中。

HtDP 第 31.3 节"将函数转换为累加器样式"