Re: intersection

From: Kaz Kylheku (kaz_at_ashi.footprints.net)
Date: 01/29/04 

Date: 28 Jan 2004 17:07:06 -0800

tuanglen@hotmail.com (Tuang) wrote in message news:<df045d93.0401281153.11b0c115@posting.google.com>...
> 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.

No, it isn't. ``Undefined with respect to the number of duplicates''
means exactly the same thing as ``may have duplicates'', which means
exactly the same thing as ``The number of duplicates can be any
non-negative integer''.

> 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.

There is a mathematical basis for this, because exponentiation to the
power of zero is 1.

  (= (expt 42 3) (* 42 42 42))
  (= (expt 42 2) (* 42 42))
  (= (expt 42 1) (* 42))
  (= (expt 42 0) (*))

Similar reasoning allows a zero-dimensional array A have a single
element that is specified by no subscripts whatsoever. The size of an
array is a product of all the dimensions. The product of dimensions in
this case, since there aren't any, is (*), so the size is 1. Thus
there is a single cell in the array and is named by the place (AREF
A).

> 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.

No algorithm for INTERSECTION that can be called ``evolved'' would
support the preservation of duplicates, regardless of the order of the
parameters. It would be inefficient compared to algorithms that don't
care about preserving duplicates.

Requiring implementations to do inefficient things to support
braindamaged inputs is rarely a good idea, unless there is evidence of
a significant body of existing code which relies on it.

The semantics of INTERSECTION are very rigid when you give it lists
that behave like sets, and therefore have no duplicates. Feed no
duplicates, get no duplicates.

Lastly, consider that it's *impossible* to require INTERSECTION to
support duplicates from both sets, commutatively, without
simultaneously requiring it to *generate* spurious duplicates when
neither list has duplicates.

If you compute

  (intersection '("A") '("A") :test #equal)

you must get the list

  '("A")

So in other words, one of the two "A" objects, which are not
necessarily the same object, has to be rejected so that duplicates are
not generated in the output.

You could require INTERSECTION to always favor the left side when
choosing what to reject, but then it would no longer satsify your
expectation of commutativity. You would end up with some ridiculous,
contorted definition like:

   ``Keep all the elements from the right list (all duplicates )
     that appear one or more times in the left list. Additionally, for
     all such elements, keep any duplicates from the left list.''
     ----
     * So that if there is just one occurence of a matched item in the
       left list, then it does not appear in the output. If the item
       is duplicated twice, then just the second occurence appears in
       the resulting list, and so on.

Ugh.

Relevant Pages

  • Re: intersection
    ... | statement than the "may have duplicates" line in the spec. ... meaning in your personal universe and to spend your energy on proving ... | I didn't think "may have duplicates" would imply "the number of members ... The obvious implementation of INTERSECTION is the trivial ...
    (comp.lang.lisp)
  • Re: Managing a data list and removing duplicates
    ... if you did want to restrict the mailing to one letter per ... >be doing on a regular basis with new lists of varying types. ... Removing most of the duplicates will save a fortune on the ... >> members of the same family. ...
    (microsoft.public.access.modulesdaovba)
  • Re: intersection
    ... > If one of the lists contains duplicate elements, ... > intersection of two sets A and B is the the set of all x, ... statement than the "may have duplicates" line in the spec. ... With that much description of an implementation dependency that ...
    (comp.lang.lisp)
  • Re: intersection
    ... ``If one of the lists contains duplicate elements, ... INTERSECTION, don't count on it to normalize the results to a proper ... set-like sequence with no duplicates, but also don't count on it to ... items are in the first set. ...
    (comp.lang.lisp)
  • Re: removing dupliates from 2 lists with similar content
    ... In XL2007 there is a feature to Remove Duplicates under the Data tab. ... sheet that others can just drop their lists into? ... Each contains unique entries, as well as ...
    (microsoft.public.excel.newusers)