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

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

; 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)

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


recursive-datastructures racket mutual-recursion list-processing
person birds_the_word    schedule 08.05.2020    source источник
comment
Есть два определения данных. Один для Discussion и один для Digressions, которые взаимно рекурсивны. Если структура программы соответствует структуре данных, должно быть две функции, по одной для каждого datadef, которые взаимно рекурсивны так же, как и datadef.   -  person Alex Knauth    schedule 09.05.2020
comment
Один запах кода в вашем коде повторяется на новом построенном make-discussion вместо меньшего фрагмента данных. В Проектирование с использованием ссылок на себя Определения данных для структурной рекурсии, естественная рекурсия всегда находится в части исходных данных, например, в результате селектора поля, а не в новой структуре, созданной прямо здесь.   -  person Alex Knauth    schedule 09.05.2020

Ответы (1)


arrow_upward
1
arrow_downward

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

  • Если список digressions пуст, значит, мы нашли одну тему и больше некуда идти.
  • В противном случае мы считаем одну тему (текущую) и вызываем рекурсию по всем элементам в списке 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
person Óscar López    schedule 08.05.2020