CODEWITHSUNDEEP
lispcommon-lisp
Charles Dix
Charles Dix

Reputation: 3

LISP: Why can't I use cons on an empty list?

I'm trying to construct a unique list of elements by adding to an empty list, using the following code in LISP:

    ;;;MEMSET - return T if an atom is a top-level member of a set, else NIL
    ;;;This is needed for the makeset function
    (DEFUN MEMSET (ATM L)
        (COND ( ( NULL L) NIL )
              ( (EQL ATM(CAR L)) T )
              ( T    (MEMSET ATM (CDR L)) )
        )
    )
    (DEFUN MAKESET(SET1)
        (DO ((UNIQ ()))
            ( (NULL SET1) UNIQ) 
            (COND ( (NOT (MEMSET (CAR SET1) UNIQ))
                      (CONS (CAR SET1) UNIQ)
                  )
            )
        (SETF SET1 (CDR SET1))
        ) 
    )

This particular code results in NIL when I call (makeset '(a b b a c d b a)) - it should result in (a b c d), with no regard to order) - but it looks to me like it should be adding one atom from SET1 that isn't yet in UNIQ each iteration. Can you not add to an empty list declared in a do loop, or is there some other issue I'm having? By the way, I'm using clisp.

Upvotes: 0

Views: 1205

Answers (2)

Rainer Joswig
Rainer Joswig

Reputation: 139251

All the updates can be done with the stepping forms in DO. No need for PUSH or SETF:

(defun makeset (set1)
  (do ((uniq nil (if (memset (car set2) uniq)
                      uniq
                    (cons (car set2) uniq)))
       (set2 set1 (cdr set2)))
      ((null set2) uniq)))

Upvotes: 1

Renzo
Renzo

Reputation: 27404

1. Use proper formatting

Please use a proper formatting when asking something about Common-Lisp. See for instance the first three pages returned by googling "common lisp formatting conventions".

Here is an example of conventional format applied to your functions:

;;; Memset - return T if an atom is a top-level member of a set, else NIL
;;; This is needed for the makeset function

(defun memset (atm l)
  (cond ((null l) nil)
        ((eql atm (car l)) t)
        (t (memset atm (cdr l)))))

(defun makeset (set1)
  (do ((uniq ()))
      ((null set1) uniq)
    (cond ((not (memset (car set1) uniq))
           (push (car set1) uniq)))
    (setf set1 (cdr set1))))

2. Use primitive functions when possible

Both your functions are primitive in Common-Lisp.

remove-duplicates returns a list without duplicate elements, member checks if an element belong to a set.

3. The error in your function

If you still want to use your function, instead of remove-duplicates, here is the problem in it.

If you want to modify a list, you should use a function that modifies something. The cons functions builds a new pair but does not modify anything. So in your form (cons (car set1) uniq) you add a new element to uniq in the sense that you obtain a new list with (car set1) as first element and the elements of unique as rest of the list, but this new list is immediately discarded because it is not assigned to anything.

You can change this either by using the macro setf to assign the new value to the local variable uniq in this way:

(setf uniq (cons (car set1) uniq))

or you can write the equivalent form, through the use of the macro push:

(push (car set1) uniq)

Finally, note that your cond inside the makeset function can be replaced by the more terse when, resulting in this function:

(defun makeset (set1)
  (do ((uniq nil))
      ((null set1) uniq)
    (when (not (memset (car set1) uniq))
      (push (car set1) uniq))
    (setf set1 (cdr set1))))

Upvotes: 5

Related Questions