A lisp function refinement

Question

I've done the Graham Common Lisp Chapter 5 Exercise 5, which requires a function that takes an object X and a vector V, and returns a list of all the objects that immediately precede X in V.

It works like:

> (preceders #\a "abracadabra")
(#\c #\d #r)

I have done the recursive version:

(defun preceders  (obj vec &optional (result nil) &key (startt 0))
  (let ((l (length vec)))
    (cond ((null (position obj vec :start startt :end l)) result) 
          ((= (position obj vec :start startt :end l) 0)
           (preceders obj vec result 
                      :startt (1+ (position obj vec :start startt :end l))))  
          ((> (position obj vec :start startt :end l) 0)
           (cons (elt vec (1- (position obj vec :start startt :end l))) 
                 (preceders obj vec result 
                            :startt (1+ (position obj vec
                                                 :start startt
                                                 :end l))))))))

It works correctly, but my teachers gives me the following critique:

"This calls length repeatedly. Not so bad with vectors, but still unnecessary. More efficient and more flexible (for the user) code is to define this like other sequence processing functions. Use :start and :end keyword parameters, the way the other sequence functions do, with the same default initial values. length should need to be called at most once."

I am consulting the Common Lisp textbook and google, but there seem to be of little help on this bit: I don't know what he means by "using :start and :end keyword parameters", and I have no clue of how to "call length just once". I would be grateful if you guys could give me some idea how on to refine my code to meet the requirement that my teacher posted.

UPDATE:

Now I have come up with the following code:

(defun preceders (obj vec
                  &optional (result nil)
                  &key (start 0) (end (length vec)) (test #'eql))  
  (let ((pos (position obj vec :start start :end end :test test)))  
    (cond ((null pos) result)
          ((zerop pos) (preceders obj vec result
                                 :start (1+ pos) :end end :test test)) 
          (t (preceders obj vec (cons (elt vec (1- pos)) result)
                       :start (1+ pos) :end end :test test)))))

I get this critique:

"When you have a complex recursive call that is repeated identically in more than one branch, it's often simpler to do the call first, save it in a local variable, and then use the variable in a much simpler IF or COND."

Also,for my iterative version of the function:

(defun preceders (obj vec) 
  (do ((i 0 (1+ i))
       (r nil (if (and (eql (aref vec i) obj) 
                       (> i 0)) 
                  (cons (aref vec (1- i)) r) 
                  r))) 
      ((eql i (length vec)) (reverse r)))) 

I get the critique

"Start the DO at a better point and remove the repeated > 0 test"

Answer 1

Answer for your first UPDATE.

first question:

see this

(if (foo)
  (bar (+ 1 baz))
  (bar baz))

That's the same as:

(bar (if (foo)
        (+ 1 baz)
        baz))

or:

(let ((newbaz (if (foo)
                 (+ 1 baz)
                 baz)))
  (bar newbaz))

Second:

Why not start with I = 1 ?

See also the iterative version in my other answer...

Answer 2

Since you already have a solution that's working, I'll amplifiy Rainer Joswig's solution, mainly to make related stylistic comments.

(defun preceders (obj seq &key (start 0) (end (length seq)) (test #'eql))          
  (%preceders obj seq nil start end test))

The main reason to have separate helper function (which I call %PRECEDERS, a common convention for indicating that a function is "private") is to eliminate the optional argument for the result. Using optional arguments that way in general is fine, but optional and keyword arguments play horribly together, and having both in a single function is a extremely efficient way to create all sorts of hard to debug errors.

It's a matter of taste whether to make the helper function global (using DEFUN) or local (using LABELS). I prefer making it global since it means less indentation and easier interactive debugging. YMMV.

A possible implementation of the helper function is:

(defun %preceders (obj seq result start end test)
  (let ((pos (position obj seq :start start :end end :test test)))
       ;; Use a local binding for POS, to make it clear that you want the 
       ;; same thing every time, and to cache the result of a potentially 
       ;; expensive operation. 
    (cond ((null  pos) (delete-duplicates (nreverse result) :test test))             
          ((zerop pos) (%preceders obj seq result (1+ pos) end test))
          ;; I like ZEROP better than (= 0 ...). YMMV.
          (t (%preceders obj seq 
                         (cons (elt seq (1- pos)) result)
                         ;; The other little bit of work to make things 
                         ;; tail-recursive.      
         (1+ pos) end test)))))

Also, after all that, I think I should point out that I also agree with Rainer's advice to do this with an explicit loop instead of recursion, provided that doing it recursively isn't part of the exercise.

EDIT: I switched to the more common "%" convention for the helper function. Usually whatever convention you use just augments the fact that you only explicitly export the functions that make up your public interface, but some standard functions and macros use a trailing "*" to indicate variant functionality.

I changed things to delete duplicated preceders using the standard DELETE-DUPLICATES function. This has the potential to be much (i.e., exponentially) faster than repeated uses of ADJOIN or PUSHNEW, since it can use a hashed set representation internally, at least for common test functions like EQ, EQL and EQUAL.

Answer 3

A slightly modofied variant of Rainer's loop version:

(defun preceders (item vector 
                  &key (start 0) (end (length vector))
                  (test #'eql))
  (delete-duplicates
   (loop
      for index from (1+ start) below end 
      for element = (aref vector index) 
      and previous-element = (aref vector (1- index)) then element
      when (funcall test item element)
      collect previous-element)))

This makes more use of the loop directives, and among other things only accesses each element in the vector once (we keep the previous element in the previous-element variable).