Proposal: s1.intersects(s2)

[David Abrahams]

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

Right now, the only convenient thing to do is

if s1 & s2 ...

but that builds a whole new set. IMO that query should be available
as a method of set itself.

--
Dave Abrahams
Boost Consulting
http://www.boost-consulting.com

The Astoria Seminar ==> http://www.astoriaseminar.com

 

[Marc 'BlackJack' Rintsch]

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)

Ciao,
Marc 'BlackJack' Rintsch

 

[Steven D'Aprano]

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.

 

[Erik Max Francis]

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:

Well, sure. If you're dealing with empty sets, then you should know
what you're getting yourself into if you're asking about set
intersections. If you don't, then an .intersects method isn't going to
help you out of your conundrum of not understanding how the null set
relates to intersections.

 

[richyjsm]

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.

Poppycock! It's perfectly well defined: two sets intersect if and
only if their intersection is nonempty. There's absolutely no reason
to single out the empty set for special treatment in this definition.

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.

Well of course false statements are going to cause problems.

(Not all intersecting sets are subsets, but all subsets are intersecting sets.)

Not true.

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.

Nope. There's one, obvious, correct definition, as given above. No
need to mention the empty set at all.

Richard

 

[David Abrahams]

I'd rather see sets gain an method "isintersect()"

And why is that a good name? It's not even grammatical.

with the functionality than the language to gain a built-in
function.

How is a method on sets not a built-in function? Anyway, such a
method is what I'm proposing.

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.

Depends how you define it. I define it as "has a non-empty
intersection," which is pretty obviously solid. The semantics should
be identical to

len(s1&s2) > 0

Those are exactly the semantics I want, and if mathematical purists
are going to argue that "intersects" is the wrong name, I ask that
they come up with a better one.

--
Dave Abrahams
Boost Consulting
http://www.boost-consulting.com

The Astoria Seminar ==> http://www.astoriaseminar.com

 

[Steven D'Aprano]

And why is that a good name? It's not even grammatical.

Neither is "It's not even grammatical", but all but purists use it
regardless.

A common Python convention is to have test functions named something
like "isfoo", e.g. str.isdigit(), isspace(), islower() etc. They're not
exactly grammatical either, e.g. isdigit() should actually be "contains
one or more digits, and nothing but digits". (Presumably the pedantically
correct name was rejected as being too long.) I was just following that
convention.

My main feeling is that any such function should be a set method rather
than a built-in function like len(). The name change was comparatively
unimportant.

How is a method on sets not a built-in function? Anyway, such a
method is what I'm proposing.

Although they are similar, methods are not identical to functions, even
if many of us, myself included, often use the terms interchangeably.

len() is a built-in function. str.lower() is a method of strings. I'd
prefer to see intersects() be a method of sets than a built-in function,
and I think you'd have a much better chance of getting it approved as a
method than as a function, but I could be wrong.

Depends how you define it.

Exactly my point.

I define it as "has a non-empty intersection," which is pretty obviously
solid.

I didn't say it was a bad choice, only that it isn't the only choice.

 

[=?ISO-8859-1?Q?Nis_J=F8rgensen?=]

Steven D'Aprano skrev:

Neither is "It's not even grammatical", but all but purists use it
regardless.

A common Python convention is to have test functions named something
like "isfoo", e.g. str.isdigit(), isspace(), islower() etc. They're not
exactly grammatical either, e.g. isdigit() should actually be "contains
one or more digits, and nothing but digits". (Presumably the pedantically
correct name was rejected as being too long.) I was just following that
convention.

The problem is, these functions can be read as "X is [consisting only
of] digit", "X is lower [case]" etc, where the bits in brackets have
been removed for brewity. In the case of "s1 is intersect s2" there is
no way I can see of adding words to get a correct sentence. The
"obvious" naming is "s1.intersects(s2)" which reads as "s1 intersects
s2", a perfectly cromulent sentence.

Nis

 

[Aahz]

My main feeling is that any such function should be a set method rather
than a built-in function like len(). The name change was comparatively
unimportant.

Look up at the Subject: line. There never was any suggestion that
intersects() be anything other than a set method.

 

