Racket (Рекурсивные структуры и шаблоны обработки)

Question

Я в тупике при обработке этой структуры, я хочу написать функцию, которая сообщает, сколько тем возникает в обсуждении.

; a Discussion is (make-discussion String Digressions)
(define-struct discussion [topic digressions])

; Digressions is [ListOf Discussion]



; count-topics : Discussion -> Number
; counts the number of total topics in a discussion, including repeated topics

(define (count-topics d)
  (cond
    [(empty? (discussion-digressions d)) 0]
    [(cons?  (discussion-digressions d)) (add1 (count-topics (make-discussion (first (discussion-topic d))
                                                                                (list (make-discussion (rest (discussion-digressions d)))))))]))


(check-expect (count-topics  (make-discussion "music" (list (make-discussion "politics" empty)))) 2)

Я пытался несколько часов и еще не решил. Я не уверен, куда go отсюда, у кого-нибудь есть зоркий глаз на Racket? Я пробовал сначала обработать топи c, но мне так и не удалось.

Answer 1

Вы не должны использовать make-discussion в своем решении, мы пытаемся обойти структуры, а не создавать новые. Следует рассмотреть два случая:

• Если список digressions пуст, значит, мы нашли одну вершину c, а go больше некуда.
• В противном случае мы считаем одну вершину c (текущую) и вызываем рекурсию по всем элементам в списке digressions, складывая их результаты. Это легко реализовать, используя apply и map

Вот что я имею в виду:

(define (count-topics d)
  (cond
    [(empty? (discussion-digressions d)) 1]
    [else (add1 (apply + (map count-topics (discussion-digressions d))))]))

Конечно, вы можете решить эту проблему без использования apply и map, но для этого лучше писать отдельные процедуры, как предлагает Алекс. В любом случае мой подход работает так, как ожидалось:

(count-topics
 (make-discussion "music"
                  (list (make-discussion "politics" empty))))
=> 2