DrRacket взаимно рекурсивные функции с аккумулятором

Question

(define-struct person (name house kids)) 

;; Лицо (строка 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 section 31.3 'Transforming Functions into Accumulator-Style'