intersection

From: Tuang (tuanglen_at_hotmail.com)
Date: 01/28/04 

Date: 28 Jan 2004 01:14:41 -0800

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

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.

I don't know. Is this just a bug in CLISP, or a misstatement in the
Hyperspec, or some misunderstanding on my part? I've been assuming
that something fundamental like intersection would be implemented
everywhere with the same 5-6 lines of code that have been used since
the dawn of Lisp.

Thoughts?

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)
  • Re: intersection
    ... > Common Lisp. ... > "The intersection operation is described as follows. ... > ordered pairs consisting of one element from list-1 and one element ... "If one of the lists contains duplicate elements, ...
    (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)