remove function not working in my Common lisp code

Question

I am writing a function to delete duplicates of in a list while keeping the last instance. I have written the following code:

(defun remove-dupli (list)
  (setq count1 0)
  (dolist (item1 list)
    (dolist (item2 list)
      (when (equal item1 item2)
        (setf count1 (+ 1 count1))) 
      (if (> count1 1)
        (remove item1 list)))
    (setq count1 0)))

Here, I get the same list as in return. input list: (1 3 4 4 5 4 6) output list:(1 3 4 4 5 4 6)

What might be the problem?

Instead of (remove) function, I tried using (delete) function, but every item gets deleted and the sequence is also altered. I want last instance of the duplicate to remain.

Answer 1

You're trying to implement an iterative version of the standard function delete-duplicates.

> (delete-duplicates '(1 3 4 4 5 4 6))
(1 3 5 4 6)

REMOVE and DELETE removes all elements that satisfy the test. REMOVE returns a new list and don't modify the list passed as an argument. DELETE modifies the list passed as argument.

As you want to remove in place the elements of the list, you should name your function "delete-dupli"

One way to do it is to process each element x of the list one be one, and store in a hash-table ht if you've already seen the current element.

When you've found a duplicate, make the cdr of the precedent element prec point to the element that follows the duplicate.

(defun delete-dupli (lst)
  (let ((ht (make-hash-table :test #'equal)))
    (do ((prec nil x)
         (x lst (rest x)))
        ((null x) lst)
      (if (nth-value 1 (gethash (first x) ht))
          (and prec (setf (cdr prec) (cddr prec)))
          (setf (gethash (first x) ht) t)))))

> (delete-dupli '(1 3 4 4 5 4 6))
=> (1 3 4 5 6)

That way, your time complexity is O(n), and space complexity is O(n).

Now if you want to keep only the last instance of a duplicated element, you could nreverse the list at the start of the function, and then nreverse it at then end. Surprisingly, as nreverse time complexity is O(n), your time complexity is still O(n+n+n) = O(3n) = O(n).

Answer 2

It looks like the op deleted their account. I'll post some answers, and you can critique mine if you like.

1. Using a do* loop:

(defun remove-dupli (numbers)
  (do* ((r-numbers (reverse numbers) (rest r-numbers))
        (number (first r-numbers) (first r-numbers))
        (uniques nil))
       ((null r-numbers) uniques)
    (if (not (member number uniques))
        (setf uniques (cons number uniques)))))

In the repl:

CL-USER> (remove-dupli '(1 3 2 3))
(1 2 3)

CL-USER> (remove-dupli '(1 2 3 10 1 2 3))
(10 1 2 3)

2. Using recursion:

(defun remove-dups (my-list)
  (labels ((remover (dups uniques) ; uniques is a list used to accumulate the unique elements
                                   ; found in the dups list. 
             (let ((obj (first dups)))                              
               (cond ((null dups) uniques) ; If there are no elements left to process
                                           ; in the dups list, then return the uniques list.
                     ((member obj uniques) (remover (rest dups) uniques))
                     ;; If this condition branch evaluates to true, then obj is
                     ;; already in the uniques list, therefore skip obj by not adding it
                     ;; to the uniques list--instead continue processing the rest of the list.

                     (t (remover (rest dups) (cons obj uniques)))))))
                     ;; This branch will execute if obj isn't in the uniques list, so add
                     ;; obj to the uniques list and continue processing the rest of the list.
    
    (remover (reverse my-list) nil))) ; Call remover with the reversed list, which means that duplicates
                                      ; closest to the end of the list will be added to the the uniques list,
                                      ; while duplicates nearer to the front of the list will be discarded.

3. Using loop:

(defun remove-the-dups (numbers)
  (loop for number in (reverse numbers)
        for uniques = (list number)  then (if (member number uniques)
                                              uniques
                                              (cons number uniques))
        finally
           (return uniques)))

Answer 3

The cons function doesn't seem to be working either:

CL-USER> *my-list*
(1 1 2 2)

CL-USER> (cons 3 *my-list*)
(3 1 1 2 2)

CL-USER> *my-list*
(1 1 2 2)

Is it the eclipse? Why have all the common-lisp functions stopped working?

remove, like cons, does not alter its arguments, while delete may or may not alter its argument. Therefore, if you don't do anything with the return value from remove, then the result is discarded.

Paradoxically, you don't actually need to use remove to remove things from a list: instead, you can step through a list, element by element, and either add the element to a results list or not depending on some condition. If you don't add the element to the results list, then you will have removed the element from the results list. You may want to try creating a new list inside your function and return it rather than trying to alter the function's argument.

I want last instance of the duplicate to remain.

If you reverse your list, then you will want the first instance of the duplicate to remain. For instance, if you start with the list

'(1 3 2 3)

and you want the result to be:

'(1 2 3)

then if you start by reversing the list in your function:

'(3 2 3 1)

then you will want to keep the first duplicate and remove the rest.

When you process a list, it's efficient to start at the beginning of the list, then add the elements you want to keep to a results list using cons. As you cons things to a results list, the list gets built up in the reverse order. For instance, if you start with '(1 2 3) and cons the elements to the results list:

       results = nil
       results = (cons 1 results) = '(1)
       results = (cons 2 results) = '(2 1)
       results = (cons 3 results) = '(3 2 1)

Similarly, if you start by reversing the list:

   '(1 3 2 3)

giving you:

    '(3 2 3 1)

then you can cons the first 3 to the results list, giving you:

     '(3)

Then you can cons the 2 to the results list, giving you:

     '(2 3)

Then you can cons the 1 to the results list, giving you:

     '(1 2 3)

Voila! You just need to figure out the logic for when you should discard an element and when you should add an element to the results list.

Answer 4

Help! The + function in Lisp is not adding to my simulated bank account:

(defvar *balance* 0)

(defun credit (cents)
  (+ *balance* cents))

(defun debit (cents)
  (- *balance* cents))

After I call (credit 42), *balance* is still zero. Same with debit.

Any hints appreciated.

Answer 5

Here is a hint:

remove returns a value. remove has a :count named argument.

CL-USER 3 > (let ((my-list (list 1 2 4 1 3 5 2 1))
                  (result-list (list)))
                  
              (setf result-list (remove 2 my-list :count 1))
              
              (print (list 'removing 'one 2 'from my-list
                           'result 'is result-list))

              result-list)

(REMOVING ONE 2 FROM (1 2 4 1 3 5 2 1) RESULT IS (1 4 1 3 5 2 1)) 
(1 4 1 3 5 2 1)