containment in a set different from containment in a set - help needed

[Martin R]

I need help with https://trac.sagemath.org/ticket/34817

Essentially, I have a list P and an object g such that g in P but g not in set(P).

How could this happen?

[Martin R]

a hashing problem, maybe?

[Dima Pasechnik]

On Fri, Dec 2, 2022 at 2:44 PM 'Martin R' via sage-devel
<sage-...@googlegroups.com> wrote:
>
> a hashing problem, maybe?

to me, is't a problem of different "types" (.parent(), to be precise.
See my reply on the ticket)

> --
> You received this message because you are subscribed to the Google Groups "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/3740834b-7ff2-478c-9ce5-0b33b439b157n%40googlegroups.com.

[Martin R]

OK, thank you, but is this really intentional?  I would have thought that x in P and  x in set(P) should give the same result.

[Dima Pasechnik]

On Fri, Dec 2, 2022 at 5:05 PM 'Martin R' via sage-devel
<sage-...@googlegroups.com> wrote:
>
> OK, thank you, but is this really intentional? I would have thought that x in P and x in set(P) should give the same result.

I guess that hashing is done using a .parent()...

>
> On Friday, 2 December 2022 at 16:57:50 UTC+1 dim...@gmail.com wrote:
>>
>> On Fri, Dec 2, 2022 at 2:44 PM 'Martin R' via sage-devel
>> <sage-...@googlegroups.com> wrote:
>> >
>> > a hashing problem, maybe?
>>
>> to me, is't a problem of different "types" (.parent(), to be precise.
>> See my reply on the ticket)
>>
>> >
>> > On Friday, 2 December 2022 at 15:43:33 UTC+1 Martin R wrote:
>> >>
>> >> I need help with https://trac.sagemath.org/ticket/34817
>> >>
>> >> Essentially, I have a list P and an object g such that g in P but g not in set(P).
>> >>
>> >> How could this happen?
>> >
>> > --
>> > You received this message because you are subscribed to the Google Groups "sage-devel" group.
>> > To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
>> > To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/3740834b-7ff2-478c-9ce5-0b33b439b157n%40googlegroups.com.
>
> --
> You received this message because you are subscribed to the Google Groups "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.

> To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/566e74d7-638e-4baa-8f25-919bb20bb7e7n%40googlegroups.com.

[Dima Pasechnik]

in fact, you can see that

sP=set(P)
sP.add(g)
len([t for t in sP])==len(P)+1

gets you True...

[Dima Pasechnik]

but you can use Set() (a Sage's class for sets), which is much more sane here:

sage: f in Set(P)
True
sage: g in Set(P)
True

[Martin R]

Hi Dima!

Thank you for your replies!  I understand the technicalities, but my main question is: do we really want that?

I should add that it took me a long while to figure out what's happening, because in my application I computed orbits under an action, and I observed that the orbit sizes were wrong.  Through tracing, I figured that `orbit_decomposition` is using sets (which is OK, of course), and that containment in sets is different than containment in lists.

Note that this does not happen for DyckWords or Permutations.

I think - should we decide that we do not want this - we could try to add a test to the category framework.  Is there already some structure in place to get from the class in infinite enumerated sets to the subclass in finite enumerated sets?

Martin

[Nils Bruin]

On Saturday, 3 December 2022 at 06:41:30 UTC-8 axio...@yahoo.de wrote:

Note that this does not happen for DyckWords or Permutations.

I think - should we decide that we do not want this - we could try to add a test to the category framework.  Is there already some structure in place to get from the class in infinite enumerated sets to the subclass in finite enumerated sets?

This is really the usual thing about hashes and equality: for sets to behave consistently, one needs that elements that test equal have identical hashes. If you allow equality through coercion, this quickly becomes impossible. In fact, transitivity of equality is already difficult: GF(3)(4) == ZZ(4) and ZZ(4) == GF(5)(4).

For this particular one, where parking functions of specific length are completely described as subsets of parking functions, it seems like equality should not be a problem, so the hash should probably not taking into account the "length" in the parent.

[Martin R]

I actually don't see how to do this, because ParkingFunction inherits the implementation of _hash_ from ClonableArray, just the same as, for example DecoratedPermutation, where the problem does not occur.

Any ideas?

[Nils Bruin]

It looks like just overriding `_hash_` should do the trick. It's a "cpdef" method so the code should be there to check if it's overridden on a descendant class instance. There will be a performance degradation, although it will be mild because the hash is cached. If that's a problem, you can cythonize ParkingFunction and override the whole equality and "__hash__" infrastructure on the class. If that's too much work it's an indication that perhaps it's not such a big problem :-)

