From: Dae-Won Lim
Subject: [Q] HELP: Remove-Duplicates!
Date: 
Message-ID: <3445C351.CE36CE2A@daelimen.co.kr>
Hi,
I have very big (?) question.

I don't konw how to remove duplicated string
For example,

    (remove-duplicates '("a" "a" "a" "b" "c"))

I expect to have this result. ----> ("a" "b" "c")

Please solve my touble and send me your solution.

Thanks,



Dae-won
My Blue Heaven!

From: Christopher N. Vogt
Subject: Re: [Q] HELP: Remove-Duplicates!
Date: 
Message-ID: <344631E1.9F47CF0F@home.com>
Dae-Won Lim wrote:
> 
> Hi,
> I have very big (?) question.
> 
> I don't konw how to remove duplicated string
> For example,
> 
>     (remove-duplicates '("a" "a" "a" "b" "c"))
> 
> I expect to have this result. ----> ("a" "b" "c")
> 
> Please solve my touble and send me your solution.

remove-duplicates, like most of the sequence operations,
takes a keyword argument :test and the default test is #'eq.
In order for remove-duplicates to work as you would like,
you need to supply the :test keyword argument with #'equal (or
maybe #'string-equal or maybe #'string=) e.g.

(remove-duplicates '("a" "a" "a" "b" "c") :test #'string-equal)
From: Barry Margolin
Subject: Re: [Q] HELP: Remove-Duplicates!
Date: 
Message-ID: <624gp6$bif@pasilla.bbnplanet.com>
In article <·················@daelimen.co.kr>,
Dae-Won Lim  <·····@daelimen.co.kr> wrote:
>I don't konw how to remove duplicated string
>For example,
>
>    (remove-duplicates '("a" "a" "a" "b" "c"))
>
>I expect to have this result. ----> ("a" "b" "c")

Hint: the default comparison function is EQL.  What's the result of

    (eql "a" "a")

?  What comparison function will cause the result you want?

-- 
Barry Margolin, ······@bbnplanet.com
GTE Internetworking, Powered by BBN, Cambridge, MA
Support the anti-spam movement; see <http://www.cauce.org/>
Please don't send technical questions directly to me, post them to newsgroups.
From: Dan
Subject: Re: [Q] HELP: Remove-Duplicates!
Date: 
Message-ID: <62o8d8$bes$1@winter.news.erols.com>
I am actually working on the same problem but I don't have a lisp
interpereter at home to test out my solution.  I figured you could do it
without any tests but instead as follows:

(defun remove-duplicates (lst)
    (reverse (mapcar #'(lambda (elem) (cons elem (remove elem lst)) lst)))

I think this would work but then again I am new to LISP but perhaps this is
an awkward solution.  If anybody knows where I could down load a free lisp
interpereter for a Windows machine I would appreciate it.

Thanks,
Dan Balis
·······@vaxsar.vassar.edu
From: Thomas A. Russ
Subject: Re: [Q] HELP: Remove-Duplicates!
Date: 
Message-ID: <ymibu07w4fl.fsf@sevak.isi.edu>
"Dan" <·······@vaxsar.vassar.edu> writes:

> 
> I am actually working on the same problem but I don't have a lisp
> interpereter at home to test out my solution.  I figured you could do it
> without any tests but instead as follows:
  ~~~~~~~~~~~~~~~~~

Except that the REMOVE function uses tests internally.  That is why, for
example, it accepts the :TEST keyword -- to allow you to specify a test
other than the default EQL test to use for comparing elements. 

> (defun remove-duplicates (lst)
>     (reverse (mapcar #'(lambda (elem) (cons elem (remove elem lst)) lst)))
> 
> I think this would work but then again I am new to LISP but perhaps this is
> an awkward solution.  If anybody knows where I could down load a free lisp
> interpereter for a Windows machine I would appreciate it.

I think that this program will have a few problems:

First off, mapcar applies the function to each element of a list and it
then collects the results of each such function application into a
list.  So for the simple case of applying your function to

 Let f = #'(lambda (elem) (cons elem (remove elem lst)))

 '(a a b a b)

  you would get the equivalent of

 (list (f a) (f a) (f b) (f a) (f b))

  =>

 (list (a b b) (a b b) (b a a a) (a b b) (b a a a))

Which is probably not what you would want.  A couple alternatives that
use things like your solution do come to mind.  For example:

Recursive:

  (defun recursive-remove-duplicates (lst)
     (if (null lst)
	 nil
         (cons (first lst)
                (recursive-remove-duplicates (remove (first lst) lst)))))

This is an N^2 algorithm because it will call REMOVE (which is O(N)), N
times.  It will also cons up a storm, since the calls to remove will
have to generate new list structure.  I woudn't recommend it for
production code.  A recursive solution that uses something like PUSHNEW
and a value accumulating argument would be an improvement on the
consing.

Mapping:

  (defun mapping-remove-duplicates (lst)
     (mapc #'(lambda (elem) (setf lst (cons elem (remove elem lst))))
	   lst)
     lst)

Again this is an N^2 algorithm since it will call REMOVE N times.  It
also has the (to my opinion) extremely distasteful feature of having
side-effects in the mapped function that affect the structure being
mapped over.



Our experience is that the built-in remove-duplicates code in most lisp
implementation uses an O(N^2) algorithm for duplicate removal.  For large
lists this gets to be a real performance bottleneck, so we ended up
implementing our own fast-remove-duplicates using hashtables.  Since we
weren't concerned about preserving the original order, this allowed a
fairly simple O(N) algorithm.  Actually, one that preserved order
wouldn't actually be particularly difficult to write either...

-- 
Thomas A. Russ,  USC/Information Sciences Institute          ···@isi.edu