Re: intersection
From: Marco Antoniotti (marcoxa_at_cs.nyu.edu)
Date: 01/28/04
- Next message: Kaz Kylheku: "Re: intersection"
- Previous message: George Hester: "Re: ... Don't try this; $$$$$ Want Money?? Let me tell you how AND IT WORKS!!! $$$$$"
- In reply to: Tuang: "intersection"
- Next in thread: Kaz Kylheku: "Re: intersection"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Wed, 28 Jan 2004 12:10:47 -0500
Tuang wrote:
> 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?
That depends on your definition of set intersection and set equality.
If you do not consider multiplicity of elements, basic set theory says that
{A, A, A} = {A}
hence CLisp (and Common Lisp) are right in returning what they return.
Of course you may have problems if you want to do
(equal '(A A A) '(A A))
but then, nobody ensured that EQUAL implements set equality as intended
in basic set theory. To do that, you are better off with
(defun set-equal (s1 s2)
(and (subsetp s1 s2) (subsetp s2 s1)))
Of course, you can add all the &key you need etc etc...
Note also that
(union '(a) '(a a c))
yields different results on different CL implementations. But then
again the basi set semantics is correct and SET-EQUAL will work as
expected. It is the LIST interpretation of sets that yields incorrect
results.
The use of lists as sets is a simple and nice and quick and dirty way to
do set-theory in CL. It is not necessarily the right way, especially
when sets become large. In that case you are better off writing your
own set manipulation library.
Cheers
-- Marco
- Next message: Kaz Kylheku: "Re: intersection"
- Previous message: George Hester: "Re: ... Don't try this; $$$$$ Want Money?? Let me tell you how AND IT WORKS!!! $$$$$"
- In reply to: Tuang: "intersection"
- Next in thread: Kaz Kylheku: "Re: intersection"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
