scheme - function that checks whether an element appears in an expression or any of its nested expressions twice or more

Question

I wrote the following function which checks if el appears in exp or any of its nested lists once or more and I'm having trouble understanding how to check for twice:

(define appearInExp?
    (lambda (el exp)
        (let ((found?     (ormap (lambda (e) (equal? el e)) exp))
              (listsLeft? (ormap (lambda (e) (list? e)) exp))
              (lists (filter (lambda (e) (list? e)) exp)))

        (if found?
            #t
            (if (not listsLeft?)
                #f
                (let ((elList (extendList el (length lists))))
                    (ormap appearInExp? elList lists)))))))



  *help function:*

    (define extendList
        (lambda (el num)
            (if (equal? num 1)
                `(,el)
                `(,el ,@(extendList el (- num 1))))))

**tests:
(appearInExp? '3 '(1 2 3))             ---> #t
(appearInExp? '3 '(1 2 '(3)))          ---> #t
(appearInExp? '3 '(1 2 '(1 2 ((3)))))  ---> #t

I guess I should add counter and make every recursive call count how many instances of el are in the relevant exp and sum them all together but I'm having trouble doing so..

your help will be very much appreciated.

Answer 1

Following works. It has a counter c and a loop to go through all items of the list. If the item is a list, the function is recusively called:

(define (appearInExp? el exp)
  (let loop ((exp exp)
             (c 0))
    (cond
      [(empty? exp) c]
      [(list? (first exp))
       (loop (rest exp)
             (+ c (appearInExp? el (first exp))))]
      [(equal? el (first exp))
       (loop (rest exp) (add1 c))]
      [else
       (loop (rest exp) c)])))

(appearInExp? '2 '(1 2 3))
(appearInExp? '2 '(1 2 '(2 3)))
(appearInExp? '2 '(1 2 '(1 2 ((3 2)))))

Output:

1
2
3

Answer 2

Another approach you could take is to flatten the list.

(define (flatten lst)
  (cond [(empty? lst) empty]
        [(number? (first lst)) (cons (first lst) (flatten (rest lst)))]
        [else (append (flatten (first lst)) (flatten (rest lst)))]))

(define (f/acc n lst counter)
  (cond [(empty? lst) counter)]
        [(= n (first lst)) (f n lst (add1 counter))]
        [else (f n lst counter)]))

(define (f n lst)
   (f/acc n lst 0))