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

user_9616438 0
Viewed 108

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!

racket recursion scheme lisp functional-programming
4 Answers

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
user_2013590

I don't recommend actually taking this approach because a normal tail-recursive implementation is a lot more efficient, simpler, and easier to understand, but you can use a continuation to short-circuit unwinding the call stack in the failure case:

(define (first_elt_occ lst num)
  (call/cc
   (lambda (return)
     (letrec ((loop (lambda (lst)
                      (cond
                       ((null? lst) (return #f))
                       ((= (car lst) num) 0)
                       (else (+ 1 (loop (cdr lst))))))))
        (loop lst)))))
user_99521960

The basic find first occurrence "skeleton" function is

(define (first_elt_occ lst num)
   (and (not (null? lst))
        (or (equal (car lst) num)
            (first_elt_occ (cdr lst) num))))

This does not return index though. How to add it in?

(define (first_elt_occ lst num)
   (and (not (null? lst))
        (or (and (equal (car lst) num) 0)
            (+ 1 (first_elt_occ (cdr lst) num)))))

Does it work? Not if the element isn't there! It'll cause an error then. How to fix that? Change the +, that's how!

(define (first_elt_occ lst num)
  (let ((+ (lambda (a b) (if b (+ a b) b))))
    (and (not (null? lst))
         (or (and (= (car lst) num) 0)
             (+ 1 (first_elt_occ (cdr lst) num))))))

And now 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 '(3 2 3 3 4) 5)
#f

And to get your second desired function, we restructure it a little bit, into

(define (first_elt_occ lst num)
  (let ((+ (lambda (a b) ...... )))
    (and (not (null? lst))
         (+ (and (= (car lst) num) 0)
            (first_elt_occ (cdr lst) num)))))

Now, what should that new + be? Can you finish this up? It's straightforward!

user_8498910

It's unclear why you are opposed to tail recursion. You talk about "proper recursion", which is not a technical term anyone uses, but I assume you mean non-tail recursion: a recursive process rather than an iterative one, in SICP terms. Rest assured that tail recursion is quite proper, and in general is preferable to non-tail recursion, provided one does not have to make other tradeoffs to enable tail recursion.

As Óscar López says, this problem really is easier to solve with tail recursion. But if you insist, it is certainly possible to solve it the hard way. You have to avoid blindly adding 1 to the result: instead, inspect it, adding 1 to it if it's a number, or returning it unchanged if it's false. For example, see the number? predicate.

user_6254030
Related