Set immutable?
Kyle Schalm
this does seem to be the intent, since there is no method on the object
itself which can be used to change its value. however,
In [58]: x=[1,2,3]
In [59]: s=Set(x)
In [60]: x[1]=5
In [61]: s
Out[61]: {1, 3, 5}
i propose that this is undesirable, and there is an easy fix, assuming
any X for which X.is_finite() == True also has an iterator (and can
therefore be converted to a python set). see patch below.
note: the second part of this patch assumes the patch in my previous email
has been applied. if not, just use the first part of this patch.
# HG changeset patch
# User Kyle Schalm <ksc...@math.utexas.edu>>
# Date 1176453082 18000
# Node ID ce41e74d58b655aa854acba1e08a69fec9534cc6
# Parent bca0cc86fd5e88dc21887c5d222c1fcfa71ae490
guard Set_object_enumerated against accidental change via underlying
object
diff -r bca0cc86fd5e -r ce41e74d58b6 sage/sets/set.py
--- a/sage/sets/set.py Fri Apr 13 03:07:17 2007 -0500
+++ b/sage/sets/set.py Fri Apr 13 03:31:22 2007 -0500
@@ -55,8 +55,8 @@ def Set(X):
if isinstance(X, Element):
raise TypeError, "Element has no defined underlying set"
try:
- if isinstance(X, (list, tuple, set)) or X.is_finite():
- return Set_object_enumerated(X)
+ if isinstance(X, (list, tuple, set, frozenset)) or X.is_finite():
+ return Set_object_enumerated(frozenset(X))
except AttributeError:
pass
return Set_object(X)
@@ -527,11 +527,7 @@ class Set_object_enumerated(Set_object):
sage: type(X)
<class 'sage.sets.set.Set_object_enumerated'>
"""
- try:
- return self.__set
- except AttributeError:
- self.__set = frozenset(self.object())
- return self.__set
+ return self.object()
def __hash__(self):
return hash(self.set())
William Stein
> while i'm on the topic of sets, is the Set class intended to be immutable?
No. The builtin Python set type isn't immutable, so it doesn't
seem sensible to make the SAGE one immutable. E.g., the
builtin set type has an add method:
> sage: a = set([1,2,3])
> sage: a.add(10)
> sage: a
> set([1, 2, 3, 10])
Since sets aren't immutable, they aren't hashable:
> sage: hash(a)
>> <type 'exceptions.TypeError'>: set objects are unhashable
Sets in SAGE should have very similar behavior to Python sets,
except "be more mathematical", and of course allow for infinite
sets. Thus actually, regarding your previous patch, sets shouldn't
be allowed as dictionary keys and shouldn't have a hash method
at all, or have one that raises type error. If you want to use one
as a key, you should maybe be using a tuple instead.
In short -- SAGE sets should be like Python sets, unless there is
a very very good argument otherwise, and Python sets
are mutable and not hashable.
I would not be opposed to creating an immutability flag
for sets, and having a "set_immutable" option (like with
Sequences), to create immutable sets. But those shouldn't
be the default.
--
William Stein
Associate Professor of Mathematics
University of Washington
http://www.williamstein.org
Kyle Schalm
>> while i'm on the topic of sets, is the Set class intended to be immutable?
>
> No. The builtin Python set type isn't immutable, so it doesn't
> seem sensible to make the SAGE one immutable. E.g., the
> builtin set type has an add method:
ok, but there is no add method in the SAGE Set, nor is there a remove
method. so as it stand right now, it isn't very similar to a python set.
> Sets in SAGE should have very similar behavior to Python sets,
> except "be more mathematical", and of course allow for infinite
> sets. Thus actually, regarding your previous patch, sets shouldn't
> be allowed as dictionary keys and shouldn't have a hash method
> at all, or have one that raises type error. If you want to use one
> as a key, you should maybe be using a tuple instead.
if Sets aren't going to be usable as dictionary keys, then i'm going to
create a new immutable set class that can, because i really need that.
tuples won't cut it.
> I would not be opposed to creating an immutability flag
> for sets, and having a "set_immutable" option (like with
> Sequences), to create immutable sets. But those shouldn't
> be the default.
you mean something like
s = Set([1,2,3],immutable=True)
? that would work for me. in any case, i think the following behaviour
>>
>> In [58]: x=[1,2,3]
>>
>> In [59]: s=Set(x)
>>
>> In [60]: x[1]=5
>>
>> In [61]: s
>> Out[61]: {1, 3, 5}
is still highly undesirable.
shall i go ahead and add the immutable option, and some add and remove
methods?
-kyle
William Stein
> >
> > No. The builtin Python set type isn't immutable, so it doesn't
> > seem sensible to make the SAGE one immutable. E.g., the
> > builtin set type has an add method:
>
> ok, but there is no add method in the SAGE Set, nor is there a remove
> method. so as it stand right now, it isn't very similar to a python set.
There should be a remove and add method. I forgot to implement them.
> > Sets in SAGE should have very similar behavior to Python sets,
> > except "be more mathematical", and of course allow for infinite
> > sets. Thus actually, regarding your previous patch, sets shouldn't
> > be allowed as dictionary keys and shouldn't have a hash method
> > at all, or have one that raises type error. If you want to use one
> > as a key, you should maybe be using a tuple instead.
>
> if Sets aren't going to be usable as dictionary keys, then i'm going to
> create a new immutable set class that can, because i really need that.
> tuples won't cut it.
I totally understand. Immutable types are really useful in practice.
> > I would not be opposed to creating an immutability flag
> > for sets, and having a "set_immutable" option (like with
> > Sequences), to create immutable sets. But those shouldn't
> > be the default.
>
> you mean something like
>
> s = Set([1,2,3],immutable=True)
>
> ? that would work for me.
Yes, exactly. Also,
s = Set([1,2,3])
then
s.set_immutable()
Definitely look at the Sequence code in structure/sequence.py
before implementing the above though.
> in any case, i think the following behaviour
>
> >>
> >> In [58]: x=[1,2,3]
> >>
> >> In [59]: s=Set(x)
> >>
> >> In [60]: x[1]=5
> >>
> >> In [61]: s
> >> Out[61]: {1, 3, 5}
>
>
> is still highly undesirable.
I agree. Removing setitem, as I think you did, is a good
idea. The python builtin set doesn't have it.
> shall i go ahead and add the immutable option, and some add and remove
> methods?
Yes. Thanks!
William
William Stein
>
> >> you mean something like
> >>
> >> s = Set([1,2,3],immutable=True)
> >>
> >> ? that would work for me.
> >
> > Yes, exactly. Also,
> > s = Set([1,2,3])
> > then
> > s.set_immutable()
>
You create a set by doing lots of operations on it, so it has to be mutable.
Then you record the set as an attribute of a class. Then you have a method
to return that set -- you don't want the code that calls the method to be
able to change the set. E.g., maybe your set is the primes of bad
reduction for an elliptic curve, which you compute as you go. Then
you do self.__bad_primes = that set. If you return self.__bad_primes,
and don't make it immutable, then users could mess with that set.
This is a very common sort of situation in mathematical algorithms.
> i don't have a problem with it, just wondering. this only goes one way, i
> hope -- that is, it won't be allowed to change back from immutable to
> mutable, right? (that would be bad IMHO.)
Yes. There is no way to make something immutable back to being mutable,
beyond sneaky __ methods.
> > I agree. Removing setitem, as I think you did, is a good
> > idea. The python builtin set doesn't have it.
>
> i didn't -- it was already gone (or never there).
> however, something like
>
> s.replace(a,b)
>
> which is equivalent to
>
> s.remove(a)
> s.add(b)
>
> might make sense -- i don't want to add features no one needs; what do
> you think?
Don't add features nobody needs or request.
> while i'm at it, what about these additional methods, which exist in
> python sets? they look useful:
>
> s.issubset(t) s <= t test whether every element in s is in t
> s.issuperset(t) s >= t test whether every element in t is in s
>
> s.update(t) s |= t update set s, adding elements from t
> s.intersection_update(t) s &= t update set s, keeping only elements found in both s and t
> s.difference_update(t) s -= t update set s, removing elements found in t
> s.symmetric_difference_update(t) s ^= t update set s, keeping only elements found in either s or t but not in both
>
> although my preference would be change the name of update to union_update.
Sure, add them. You're right -- union_update is a good choice of name.
> also, what about:
>
> * making + and += synonyms for | and |= ?
> * a "powerset" method?
Sounds good if the precedence is correct.
William
Nick Alexander
at some length. A little google-fu might be in order to address the
issues they had with mutable sets and the language.
Nick
William Stein
Good point. See the docs here:
http://docs.python.org/lib/types-set.html
In particular, we should probably use the frozenset type to implement
immutable sets.
That said, I totally disagree with carrying their design over to SAGE, i.e.,
having mutable and immutable versions be different types -- having mutability
be a property is better. For matrices having separate types would
lead to a maintenance and
implementation nightmare, and the same probably goes for sets, since
in SAGE there
are many many different types of sets, and will likely be many many more.
>
> Nick