[Steven D'Aprano]

Look up at the Subject: line.

Subject line? What's that?

*chagrined wink*

There never was any suggestion that
intersects() be anything other than a set method.

My fault for replying to a reply instead of the original post.

 

[Steven D'Aprano]

Poppycock! It's perfectly well defined: two sets intersect if and
only if their intersection is nonempty.

That's certainly _a_ definition.

I'm not a professional set theorist, but in 15-odd years of studying and
teaching maths I've never come across mathematicians using intersect as a
verb except as informal short-hand. I often say "North Street and South
Street don't intersect", but "the intersection of sets A and B is empty".

Just because I've never come across it doesn't mean it exists, so I'd be
grateful for any reference to a technical definition, or even references
to any mathematician using intersect as a verb in a vigorous,
non-hand-waving way. Here's a link to get you started:

http://www.google.com.au/search?q=define:intersect

There's absolutely no reason
to single out the empty set for special treatment in this definition.

But you can't avoid treating the empty set as special, because it _is_
special. You can only choose where to do so. For instance, do sets
intersect with themselves?

By my rule, every set intersects with itself, no exceptions.

By your rule, every set intersects with itself, except for the empty set.

Well of course false statements are going to cause problems.

My statement is only false if we treat the empty set as special, which
you've said we shouldn't do.

By my rule: if A <= B, then A and B intersect, no exceptions.

By your rule: if A <= B and A is not the empty set, then A and B intersect.

Not true.

Can you give a counter-example, without treating the empty set as special?

Of course if you exclude the empty set by definition, my statement is no
longer true -- but that's begging the question of whether we should
exclude the empty set or not.

Nope. There's one, obvious, correct definition, as given above. No
need to mention the empty set at all.

It is obvious, but whether it is correct or not depends on how you decide
whether two things intersect or not.

 

[OKB (not okblacke)]

Just because I've never come across it doesn't mean it exists, so
I'd be grateful for any reference to a technical definition, or
even references to any mathematician using intersect as a verb in a
vigorous, non-hand-waving way. Here's a link to get you started:

Here ( http://arxiv.org/PS_cache/math/pdf/0702/0702029v1.pdf )is a
Russian math text (in English) which says:

"If A \cap B 6 = \emptyset, then we say that the sets A and B do
intersect. Otherwise, if A \cap B = \emptyset, then we say that these
sets do not intersect."

Here (
http://www.tcs.ifi.lmu.de/~fischerf/publications/bfh_tark07.pdf ) is a
math paper which says:

"Sets that are disjoint in the diagram may have an empty
intersection, i.e., there exist instances where these sets do not
intersect."

A simple Google search will also turn up numerous uses of the
phrase "non-intersecting sets", which would seem to be parallel (i.e.,
people are not bending over backwards to say "disjoint sets" or "sets
with empty intersection").

--
--OKB (not okblacke)
Brendan Barnwell
"Do not follow where the path may lead. Go, instead, where there is
no path, and leave a trail."
--author unknown

 

[Christoph Zwerschke]

The problem is, these functions can be read as "X is [consisting only
of] digit", "X is lower [case]" etc, where the bits in brackets have
been removed for brewity. In the case of "s1 is intersect s2" there is
no way I can see of adding words to get a correct sentence. The
"obvious" naming is "s1.intersects(s2)" which reads as "s1 intersects
s2", a perfectly cromulent sentence.

Agree. A possible alternative would be "s1.hasintersection(s2)", but
s1.intersects(s2) is ok as well.

-- Chris

 

[Christoph Zwerschke]

I'm not a professional set theorist, but in 15-odd years of studying and
teaching maths I've never come across mathematicians using intersect as a
verb except as informal short-hand. I often say "North Street and South
Street don't intersect", but "the intersection of sets A and B is empty".

I think mathematicians use more often the inverse predicate, namely
"disjoint", which is well defined as having an empty intersection.

-- Chris

 

[David Abrahams]

I think mathematicians use more often the inverse predicate, namely
"disjoint", which is well defined as having an empty intersection.

Doesn't read so well as a method, though. You end up with
"a.is_disjoint_with(b)."

--
Dave Abrahams
Boost Consulting
http://www.boost-consulting.com

The Astoria Seminar ==> http://www.astoriaseminar.com