How to write one's own remove-duplicates?

Discussion of Common Lisp
Post Reply
blerta12
Posts: 2
Joined: Wed Feb 17, 2010 4:38 am

How to write one's own remove-duplicates?

Post by blerta12 » Wed Feb 17, 2010 4:45 am

Hello guys! I'm trying to write my own remove-duplicates function. The code I have written so far works fine when the repeating elements of the list are non-adjacent, but it doesn't work at all when they are. Any suggestions? Thank you in advance.

Code: Select all

(defun uniq (L)
(if (= (length L) 0) NIL                                                
(if (> (length L) 1) 
(uniq (delete (first L) L))))                           
L)

gugamilare
Posts: 406
Joined: Sat Mar 07, 2009 6:17 pm
Location: Brazil
Contact:

Re: How to write one's own remove-duplicates?

Post by gugamilare » Wed Feb 17, 2010 5:56 am

blerta12 wrote:Hello guys! I'm trying to write my own remove-duplicates function. The code I have written so far works fine when the repeating elements of the list are non-adjacent, but it doesn't work at all when they are. Any suggestions? Thank you in advance.

Code: Select all

(defun uniq (L)
(if (= (length L) 0) NIL                                                
(if (> (length L) 1) 
(uniq (delete (first L) L))))                           
L)
It seems you are trying to destructively modify the list. If you want to modify the list, you should explicitly say so using setf:

Code: Select all

(defun uniq (L)
  (if (= (length L) 0)
      NIL                                                
      (when (> (length L) 1)
        (setf (cdr L) (delete (first L) L))
        (uniq (cdr L))))
  L)
Testing that the list is empty can be done faster with the function null, so:

Code: Select all

(defun uniq (L)
  (if (null L)
      NIL                                                
      (when (not (null (cdr L)))
        (setf (cdr L) (delete (first L) L))
        (uniq (cdr L))))
  L)

blerta12
Posts: 2
Joined: Wed Feb 17, 2010 4:38 am

Re: How to write one's own remove-duplicates?

Post by blerta12 » Wed Feb 17, 2010 7:30 am

Thanks a lot :) That is exactly the result I wanted to achieve :)

smithzv
Posts: 94
Joined: Wed Jul 23, 2008 11:36 am

Re: How to write one's own remove-duplicates?

Post by smithzv » Thu Feb 18, 2010 12:37 pm

Well, strictly speaking, remove-duplicates is supposed to leave the list unchanged, so this is an implementation of delete-duplicates.

JamesF
Posts: 98
Joined: Thu Jul 10, 2008 7:14 pm

Re: How to write one's own remove-duplicates?

Post by JamesF » Sun Feb 21, 2010 9:25 pm

To add a late hint or two: as smithzv pointed out, remove-duplicates should return a new list.
While strict functional style discourages you from destructively modifying data structures, in practice there's no problem with a function modifying a structure that it has created and that won't be modified by anything else until it's returned by the function that generated it.

So what you might want to look into is a function that accepts a list and an accumulator, that makes use of member and either append or nconc (you may wish to try both, to expand the learning opportunity), and that calls itself with a modified reference to the list that it received as an argument, unless it's run out of list. Tail recursion FTW :)

I'd write a draft demo version here, but this sounds like a homework assignment to help you get the hang of thinking in Lisp, and I'd hate to cheat you of that benefit. Besides, my description probably gave the game away anyway.

Post Reply