CODEWITHSUNDEEP
recursionfunctional-programminglisp
bos570
bos570

Reputation: 1523

Recursively find element position in list using LISP

Here is my problem:
Without using MEMBER, complete the following definition of a recursive function POS such that if L is a list and E is an element of L then (POS E L) returns the position of the first occurrence of E in L, and such that if E is not an element of L then (POS E L) returns 0.

This is the solution have come up with:

(DEFUN POS (E L)
(COND ((ENDP L)  0)
((EQUAL E (CAR L)) 1 )
(T 
      (+ 1 (POS E (CDR L)) )   

  )))

The algorithm works fine if the element I am looking for is in the list. My problem is that when the element is not in the list I will get the length of the list.

Example: 

list[1,2,3,4] Find: 5  will reurn 4

How do I get it to return 0 if element is not found. And as it is functional programming I can't use loops or variable.

Upvotes: 0

Views: 1404

Answers (2)

coredump
coredump

Reputation: 38967

You always return (+ 1 <recursive-call>). But what if the recursive result is zero? You should check that return value before computing the result.

  • if you find an occurence, return 1
  • if you don't find a result, compute recursively, which gives you R
  • if R is zero, return zero
  • otherwise, return R + 1

As an aside, the Common Lisp way would be:

(or (position E L :test #'equal) 0)

Upvotes: 4

mobiuseng
mobiuseng

Reputation: 2396

As @coredump has explained, the problem is that you are always adding 1 to the result, even if you haven't found the element. I would keep the track of the current position within the list by adding an extra parameter to function POS:

(defun pos (element list &optional (start 0))
  (cond ((endp list) 0)
        ((equal element (first list)) (1+ start))
        (t (pos element (rest list) (1+ start)))))

Testing:

(pos 'a '(b a c d a))
2

(pos 'a '(a d a f g))
1

(pos 'w '(a b c d e f))
0

One extra benefit: this function generates iterative process due to recursive call being in tail-call position (however, ANSI Common Lisp does not guarantee it will do tail-call optimization! AFAIK, CLisp doesn't do it; SBCL and CCL will do for optimized code, see DECLARE). More idiomatic Common Lisp solution would be using LOOP:

(defun pos (element list)
  (loop for x in list
     counting x into pos
     when (equal element x)
     return pos
     end
     finally (return 0)))

Upvotes: 0

Related Questions