How to return false if the number is not found in the list

Question

So, I am trying to do this hw problem: write a function that takes two arguments, a list and a number, and the function returns the index of the leftmost occurrence of the number in the list. For example:

• If '(1 2 3 3 4) and num = 3, then it returns 2

• If '(3 2 3 3 4) and num = 3, then it returns 0

I was able to do that part but what if the number was never found? What if I want to return false when num is not found in the list? How do I do that?

Please remember, I am trying to do this in proper recursion, not tail recursion.

Here's my code.

(define (first_elt_occ lst num)
   (cond
       ((null? lst) #f)
       ((eq? (car lst) num) 0)
       (else
          (+ 1 (first_elt_occ (cdr lst) num)))))

(first_elt_occ '(1 2 3 3 4) 3) ;2
(first_elt_occ '(3 2 3 3 4) 3) ;0
(first_elt_occ '(1 2 5 4 3) 3) ;4
(first_elt_occ '(1 2 5 4 3) 6) ;Error 
     ;(makes sense because you can't add boolean expression)

Another question I have is, how would I approach this problem, if I was asked to return the index of the rightmost occurrence of the number in a list (proper recursion). For example: '(3 4 5 4 3 7 ), num = 3 returns 4.

Thank you!

Answer 1

As suggested in the comments, this will be easier if we implement the procedure using tail recursion - by the way, tail recursion is "proper recursion", what makes you think otherwise?

By defining a helper procedure called loop and passing the accumulated result in a parameter, we can return either #f or the index of the element:

(define (first_elt_occ lst num)
  (let loop ((lst lst) (acc 0))
    (cond
      ((null? lst) #f)
      ((equal? (car lst) num) acc)
      (else (loop (cdr lst) (add1 acc))))))

If, for some bizarre requirement you can't use tail recursion in your solution, it's possible to rewrite you original solution to account for the case when the answer is #f - but this isn't as elegant or efficient:

(define (first_elt_occ lst num)
  (cond
    ((null? lst) #f)
    ((equal? (car lst) num) 0)
    (else
     (let ((result (first_elt_occ (cdr lst) num)))
       (if (not result) #f (add1 result))))))

Either way, it works as expected:

(first_elt_occ '(1 2 3 3 4) 3) ; 2
(first_elt_occ '(3 2 3 3 4) 3) ; 0
(first_elt_occ '(1 2 5 4 3) 3) ; 4
(first_elt_occ '(1 2 5 4 3) 6) ; #f