Re: Proposal: s1.intersects(s2)

[David Abrahams]

on Thu Jul 05 2007, Christoph Zwerschke  wrote:

> Steven D'Aprano wrote:
>> 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.

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

-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Proposal: s1.intersects(s2)

[Christoph Zwerschke]

Steven D'Aprano wrote:
> 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
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Proposal: s1.intersects(s2)

[Christoph Zwerschke]

Nis Jørgensen wrote:
> The problem is, these functions can be read as "X is [consisting only
> of] digit[s]", "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
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Proposal: s1.intersects(s2)

[OKB (not okblacke)]

Steven D'Aprano wrote:

> 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
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Proposal: s1.intersects(s2)

[Steven D'Aprano]

On Thu, 05 Jul 2007 01:48:58 +, richyjsm wrote:

> On Jul 4, 8:14 pm, Steven D'Aprano
> <[EMAIL PROTECTED]> wrote:
>> 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.

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%3Aintersect


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



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

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 all intersecting sets are subsets, but all subsets are
>> intersecting sets.)
> 
> 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.


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

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


-- 
Steven.

-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Proposal: s1.intersects(s2)

[Steven D'Aprano]

On Thu, 05 Jul 2007 07:34:28 -0700, Aahz wrote:

> In article <[EMAIL PROTECTED]>,
> Steven D'Aprano  <[EMAIL PROTECTED]> wrote:
>>
>>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.  

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.

-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Proposal: s1.intersects(s2)

[Aahz]

In article <[EMAIL PROTECTED]>,
Steven D'Aprano  <[EMAIL PROTECTED]> wrote:
>
>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.
-- 
Aahz ([EMAIL PROTECTED])   <*> http://www.pythoncraft.com/

I support the RKAB
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Proposal: s1.intersects(s2)

[Nis Jørgensen]

Steven D'Aprano skrev:
> On Wed, 04 Jul 2007 23:53:15 -0400, David Abrahams wrote:
> 
>> on Wed Jul 04 2007, "Steven D'Aprano" 
>>  wrote:
>>
>>> On Wed, 04 Jul 2007 14:37:34 +, 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()" 
>> 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.

The problem is, these functions can be read as "X is [consisting only
of] digit[s]", "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
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Proposal: s1.intersects(s2)

[David Abrahams]

on Wed Jul 04 2007, "Steven D'Aprano"  
wrote:

> On Wed, 04 Jul 2007 14:37:34 +, 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()" 

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

-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Proposal: s1.intersects(s2)

[richyjsm]

On Jul 4, 8:14 pm, Steven D'Aprano
<[EMAIL PROTECTED]> wrote:
> 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

-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Proposal: s1.intersects(s2)

[Erik Max Francis]

Steven D'Aprano wrote:

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

-- 
Erik Max Francis && [EMAIL PROTECTED] && http://www.alcyone.com/max/
  San Jose, CA, USA && 37 20 N 121 53 W && AIM, Y!M erikmaxfrancis
   Perfect girl / She was never me
-- Lamya
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Proposal: s1.intersects(s2)

[Steven D'Aprano]

On Wed, 04 Jul 2007 14:37:34 +, 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.

-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Proposal: s1.intersects(s2)

[Marc 'BlackJack' Rintsch]

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)

Ciao,
Marc 'BlackJack' Rintsch
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Proposal: s1.intersects(s2)

[Marc 'BlackJack' Rintsch]

On Wed, 04 Jul 2007 16:18:58 +0200, Thomas Jollans wrote:

> On Wednesday 04 July 2007, David Abrahams wrote:
>> 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.
> 
 s1 = set(xrange(5))
 s2 = set(xrange(3,9))
 s1
> set([0, 1, 2, 3, 4])
 s2
> set([3, 4, 5, 6, 7, 8])
 s1 | s2
> set([0, 1, 2, 3, 4, 5, 6, 7, 8])
 s1 & s2
> set([3, 4])

> 
> It's all in python already. And documented on the web too.

The OP already knows that but does not want to build a new `set`.  He just
wants to know efficiently if the sets intersect without actually *doing*
the intersection.

Ciao,
Marc 'BlackJack' Rintsch
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Proposal: s1.intersects(s2)

[Thomas Jollans]

On Wednesday 04 July 2007, 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
>
> 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.

>>> s1 = set(xrange(5))
>>> s2 = set(xrange(3,9))
>>> s1
set([0, 1, 2, 3, 4])
>>> s2
set([3, 4, 5, 6, 7, 8])
>>> s1 | s2
set([0, 1, 2, 3, 4, 5, 6, 7, 8])
>>> s1 & s2
set([3, 4])
>>>

It's all in python already. And documented on the web too.

-- 
  Regards,   Thomas Jollans
GPG key: 0xF421434B may be found on various keyservers, eg pgp.mit.edu
Hacker key :
v4sw6+8Yhw4/5ln3pr5Ock2ma2u7Lw2Nl7Di2e2t3/4TMb6HOPTen5/6g5OPa1XsMr9p-7/-6


signature.asc
Description: This is a digitally signed message part.
-- 
http://mail.python.org/mailman/listinfo/python-list

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

-- 
http://mail.python.org/mailman/listinfo/python-list