Re: intersection

From: Pascal Bourguignon (spam_at_thalassa.informatimago.com)
Date: 01/28/04 

Date: 28 Jan 2004 21:18:09 +0100

tuanglen@hotmail.com (Tuang) writes:

> Erik Naggum <erik@naggum.no> wrote in message news:<3284290946418800KL2065E@naggum.no>...
> > * Tuang
> > | The Hyperspec says the following about intersection:
> >
> > If one of the lists contains duplicate elements, there may be
> > duplication in the result.
> >
> > Sets implemented as lists are defined on the presence of members of
> > the set in the list. It is strictly speaking an error to duplicate
> > members of the set in the list representation, but this error is hard
> > to detect inexpensively, so the rational course of action is to allow
> > it with suitable hand-waving. The above is an instance of precisely
> > such hand-waving.
>
> and Marco said:
>
> > Remember the definition of an intersection: the
> > intersection of two sets A and B is the the set of all x, where x is
> > an element of A and x is an element of B. Taking this into account the
> > solution could also be '(A) or '(A A A A A A A A A)
>
>
> Both of these replies (thank you, BTW) seem to be saying that the
> result of performing an intersection on lists containing duplicate
> members is undefined, at least with respect to the number of
> duplicates that may show up in the result. That's a much stronger
> statement than the "may have duplicates" line in the spec.
>
> The spec made a big point about how "nintersection" was destructive to
> one of its inputs, and how that destruction was implementation
> dependent, and provided examples of different results of destruction,
> etc. With that much description of an implementation dependency that
> could have been covered with "the first input to nintersection is
> destroyed", I didn't think "may have duplicates" would imply "the
> number of members in the result is so undefined that even within the
> same implementation the length of X i'sect Y isn't guaranteed to be
> the same as the length of Y i'sect X.
>
> I did understand that intersection (and other set operations) had
> several possible definitions in the presence of duplicates, but I was
> thinking that the Lisp world had probably chosen the one that was most
> useful as a building block for higher abstractions long ago -- like
> defining multiplication of no arguments to equal 1 instead of making
> it implementation dependent.
>
> Of course, Lisp makes it easy for me to define it any way I like and
> implement it in about half a dozen lines of code, so it doesn't matter
> in that respect. I was thinking, though, that I was going to learn how
> I *ought* to define it, mistakenly thinking that all of the Lisp
> builtins, except where explicitly noted, had evolved to very rigidly
> defined algorithms years ago.

Yes, but all of this has no importance if you use this list->set
function:

    (defun list->set (list) (remove-duplicates list))
    (setq p (list->set '(a a b a c a a d)))
    (setq q (list->set '(a a a a a d a d)))
    (intersection p q) --> (d a) ;; or (a d)... 

-- 
__Pascal_Bourguignon__                     http://www.informatimago.com/
There is no worse tyranny than to force a man to pay for what he doesn't
want merely because you think it would be good for him.--Robert Heinlein
http://www.theadvocates.org/