Re: intersection

From: Marco Gidde (marco.gidde_at_tiscali.de)
Date: 01/28/04 

Date: 28 Jan 2004 11:28:15 +0100

tuanglen@hotmail.com (Tuang) writes:

> I'm a bit confused about how "intersection" is supposed to work in
> Common Lisp.
>
> The Hyperspec says the following about intersection:
>
> "The intersection operation is described as follows. For all possible
> ordered pairs consisting of one element from list-1 and one element
> from list-2, :test or :test-not are used to determine whether they
> satisfy the test [of equality]....For every pair that satifies the
> test, exactly one of the two elements of the pair will be put in the
> result."

It also says:

"If one of the lists contains duplicate elements, there may be
duplication in the result."

> That tells me that if you have 3 A's in one list and 2 A's in the
> other, you'll have six possible ordered pairs containing one A from
> each list. Taking one from each pair, it sounds as though there should
> be six A's in the result. Of course you could remove a pair, after
> adding one A to the result, as soon as you get a match, but then you
> wouldn't be considering "all possible ordered pairs".
>
> Trying it out with CLISP (on Win32) to help myself understand it, I
> get the following:
>
> > (intersection '(A A A D E) '(A A B C))
> (A A A)
> > (intersection '(A A B C) '(A A A D E))
> (A A)
>
> Well, now I'm even more confused. At the very least, it would seem to
> me that (intersection X Y) ought to be the same as (intersection Y X),
> though potentially in a different order.
>
> I think that the second is what I would normally consider
> intersection, which is sharing an element in common in a venn diagram.
> If set X contains 2 A's and set Y contains 3 A's, then drawing the
> intersecting circles, you could put two A's in the shared (overlapped)
> part with one more A in Y but outside the shared part. The
> intersection would be those items in the shared region, meaning 2 A's
> in the intersection.

You assume the A's are different, while in fact they are
equal. 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)

Relevant Pages

  • Re: intersection
    ... > The Hyperspec says the following about intersection: ... > "The intersection operation is described as follows. ... > ordered pairs consisting of one element from list-1 and one element ... hence CLisp (and Common Lisp) are right in returning what they return. ...
    (comp.lang.lisp)
  • intersection
    ... Common Lisp. ... The Hyperspec says the following about intersection: ... ordered pairs consisting of one element from list-1 and one element ...
    (comp.lang.lisp)
  • Re: ordered pairs/n-tuples as collections of sets
    ... Is there a way to express T_1 and T_2, the first and second elements of the tuple in terms of standard operations on sets like intersection and union and such instead of the gibberish found on http://en.wikipedia.org/wiki/Ordered_pair? ... one of these must be a doubleton whereof the singleton is a subset. ... You can't do that immediately for ordered pairs, since the definition of function uses ordered pairs itself. ...
    (sci.math)