Блог

Главная - Вопросы по программированию - Common Lisp: почему эта функция вызывает бесконечную рекурсию?

Common Lisp: почему эта функция вызывает бесконечную рекурсию?

#lisp #common-lisp #infinite-loop

#lisp #common-lisp #бесконечный цикл

Вопрос:

Я пытаюсь написать функцию (lnn; list-not-nil), аналогичную list, которая добавляет только значения, отличные от nil .

 (list nil 3) --> (NIL 3)
(lnn nil 3) --> (3)

Вот код, который у меня есть на данный момент. По какой-то причине это вызывает бесконечную рекурсию при любом вводе, который я пытаюсь.

 (defun lnn (amp;rest items)
  (lnn-helper nil items))

(defun lnn-helper (so-far items)
   (cond ((null items)
           so-far)
     ((null (car items))
      (lnn-helper so-far (cdr items)))
     (t (lnn-helper (append so-far (list (car items))) (cdr items)))))

Есть идеи? Большое спасибо.

Ответ №1:

 (defun lnn-helper (so-far amp;rest items)
  ...)

С этим списком аргументов items никогда не будет nil , если вы всегда вызываете lnn-helper с двумя аргументами. Удалите amp;rest спецификатор, и он будет работать.

Комментарии:

1. Спасибо, я внес это исправление, но я все равно получаю бесконечную рекурсию.

2. @Miriam Это работает для меня: (lnn nil 3) => (3) ; (lnn 1 2 nil 3) => (1 2 3) . Какой ввод приводит к бесконечной рекурсии?

3. У меня также возникнет соблазн поместить элементы в начало SO-FAR , а затем завершить возвращением (NREVERSE SO-FAR), не имеет значения для коротких списков, но APPEND — это O (n), поэтому LNN-HELPER заканчивается O(n ^ 2) .

Ответ №2:

Ответ Маттиаса должен был помочь. Также обратите внимание, что это всего лишь простое сокращение:

 (defun lnn (amp;rest elements)
  (reduce (lambda (elt acc) (if elt (cons elt acc) acc))
          elements
          :from-end t
          :initial-value nil))

Или даже (менее эффективный):

 (defun lnn (amp;rest elements)
  (reduce #'cons (remove nil elements) :from-end t :initial-value nil))

Затем:

 (defun lnn (amp;rest elements)
  (remove nil elements))

🙂

PS: Я знаю, что это, вероятно, было просто упражнение в рекурсии, но SCNR.