Common Lisp: Why does this function cause infinite recursion?

Question

I am trying to write a function (lnn; list-not-nil) similar to list that only appends values that are not nil.

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

Here is the code I have so far. For some reason it causes infinite recursion on any input that I try.

(defun lnn (&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)))))

Any ideas? Thanks very much.

Matthias Benkard · Accepted Answer · 2011-10-29 13:26:25Z

4

(defun lnn-helper (so-far &rest items)
  ...)

With this argument list, items will never be nil if you always call lnn-helper with two arguments. Remove the &rest specifier, and it'll work.

answered Oct 29, 2011 at 13:26

Matthias Benkard

15.8k4 gold badges42 silver badges47 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Miriam Over a year ago

Thank you, I made this correction, but I still get infinite recursion.

Matthias Benkard Over a year ago

@Miriam It works for me: (lnn nil 3) => (3); (lnn 1 2 nil 3) => (1 2 3). What input results in the infinite recursion?

Vatine Over a year ago

I'd also be tempted to CONS the elements onto the head of SO-FAR, then finish by returning (NREVERSE SO-FAR), won't matter for short lists, but APPEND is O(n) so LNN-HELPER ends up being O(n^2).

danlei · Accepted Answer · 2011-10-29 14:00:55Z

2

Matthias' answer should have helped. Also note, that this is just a simple reduction:

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

Or even (less efficient):

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

Then:

(defun lnn (&rest elements)
  (remove nil elements))

:)

P.S.: I know this was probably just an exercise in recursion, but SCNR.

edited Oct 29, 2011 at 14:00

answered Oct 29, 2011 at 13:55

danlei

14.3k5 gold badges60 silver badges82 bronze badges

Collectives™ on Stack Overflow

Common Lisp: Why does this function cause infinite recursion?

2 Answers 2

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related