Уточнение функции lisp

типичный список параметров для такой функции:

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

Как видите, у него есть параметры START и END.

ТЕСТ — это функция сравнения по умолчанию. Используйте (элемент теста funcall (вектор aref i)). Часто есть еще КЛЮЧЕВОЙ параметр...

LENGTH вызывается повторно для каждого рекурсивного вызова PRECEDERS.

Я бы сделал нерекурсивную версию и переместил два индекса по вектору: один для первого элемента и один для следующего элемента. Всякий раз, когда следующий элемент является EQL для элемента, который вы ищете, затем вставьте первый элемент в список результатов (если он там не является членом).

Для рекурсивной версии я бы написал вторую функцию, которая вызывается PRECEDERS, которая принимает две индексные переменные, начинающиеся с 0 и 1, и использовала ее. Я бы не назвал POSITION. Обычно эта функция является локальной функцией через LABELS внутри PRECEDERS, но чтобы упростить ее написание, вспомогательная функция может быть и снаружи.

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

Это помогает?

Вот итеративная версия с использованием 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)))

Поскольку у вас уже есть работающее решение, я дополню решение Райнера Джосвига. , в основном, чтобы сделать соответствующие стилистические комментарии.

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

Основная причина иметь отдельную вспомогательную функцию (которую я называю %PRECEDERS, общепринятое соглашение для обозначения того, что функция является «частной») состоит в том, чтобы исключить необязательный аргумент для результата. Использование необязательных аргументов таким образом в целом нормально, но необязательные аргументы и аргументы с ключевыми словами ужасно сочетаются друг с другом, и наличие обоих в одной функции является чрезвычайно эффективным способом создания всех видов трудно отлаживаемых ошибок.

Делать вспомогательную функцию глобальной (используя DEFUN) или локальной (используя LABELS) — дело вкуса. Я предпочитаю делать его глобальным, так как это означает меньше отступов и более простую интерактивную отладку. YMMV.

Возможная реализация вспомогательной функции:

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

Кроме того, после всего этого я думаю, что должен указать, что я также согласен с советом Райнера сделать это с помощью явного цикла вместо рекурсии, при условии, что рекурсивное выполнение этого не является частью упражнения.

EDIT: я переключился на более распространенное соглашение "%" для вспомогательной функции. Обычно любое соглашение, которое вы используете, лишь дополняет тот факт, что вы явно экспортируете только те функции, которые составляют ваш общедоступный интерфейс, но некоторые стандартные функции и макросы используют завершающий «*» для обозначения вариантов функциональности.

Я изменил вещи, чтобы удалить повторяющиеся прецеденты, используя стандартную функцию DELETE-DUPLICATES. Это может быть намного (то есть экспоненциально) быстрее, чем многократное использование ADJOIN или PUSHNEW, поскольку оно может использовать хешированное представление множества внутри, по крайней мере, для общих тестовых функций, таких как EQ, EQL и EQUAL.

Слегка модифицированный вариант версии петли Райнера:

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

Это позволяет больше использовать директивы цикла и, помимо прочего, обращается к каждому элементу в векторе только один раз (мы сохраняем предыдущий элемент в переменной предыдущего элемента).

Ответ на ваше первое ОБНОВЛЕНИЕ.

Первый вопрос:

видеть это

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

Это то же самое, что:

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

or:

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

Второй:

Почему бы не начать с I = 1 ?

Смотрите также итеративную версию в моем другом ответе...

Итеративная версия, предложенная Райнером, очень хороша, она компактна и более эффективна, так как вы проходите последовательность только один раз; в отличие от рекурсивной версии, которая вызывает position на каждой итерации и, таким образом, каждый раз проходит подпоследовательность. (Изменить: извините, я был совершенно не прав насчет этого последнее предложение, см. комментарий Райнера)

Если требуется рекурсивная версия, другой подход состоит в том, чтобы продвигать start до тех пор, пока он не встретится с end, собирая результат по пути.

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

Конечно, это всего лишь еще один способ выразить версию loop.

тестовое задание:

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

Кроме того, мне интересно, Роберт, сказал ли ваш учитель, почему ему не нравится использовать adjoin или pushnew в рекурсивном алгоритме?