Searching within nested list Scheme/Racket

1
votes
(define-struct school (name students))
;; An SchoolChart is a (make-school Str (listof SchoolChart))
;; names are unique

I have a school chart say

(define s-chart (make-school "Tom" (list 
(make-school "James" empty) 
(make-school "Claire" 
    (make-school "David" empty) 
    (make-school "Travis" empty)) 
(make-school "Timmy" empty))))

This is a general tree, say I define a function

(define (find-name name school)) ;;produces true if found/false if not.

How do I go about the recursion? This specific case is fine, but each child can have infinite children? I just need a hint

2
schemeracket
If you are searching you check if the current node is your answer, else you check if each of the children using recursion, when no node left and nothing found you return a false or something to indicate failure. Ps: for infinite children recursion won't help so it cannot be that. If you meant cycles then you need a structure to know the visited nodes. - Sylwester

2 Answers

1
votes

There can only be a finite amount of children.
The amount is arbitrary and only bounded by your machine's memory, but it can't be infinite.

(And your s-chart is ill-formed, since "Claire"'s children are not a list.)

The recursion can be pretty simple.
Here's a depth-first search:

(define (find-name name school)
    (or (string=? name (school-name school))
        (any (lambda (s) (find-name name s)) (school-students school))))

where (any p ls) is #t if and only if (p e) is #t for at least one element e of the list ls.

Now all that remains is to write any...

0
votes

Following recursively checks all items and, if found, add the name to a list outside the loop. However, it needs to use set!. It uses string-prefix? instead of string=? for demonstration purposes (to get more names in the current structure):

(define-struct school (name students))

(define s-chart
  (make-school "Tom"
               (list 
                (make-school "James" empty) 
                (make-school "Claire" (list
                                       (make-school "David" empty) 
                                       (make-school "Travis" empty)))
                (make-school "Timmy" empty))))


(define (find-name name school)
  (define ol '())
  (let loop ((s school))
    (cond
      [(list? s)
       (when (not(empty? s))
           (begin (loop (first s))
                  (loop (rest s))))]
      [else
       (when (string-prefix? (school-name s) name)
         (set! ol (cons (school-name s) ol)))
       (loop (school-students s))
         ]))
  ol
  )

(find-name "T" s-chart)

Output: 

'("Timmy" "Travis" "Tom")