[Q] HELP: Remove-Duplicates!

[Barry Margolin]

In article <3445C351...@daelimen.co.kr>,
Dae-Won Lim <dw...@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, bar...@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.

[Dae-Won Lim]

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!

[Christopher N. Vogt]

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)

[Dan]

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
dab...@vaxsar.vassar.edu

[Thomas A. Russ]

"Dan" <dab...@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 t...@isi.edu