CODEWITHSUNDEEP
recursionlispcommon-lisp
AreTaro
AreTaro

Reputation: 41

Lisp exit defun function with nil as value

I'm trying to do a recursive version of the function position called positionRec. The objective is define the position of an element in a list, and if the element is not in the list return "nil". For exemple: (positionRec 'a '(b c d a e)) => 4 (positionRec 'a '(b c d e)) => nil

I have written:

(defun positionRec (c l)
  (cond
   ((atom l) (return nil))
   ((equal c (first l)) 1)
   (t (+ 1 (positionRec c (rest l)))) ) )

I don't succeed to return nil. I have an error "*** - return-from: no block named nil is currently visible"

Anyone can teach me how to do it?

Upvotes: 0

Views: 496

Answers (2)

Vatine
Vatine

Reputation: 21258

The main problem is that you're trying to deal with incommensurable values. On the one hand, you want to deak with numbers, on the other, you want to deal with the empty list. You cannot add a number to a list, but you will inherently try doing so (you have an unconditional (1+ ...) call in your default branch in your cond).

There are ways to work around that, one being to capture the value:

(cond
  ...
  (t (let ((val (positionRec c (rest l))))
        (when val ;; Here we "pun" on nil being both false and the "not found" value
           (1+ val)))))

Another would be to use a method amenable to tail-recursion:

(defun positionrec (element list &optional (pos 1))
  (cond ((null list) nil)
        ((eql element (head list)) pos)
        (t (positionrec element (rest list) (1+ pos)))))

The second function can (with a sufficently smart compiler) be turned into, basically, a loop. The way it works is by passing the return value as an optional parameter.

You could build a version using return, but you would probably need to make use of labels for that to be straight-forward (if you return nil directly from the function, it still ends up in the (1+ ...), where you then have numerical incompatibility) so I would go with either "explicitly capture the value and do the comparison against nil/false" or "the version amenable to tail-call elimination" and simply pick the one you find the most readable.

Upvotes: 0

user5920214
user5920214

Reputation:

Lisp is an expression language: it has only expressions an no statemends. This means that the value of a call to a function is simply the value of the last form involved in that call This is different than many languages which have both statements and expressions and where you have to explicitly litter your code with explicit returns to say what the value of a function call is.

A cond form in turn is an expression. The value of an expression like

(cond
 (<test1> <test1-form1> ... <test1-formn>)
 (<test2> <test1-form1> ... <test1-formn>)
 ...
 (<testn> <testn-form1> ... <testn-formnn>))

is the <testm-formn> of the first <testm> which is true, or nil if none of them are (and as a special case, if there are no forms after a test which is true the value is the value of that test).

So in your code you just need to make sure that the last form in the test which succeeds is the value you want:

(defun positionRec (c l)
  (cond
   ((atom l) nil)
   ((equal c (first l)) 1)
   (t (+ 1 (positionRec c (rest l))))))

So, what use is return? Well, sometimes you really do want to say 'OK, in the middle of some complicated loop or something, and I'm done now':

(defun complicated-search (...)
  (dolist (...)
    (dolist (...)
      (dotimes (...)
        (when <found-the-interesting-thing>
          (return-from complicated-search ...))))))

return itself is simply equivalent to (return-from nil ...) and various constructs wrap blocks named nil around their bodies. Two such, in fact, are dotimes and dolist, so if you want to escape from a big loop early you can do that:

(defun complicated-search (...)
  (dolist (...)
    (when ...
      (return 3))))                     ;same as (return-from nil 3)

But in general because Lisp is an expression language you need to use return / return-from much less often than you do in some other languages.

In your case, the modified function is going to fail: if you get to the ((atom l) nil) case, then it will return nil to its parent which will ... try to add 1 to that. A better approach is to keep count of where you are:

(defun position-of (c l)
  (position-of-loop c l 1))

(defun position-of-loop (c l p)
  (cond
   ((atom l) nil)
   ((equal c (first l)) p)
   (t (position-of-loop c (rest l) (1+ p)))))

Note that this (as your original) uses 1-based indexing: zero-based would be more compatible with the rest of CL.

It would probably be idiomatic to make position-of-loop a local function:

(defun position-of (c l)
  (labels ((position-of-loop (lt p)
             (cond
              ((atom lt) nil)
              ((equal c (first lt)) p)
              (t (position-of-loop (rest lt) (1+ p))))))
    (position-of-loop l 1)))

And you could then use an iteration macro if you wanted to make it a bit more concise:

(defun position-of (c l)
  (iterate position-of-loop ((lt l) (p 1))
    (cond
     ((atom lt) nil)
     ((equal c (first lt)) p)
     (t (position-of-loop (rest lt) (1+ p))))))

Upvotes: 3

Related Questions