Racket (Recursive structures and processing templates)

Question

I'm stumped on processing this structure, I want to write a function that tells how many topics occur in a discussion.

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

I've been trying for a few hours and haven't solved it yet. I'm not sure where to go from here, anybody have a sharp eye for Racket? I've tried to process the topic first, but haven't had any luck doing it that way.

Answer 1

You should not use make-discussion in your solution, we're trying to traverse the structures, not to create new ones. There are two cases to consider:

• If the digressions list is empty, then we've found one topic, and there's nowhere else to go.
• Otherwise, we count one topic (the current one) and call the recursion over all the elements in the list of digressions, adding their results. This is easy to implement using apply and map

This is what I mean:

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

Of course you can solve this without using apply and map, but for that it's better to write separate procedures as Alex suggests. Anyway, my approach works as expected:

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