A lisp function refinement
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)))
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
.
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).