A lisp function refinement

Question

Dear all:

Hi, 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. Thanks a lot!

UPDATE:

Hi guys, 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"

Could you please share your ideas with me, I think this is my final step toward success! Many thanks!

Answer 1

a typical parameter list for such a function would be:

(defun preceders (item vector 
                  &key (start 0) (end (length vector))
                       (test #'eql))
    ...
)

As you can see it has START and END parameters.

TEST is the default comparision function. Use (funcall test item (aref vector i)). Often there is also a KEY parameter...

LENGTH is called repeatedly for every recursive call of PRECEDERS.

I would do the non-recursive version and move two indexes over the vector: one for the first item and one for the next item. Whenever the next item is EQL to the item you are looking for, then push the first item on to a result list (if it is not member there).

For the recursive version, I would write a second function that gets called by PRECEDERS, which takes two index variables starting with 0 and 1, and use that. I would not call POSITION. Usually this function is a local function via LABELS inside PRECEDERS, but to make it a bit easier to write, the helper function can be outside, too.

(defun preceders (item vector 
                  &key (start 0) (end (length vector))
                       (test #'eql))
   (preceders-aux item vector start end test start (1+ start) nil))


(defun preceders-aux (item vector start end test pos0 pos1 result)
  (if (>= pos1 end)
      result
      ...
  ))

Does that help?

Here is the iterative version using LOOP:

(defun preceders (item vector 
                  &key (start 0) (end (length vector))
                       (test #'eql))
  (let ((result nil))
    (loop for i from (1+ start) below end
          when (funcall test item (aref vector i))
          do (pushnew (aref vector (1- i)) result))
    (nreverse result)))

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

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 4

Hi,

The iterative version proposed by Rainer is very nice, it's compact and more efficient since you traverse the sequence only one time; in contrast to the recursive version which calls position at every iteration and thus traverse the sub-sequence every time. (Edit: I'm sorry, I was completely wrong about this last sentence, see Rainer's comment)

If a recursive version is needed, another approach is to advance the start until it meets the end, collecting the result along its way.

(defun precede (obj vec &key (start 0) (end (length vec)) (test #'eql))
  (if (or (null vec) (< end 2)) nil
    (%precede-recur obj vec start end test '())))

(defun %precede-recur (obj vec start end test result)
  (let ((next (1+ start)))
    (if (= next end) (nreverse result)
      (let ((newresult (if (funcall test obj (aref vec next))
                         (adjoin (aref vec start) result)
                         result)))
        (%precede-recur obj vec next end test newresult)))))

Of course this is just another way of expressing the loop version.

test:

[49]> (precede #\a "abracadabra") 
(#\r #\c #\d)
[50]> (precede #\a "this is a long sentence that contains more characters") 
(#\Space #\h #\t #\r)
[51]> (precede #\s "this is a long sentence that contains more characters")
(#\i #\Space #\n #\r)

Also, I'm interested Robert, did your teacher say why he doesn't like using adjoin or pushnew in a recursive algorithm?

Answer 5

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).