On Mon, Jun 22, 2009 at 11:25:32AM +0200, Franco Saliola wrote:
> Here is a quick description of what is below: Subclasses of Element
> complain that no sorting algorithm is defined even when all the rich
> comparison methods have been implemented. Bug?
>
> In the code sample below, C is a class that inherits from Element and
> implements all the rich comparison methods.
>
> {{{
> sage: class C(sage.structure.element.Element):
> ... def __init__(self, a):
> ... self.a = a
> ... def __repr__(self):
> ... return str(self.a)
> ... def __eq__(self, other):
> ... return self.a == other.a
> ... def __ne__(self, other):
> ... return self.a != other.a
> ... def __lt__(self, other):
> ... return self.a < other.a
> ... def __le__(self, other):
> ... return self.a <= other.a
> ... def __gt__(self, other):
> ... return self.a > other.a
> ... def __ge__(self, other):
> ... return self.a >= other.a
> }}}
>
> In theory, the cmp function should use the rich comparison methods for
> comparisions. However, since __cmp__ has also been implemented (it is
> implemented by Element), cmp bypasses all the rich comparison methods and
> calls __cmp__ directly. This leads to an error since Element requires
> subclasses to define a sorting algorithm:
>
> {{{
> sage: a = C('a')
> sage: b = C('b')
>
> sage: a < b
> True
>
> sage: cmp(a,b)
> ------------------------------------------------------------
> Traceback (most recent call last):
> File "<ipython console>", line 1, in <module>
> File "element.pyx", line 648, in
> sage.structure.element.Element.__cmp__ (sage/structure/element.c:6064)
> File "element.pyx", line 561, in sage.structure.element.Element._cmp
> (sage/structure/element.c:5135)
> File "element.pyx", line 663, in
> sage.structure.element.Element._cmp_c_impl
> (sage/structure/element.c:6239)
> NotImplementedError: BUG: sort algorithm for elements of 'None' not
> implemented
> }}}
>
> And this leads to problems with sorting via the cmp function:
>
> {{{
> sage: sorted([b,a])
> [a, b]
>
> sage: sorted([b,a], cmp=cmp)
> ------------------------------------------------------------
> Traceback (most recent call last):
> File "<ipython console>", line 1, in <module>
> File "element.pyx", line 648, in
> sage.structure.element.Element.__cmp__ (sage/structure/element.c:6064)
> File "element.pyx", line 561, in sage.structure.element.Element._cmp
> (sage/structure/element.c:5135)
> File "element.pyx", line 663, in
> sage.structure.element.Element._cmp_c_impl
> (sage/structure/element.c:6239)
> NotImplementedError: BUG: sort algorithm for elements of 'None' not
> implemented
> }}}
>
> One can get around this by implementing __cmp__ as well as the rich
> comparison methods, but I'm wondering whether it might be better for
> Element to check for and use the rich comparison methods before freaking
> out.
>
> Is there a good reason (speed? efficiency?) for this behaviour? Should I
> open a ticket?
Many Sage-Combinat developers have been annoyed by this. The thing is
that cmp is often required, even for partial orders, because many
output routines call sorted(...).
I have seen this discussed over and over on the list. Is there a
definitive synthesis of the specifications and policy in the
developers guide for how to implement partial/total orders for Python
class in Sage? There are quite a few comments in element.py, but I
find them somewhat cryptic and incomplete.
If such specifications are not yet written / fully fixed, here is what
I would find the most practical:
- The class should implement _eq_(self, other) and _lt_(self, other)
which would be guaranteed to take elements of the same parent and
test respectively whether self == other or self < other.
Other names would be fine to me. Another option would be to
implement_richcmp(self, other) which returns whether self is
strictly smaller, strictly greater, equal or incomparable.
Both options could possibly be supported, as there are situations
where one or the other are more practical.
- By default, all the other rich comparisons (__eq__, __le__, __lt__,
__gt__, __ne__, ...) would be defined by calling the above.
- By default, __cmp___ would try to use _eq_ and _lt_. What to do if the
elements are incomparable? One option would be to compare them
w.r.t. some internal order; this internal order should depend only
on the value of the object and should be consistent within a Sage
session. An option would be to compare the hash values.
Of course if the class can do something better, it should!
- Should it be imposed that the total order be a linear extension of
the partial order?
> (For the record, Nicolas tells me that the new category theory code does
> not fix this issue.)
Yup. And it can't because given the inheritance order, code in Element
(and Parent) always override stuff from the categories.
Best,
Nicolas
--
Nicolas M. Thiéry "Isil" <nthi...@users.sf.net>
http://Nicolas.Thiery.name/
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to sage-devel@googlegroups.com
To unsubscribe from this group, send email to
sage-devel-unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://www.sagemath.org
-~----------~----~----~----~------~----~------~--~---
