Proposal: s1.intersects(s2)

[Steven D'Aprano]

On Wed, 04 Jul 2007 14:37:34 +0000, Marc 'BlackJack' Rintsch wrote:

> On Wed, 04 Jul 2007 09:59:24 -0400, David Abrahams wrote:
> 
>> Here's an implementation of the functionality I propose, as a
>> free-standing function:
>> 
>>         def intersects(s1,s2):
>>             if len(s1) < len(s2):
>>                 for x in s1:
>>                     if x in s2: return True
>>             else:
>>                 for x in s2:
>>                     if x in s1 return True
>>             return False
> 
> In Python 2.5 this can be written a bit more concise:
> 
> def intersects(set_a, set_b):
>     if len(set_a) < len(set_b):
>         set_a, set_b = set_b, set_a
>     return any(item in set_a for item in set_b)


I'd rather see sets gain an method "isintersect()" with the functionality
than the language to gain a built-in function.

However, there's a very subtle flaw in the idea. While "the intersection"
of two sets is well-defined, "these two sets intersect" is (surprisingly!)
_not_ well-defined. If you only consider non-empty sets, you won't have a
problem: two non-empty sets intersect if their intersection is not empty,
and both implementations of intersects() given will do the right thing.

The problem comes if we (perhaps naively) try to say that if a set A is a
subset of set B, set A must intersect with B. (Not all intersecting sets
are subsets, but all subsets are intersecting sets.) Unfortunately that is
not the same as asking if the intersection between two sets is not empty:

>>> A = set()
>>> B = set([12, 21])
>>> A.issubset(B)
True
>>> B.issuperset(A)
True
>>> intersects(A, B) # both implementations do the same
False
>>> intersects(A, A) # does A intersect with itself?
False


PLEASE don't anybody try to argue that Python's behaviour here is "a bug"
-- the meaning of subset and superset with the empty set is
well-established and completely uncontroversial amongst mathematicians.
(It is what they call a vacuous truth.)

Rather than discuss the issues in detail, I'll just point those who care
to Wikipedia:

http://en.wikipedia.org/wiki/Empty_set#Common_problems

and point out that the behaviour of any() and all() can sometimes be
unintuitive or contradictory for the same reason.

As a result, any proposed function or method that returns a True/False
value for whether set A intersects with set B needs to define (and
justify) what it means to say that two sets intersect when one or both are
the empty set.



-- 
Steven.