The workaround is to just not use the specialized "ParkingFunctions of fixed length" parents, so that all the parking functions you use have the same (generic) parent. Or only use specific parents, depending on what is more suitable for your code. More generally "sets with elements from mixed parents" are not really supported or at least buggy; because of the fundamental problem with transitivity of equality (and the interactions with hash).

While for parking functions this may be relatively solvable, you should consider the problem you're running into a code smell. Defensive coding practices in sagemath would avoid these constructions in the first place. It's not really ideal to have undocumented or unenforced recommended practices, but in this case it's a consequence of the requirement in sagemath to stretch equality notation to something that globally is no longer transitive, together with sets that don't know about parents or coercion. A mitigating workaround would be a set that is aware of the parent of its elements. Then testing membership can coerce the candidate into the appropriate parent (if that fails, it can't possibly be in the set) and then hashes only need to be consistent with equality within the parent. If that's not the case, you tend to really have a bug, rather than just an inconvenient instance of inconsistencies that are bound to exist.

[Martin R]

I accidentally opened a new ticket https://trac.sagemath.org/ticket/34824, which is essentially ready for review.  There is another problem, which I do not understand, which may be dealt with in the same ticket, if it is easy:

sage: P = ParkingFunctions(4)
sage: B = P([1, 2, 3, 4, 5, 6])
sage: B.parent()
Parking functions of size 4

sage: B in P
False

[Nils Bruin]

On Sunday, 4 December 2022 at 23:15:35 UTC-8 axio...@yahoo.de wrote:

I accidentally opened a new ticket https://trac.sagemath.org/ticket/34824, which is essentially ready for review.  There is another problem, which I do not understand, which may be dealt with in the same ticket, if it is easy:

sage: P = ParkingFunctions(4)
sage: B = P([1, 2, 3, 4, 5, 6])
sage: B.parent()
Parking functions of size 4

sage: B in P
False

I think P.__contains__ contains the answer to that one:

sage: len(B) == P.n
False

I suppose B shouldn't be allowed to have P as a parent anyway? This just looks like shoddy programming -- it looks like you should give ParkingFunctions a thorough review before trusting what they produce, and ideally fix the issues you find for the benefit of people who come after you.

[Jan Groenewald]

Hi

Note sage 9.2 (debian package) gives an error (sage 9.7 does not):

0 jan@jan-desktop:~$sage
┌────────────────────────────────────────────────────────────────────┐
│ SageMath version 9.2, Release Date: 2020-10-24                     │
│ Using Python 3.9.2. Type "help()" for help.                        │
└────────────────────────────────────────────────────────────────────┘
sage: P = ParkingFunctions(4)
....: B = P([1, 2, 3, 4, 5, 6])
....:
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-1-7be5289b850e> in <module>
      1 P = ParkingFunctions(Integer(4))
----> 2 B = P([Integer(1), Integer(2), Integer(3), Integer(4), Integer(5), Integer(6)])

/usr/lib/python3/dist-packages/sage/combinat/combinat.py in __call__(self, x)
   1737             return self._element_constructor_(x)
   1738         else:
-> 1739             raise ValueError("%s not in %s" % (x, self))
   1740
   1741     Element = CombinatorialObject # mostly for backward compatibility

ValueError: [1, 2, 3, 4, 5, 6] not in Parking functions of size 4
sage:

Regards,

Jan

--

  .~.
  /V\     Jan Groenewald
 /( )\    www.aims.ac.za
 ^^-^^ 

[Nils Bruin]

On Sunday, 4 December 2022 at 23:45:00 UTC-8 j...@aims.ac.za wrote:

Note sage 9.2 (debian package) gives an error (sage 9.7 does not):

 

Probably the following ticket then (Scrimshaw/Chapoton):

 

https://trac.sagemath.org/ticket/15216 

[Travis Scrimshaw]

Let me mostly rephrase what Nils said above with a bit more of specific information. I would say this issue comes from a "feature" of ClonableArray. The default hashing of ClonableArray is to also hash in the parent and have elements in different parents not (by default) compare equal. A coercion needs to get involved for "natural" equality (i.e., ignoring the parent), which is a general issue within Sage.

Best,
Travis

[Martin R]

Would it make sense to have a subclass, or perhaps an option to ClonableArray.__init__, that determines whether or not to include the parent into the hash?  The current behaviour seems rather error prone to me.

On the other hand, I am not sure whether GF(3)(4) == ZZ(4) is desirable.

Martin

[Nils Bruin]

On Friday, 9 December 2022 at 02:49:12 UTC-8 axio...@yahoo.de wrote:

Would it make sense to have a subclass, or perhaps an option to ClonableArray.__init__, that determines whether or not to include the parent into the hash?  The current behaviour seems rather error prone to me.

I think we've identified that there are definitely cases where having parent *not* included in the hash for certain versions of ClonableArray is beneficial. I'm not sure we have a convincing case where having the parent in the hash IS beneficial. A scenario where this would be the case would be if somewhere we end up with sets/dictionaries with loads of (non-equal) instances of ClonableArray such that tuple(...) hashes to the same value. I think it's unlikely that distinguishing on parent in the hash is ever a performance-essential feature. So it may be reasonable to change the hash function for all of them.

If there are cases for both then the appropriate way is via overriding the hash on subclassing, not introducing extra flags on the init method: hash gets looked up via special method slots, so you should just make sure that the class has the right function registered. There's a mechanism for doing so: overriding methods in subclasses.

On the other hand, I am not sure whether GF(3)(4) == ZZ(4) is desirable.

It's basically a corollary of being able to write GF(3)(1) + 1 . You'd end up with a system that is very painful to use interactively if you wouldn't allow for that (but, yes: coercion through quotient maps is definitely more problematic than through inclusions).

[Martin R]

https://trac.sagemath.org/ticket/34824 now removes the parent from the hash, and all the overrides I could find.

[Martin R]

Help needed again.  I removed the (seemingly) useless overrides, but now SetPartition and DecoratedPermutation isn't hashable anymore.  Curiously, ParkingFunction is, and I don't see the difference.

[Nils Bruin]

Once again:

https://docs.python.org/3/reference/datamodel.html#object.__hash

__eq__ and __hash__ are tied ad the hip: overriding one prevents inheritance of the other.

Python takes its contract "equality must imply identical hashes" a little more seriously than sage, so Python doesn't allow the contract to be broken by a careless partial override: rewriting one needs a rewrite of the other as well.

Whether __eq__ is the right hook to tap into I don't know. If those classes participate in coercion, then absolutely not: they should implement _eq_ or something like that and let coercion do its thing before presenting elements to the class for comparison. But if these are really just container types then a simple-minded `__eq__` implementation may be sufficient (and perhaps there's nothing sensible to inherit from! I haven't checked their MRO)

[Martin R]

Ah, thank you so much!

Just to make sure that I understand the philosophy: if two elements are supposed to compare equal, they should have parents which can be coerced to a common parent, right?  For example, the following (which is current behaviour) is not really what we want:

sage: A = SetPartitions(3)([[1,2],[3]])
sage: B = SetPartition([[1,2],[3]])
sage: A == B
True
sage: coercion_model.common_parent(A, B)
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In [10], line 1
----> 1 coercion_model.common_parent(A, B)

File ~/sage-develop/src/sage/structure/coerce.pyx:1062, in sage.structure.coerce.CoercionModel.common_parent()
   1060         a = base.an_element() if isinstance(base, Parent) else base(1)
   1061         b = x.an_element() if isinstance(x, Parent) else x(1)
-> 1062         base = parent(self.canonical_coercion(a, b)[0])
   1063 return base
   1064

File ~/sage-develop/src/sage/structure/coerce.pyx:1393, in sage.structure.coerce.CoercionModel.canonical_coercion()
   1391         self._record_exception()
   1392
-> 1393 raise TypeError("no common canonical parent for objects with parents: '%s' and '%s'"%(xp, yp))
   1394
   1395

TypeError: no common canonical parent for objects with parents: 'Set partitions of {1, 2, 3}' and 'Set partitions'

[Nils Bruin]

On Monday, 12 December 2022 at 00:22:30 UTC-8 axio...@yahoo.de wrote:

Ah, thank you so much!

Just to make sure that I understand the philosophy: if two elements are supposed to compare equal, they should have parents which can be coerced to a common parent, right?  For example, the following (which is current behaviour) is not really what we want:

sage: A = SetPartitions(3)([[1,2],[3]])
sage: B = SetPartition([[1,2],[3]])
sage: A == B
True
sage: coercion_model.common_parent(A, B)

TypeError: no common canonical parent for objects with parents: 'Set partitions of {1, 2, 3}' and 'Set partitions'

I think that is a bit surprising, but if SetPartitions don't really occur much in binary operations I think it will be a hardly visible quirk. One has to be careful generalizing principles about how to implement coercion/equality/hashing because we a;ready know that some of the things we want lead to inconsistencies.

When in doubt, the safe thing is definitely to NOT install coercions (it can always be done later), so I'd hesitate to recommend to change the behaviour above. I think you'd want at least a practical use case to justify it.

Note that the relevant conversions: A.parent()(B) and B.parent()(A) do work.

It seems to me the converse implication, if for two elements the coercion framework is happy to find a common parent in which they compare equal, then they should be equal in the first place, sounds a little more probable, but I suspect one can get problematic situations from that too.

[Travis Scrimshaw]

+1 on what Nils said; I only find it slightly surprising initially. Compare this with comparing a list to a Partition as well. Equality is a bit different as a programming concept than a mathematical one. When you implement a custom __eq__, then you are separating that class from the coercion-based equality.

+1 on removing the parent from the hash of ClonableArray and its family tree.

Best,

Travis

[Martin R]

I must admit that I do not understand the philosophy.

But apart from that: for classes inheriting from ClonableArray, which have to implement equality (because there is no coercion to a common parent), do they have to implement _richcmp_ or __richcmp__ or _eq_ or __eq__?  (The amount of magic in python / sagemath is extremely confusing to me.)

[Martin R]

https://trac.sagemath.org/ticket/34824 has a green bot, please review!

[Travis Scrimshaw]

I must admit that I do not understand the philosophy.

Which part?

But apart from that: for classes inheriting from ClonableArray, which have to implement equality (because there is no coercion to a common parent), do they have to implement _richcmp_ or __richcmp__ or _eq_ or __eq__?  (The amount of magic in python / sagemath is extremely confusing to me.)

Double underscore stuff is usually Python (sometimes Cython; or mimicked with __richcmp__). Single underscores tend to be hooks that Sage (or a particular class) has set up to either avoid inheritance issues and/or allow more flexibility in subclasses.

Best,

Travis