{{{id=374| class Demo: def __init__(self, data): self._data = data /// }}} {{{id=375| d = Demo('s'); d /// <__main__.Demo instance at 0x517c200> }}} {{{id=397| d._data /// 's' }}} {{{id=393| type(d), d.__class__ /// (, ) }}} {{{id=383| class Demo: def __init__(self, data): self._data = data def __repr__(self): return "This is %s"%self._data /// }}} {{{id=382| d = Demo("it"); d /// This is it }}} {{{id=381| class Demo: def __init__(self, data): self._data = data def __repr__(self): return "This is %s"%self._data def __mul__(self, other): return self.__class__(self._data + other._data) /// }}} {{{id=380| d = Demo("i"); e = Demo("t") /// }}} {{{id=379| d*e /// This is it }}} {{{id=378| e*d /// This is ti }}} {{{id=377| class Demo: def __init__(self, data): self._data = data def __repr__(self): return "This is %s"%self._data def __mul__(self, other): return self.__class__(self._data + other._data) def __iter__(self): for x in self._data: yield self.__class__(x) /// }}} {{{id=376| d = Demo("i"); e = Demo("t") /// }}} {{{id=384| d*e /// This is it }}} {{{id=385| list(d*e) /// [This is i, This is t] }}} {{{id=392| len(d*e) /// Traceback (most recent call last): File "", line 1, in File "_sage_input_92.py", line 10, in exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("bGVuKGQqZSk="),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))' + '\n', '', 'single') File "", line 1, in File "/tmp/tmp8F5hfU/___code___.py", line 2, in exec compile(u'len(d*e)' + '\n', '', 'single') File "", line 1, in AttributeError: Demo instance has no attribute '__len__' }}} {{{id=391| class CardFromIter(object): def cardinality(self): return len(list(self)) /// }}} {{{id=390| class DemoLen(Demo, CardFromIter): pass /// }}} {{{id=389| e = DemoLen('bla') /// }}} {{{id=387| e /// This is bla }}} {{{id=386| e.cardinality() /// 3 }}} {{{id=394| e.__class__.mro() /// [, , , ] }}} {{{id=396| /// }}} {{{id=395| /// }}}

How to implement new algebraic structures in Sage

Sage's category and coercion framework

Simon King
Friedrich-Schiller-Universität Jena
E-mail: simon dot king at uni hyphen jena dot de
© 2011/2013
 

The aim of this tutorial is to explain how one can benefit from Sage's category framework and coercion model when implementing new algebraic structures. It is based on a worksheet created in 2011.

 There is a thematic tutorial based on this worksheet, available from your notebook via

Help -> Thematic Tutorials

-> Modeling Mathematics on a computer

-> How to implement basic algebraic structures in Sage

We illustrate the concepts of Sage’s category framework and coercion model by means of a detailed example, namely a toy implementation of fraction fields. The code is developed step by step, so that the reader can focus on one detail in each part of this tutorial.

 

Practical work after this presentation:

Implement your favourite algebraic structure, e.g., implement (a toy implementation of) group algebras.

 

Outline - for the impatient

Use existing base classes

For using Sage’s coercion system, it is essential to work with sub–classes of sage.structure.parent.Parent or sage.structure.element.Element, respectively. They provide default implementations of many “magical” double-underscore Python methods, which must not be overridden. Instead, the actual implementation should be in single underscore methods, such as _add_ or _mul_.

Turn your parent structure into an object of a category

Declare the category during initialisation—Your parent structure will inherit further useful methods and consistency tests.

Provide your parent structure with an element class

Assign to it an attribute called Element—The elements will inherit further useful methods from the category. In addition, some basic conversions will immediately work.

Implement further conversions

Never override a parent’s __call__ method! Provide the method _element_constructor_ instead.

Declare coercions

If a conversion happens to be a morphism, you may consider to turn it into a coercion. It will then implicitly be used in arithmetic operations.

Advanced coercion: Define construction functors for your parent structure

Sage will automatically create new parents for you when needed, by the so–called pushout construction.

Run the automatic test suites

Each method should be documented and provide a doc test (we are not giving examples here). In addition, any method defined for a category should be supported by a test method that is executed when running the test suite.

Base classes

In Sage, a "Parent" is an object of a category and contains elements.

Parents should inherit from `sage.structure.parent.Parent` and their elements from `sage.structure.element.Element`.

Sage provides appropriate sub-classes of Parent and Element for a variety of more concrete algebraic structures, such as groups, rings, or fields, and of their elements.

But some old stuff in Sage doesn't use it:

Volunteers for refactoring are welcome!

 

The parent

We want to implement a special kind of fields, namely fraction fields, and we should thus start with the base class `sage.rings.field.Field`.

{{{id=3| from sage.rings.field import Field /// }}}

This base class provides a lot more methods than a general parent:

{{{id=1| [p for p in dir(Field) if p not in dir(Parent)] /// ['__div__', '__fraction_field', '__ideal_monoid', '__iter__', '__pow__', '__rdiv__', '__rpow__', '__rxor__', '__xor__', '_an_element', '_an_element_c', '_an_element_impl', '_coerce_', '_coerce_c', '_coerce_impl', '_coerce_self', '_coerce_try', '_default_category', '_gens', '_gens_dict', '_has_coerce_map_from', '_ideal_class_', '_latex_names', '_list', '_one_element', '_pseudo_fraction_field', '_random_nonzero_element', '_richcmp', '_unit_ideal', '_zero_element', '_zero_ideal', 'algebraic_closure', 'base_extend', 'cardinality', 'class_group', 'coerce_map_from_c', 'coerce_map_from_impl', 'content', 'divides', 'extension', 'fraction_field', 'gcd', 'gen', 'gens', 'get_action_c', 'get_action_impl', 'has_coerce_map_from_c', 'has_coerce_map_from_impl', 'ideal', 'ideal_monoid', 'integral_closure', 'is_commutative', 'is_field', 'is_finite', 'is_integral_domain', 'is_integrally_closed', 'is_noetherian', 'is_prime_field', 'is_ring', 'is_subring', 'is_zero', 'krull_dimension', 'list', 'ngens', 'one', 'one_element', 'order', 'prime_subfield', 'principal_ideal', 'quo', 'quotient', 'quotient_ring', 'random_element', 'unit_ideal', 'zero', 'zero_element', 'zero_ideal', 'zeta', 'zeta_order'] }}} {{{id=372| Field.is_finite?? ///

File: /home/simon/SAGE/prerelease/sage-5.10.rc1/devel/sage/sage/rings/ring.pyx

Source Code (starting at line 1027):

def is_finite(self):
    """
    Return ``True`` if this ring is finite.

    EXAMPLES::

        sage: QQ.is_finite()
        False
        sage: GF(2^10,'a').is_finite()
        True
        sage: R.<x> = GF(7)[]
        sage: R.is_finite()
        False
        sage: S.<y> = R.quo(x^2+1)
        sage: S.is_finite()
        True
    """
    if self.is_zero():
        return True
    raise NotImplementedError
}}} {{{id=373| Field.extension?? ///

File: /home/simon/SAGE/prerelease/sage-5.10.rc1/devel/sage/sage/rings/ring.pyx

Source Code (starting at line 1523):

def extension(self, poly, name=None, names=None, embedding=None):
    """
    Algebraically extends self by taking the quotient ``self[x] / (f(x))``.

    INPUT:

    - ``poly`` -- A polynomial whose coefficients are coercible into
      ``self``

    - ``name`` -- (optional) name for the root of `f`

    .. NOTE::

        Using this method on an algebraically complete field does *not*
        return this field; the construction ``self[x] / (f(x))`` is done
        anyway.

    EXAMPLES::

        sage: R = QQ['x']
        sage: y = polygen(R)
        sage: R.extension(y^2 - 5, 'a')
        Univariate Quotient Polynomial Ring in a over Univariate Polynomial Ring in x over Rational Field with modulus a^2 - 5

    ::

        sage: F.<a> = GF(5).extension(x^2 - 2)
        sage: P.<t> = F[]
        sage: R.<b> = F.extension(t^2 - a); R
        Univariate Quotient Polynomial Ring in b over Univariate Quotient Polynomial Ring in a over Finite Field of size 5 with modulus a^2 + 3 with modulus b^2 + 4*a
    """
    from sage.rings.polynomial.polynomial_element import Polynomial
    if not isinstance(poly, Polynomial):
        try:
            poly = poly.polynomial(self)
        except (AttributeError, TypeError):
            raise TypeError, "polynomial (=%s) must be a polynomial."%repr(poly)
    if not names is None:
        name = names
    if isinstance(name, tuple):
        name = name[0]
    if name is None:
        name = str(poly.parent().gen(0))
    if embedding is not None:
        raise NotImplementedError, "ring extension with prescripted embedding is not implemented"
    R = self[name]
    I = R.ideal(R(poly.list()))
    return R.quotient(I, name)
}}}

The following is a very basic implementation of fraction fields, that needs to be complemented later.

{{{id=361| class MyFrac(UniqueRepresentation, Field): # UniqueRepresentation provides a weak cache def __init__(self, base): # Fraction fields are only defined for integral domains if base not in IntegralDomains(): raise ValueError, "%s is no integral domain"%base Field.__init__(self, base) def _repr_(self): # Single underscore method for string representation return "NewFrac(%s)"%repr(self.base()) # These are implicitly used in the automated test suites below def base_ring(self): return self.base().base_ring() def characteristic(self): return self.base().characteristic() /// }}}

In the following sections, we will successively add or change details of MyFrac. Rather than giving a full class definition in each step, we define new versions of MyFrac by inheriting from the previously defined version of MyFrac. In that way, we can focus on the single detail that is relevant in each section.

Some words on this basic implementation:

Python uses double-underscore methods for arithemetic methods and string representations. Sage's base classes often have a default implementation.

Hence, implement SINGLE underscore methods _repr_, and similarly _add_, _mul_ etc.

{{{id=11| MyFrac(ZZ['x']) /// NewFrac(Univariate Polynomial Ring in x over Integer Ring) }}}

The test whether the given base is an integral domain is our first use of categories:

{{{id=357| MyFrac(Integers(15)) /// Traceback (most recent call last): File "", line 1, in File "_sage_input_106.py", line 10, in exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("TXlGcmFjKEludGVnZXJzKDE1KSk="),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))' + '\n', '', 'single') File "", line 1, in File "/tmp/tmpJ2vdHc/___code___.py", line 3, in exec compile(u'MyFrac(Integers(_sage_const_15 ))' + '\n', '', 'single') File "", line 1, in File "classcall_metaclass.pyx", line 330, in sage.misc.classcall_metaclass.ClasscallMetaclass.__call__ (build/cythonized/sage/misc/classcall_metaclass.c:1224) File "cachefunc.pyx", line 992, in sage.misc.cachefunc.WeakCachedFunction.__call__ (build/cythonized/sage/misc/cachefunc.c:5394) File "/home/simon/SAGE/prerelease/sage-5.10.rc1/local/lib/python2.7/site-packages/sage/structure/unique_representation.py", line 447, in __classcall__ instance = typecall(cls, *args, **options) File "classcall_metaclass.pyx", line 518, in sage.misc.classcall_metaclass.typecall (build/cythonized/sage/misc/classcall_metaclass.c:1586) File "", line 7, in __init__ ValueError: Ring of integers modulo 15 is no integral domain }}}

Note that UniqueRepresentation automatically provides pickling, at least to some extent. And it provides a cache:

{{{id=358| loads(dumps(MyFrac(ZZ))) is MyFrac(ZZ) /// True }}}

The elements

We use the base class :class:`sage.structure.element.FieldElement`. Note that field elements do not require that their parent is a field:

{{{id=330| from sage.structure.element import FieldElement FieldElement(ZZ) /// Generic element of a structure }}}

Basic implementation of the fraction field elements

Input: Numerator and denominator, which have to belong to the underlying integral domain (the "base").

Denominator not zero, and wlog. not negative - by default, the denominator is one.

String representation via _repr_.

Arithmetic via _add_, _mul_. Do not override the default double underscore __add__, __mul__! Otherwise, you won't have coercion.

In the single underscore methods and in __cmp__, you can always assume that both arguments belong to the same parent.

Note the use of self.__class__

{{{id=332| class MyElement(FieldElement): # Input: Numerator and denominator, that need to belong to the base of the given parent def __init__(self, n,d=None, parent=None): if parent is None: raise ValueError, "The parent must be provided" B = parent.base() # Default denominator is 1 if d is None: d = B.one_element() # Numerator and denominator belong to the base if n not in B or d not in B: raise ValueError, "Numerator and denominator must be elements of %s"%B # Normalise the denominator if d==0: raise ZeroDivisionError, "The denominator must not be zero" if d<0: self.n = -n self.d = -d else: self.n = n self.d = d FieldElement.__init__(self,parent) # These methods are required! See below def numerator(self): return self.n def denominator(self): return self.d # Single underscore again def _repr_(self): return "(%s):(%s)"%(self.n,self.d) # FIRST USE OF COERCION MODEL: # We can assume that both to-be-compared elements live in the same parent. def __cmp__(self, other): return cmp(self.n*other.denominator(), other.numerator()*self.d) # Single underscore arithmetic methods # NOTE: Elements will later be sub-classes of MyElement. We make sure that the # result will use the same sub-classes def _add_(self, other): C = self.__class__ D = self.d*other.denominator() return C(self.n*other.denominator()+self.d*other.numerator(),D, self.parent()) def _sub_(self, other): C = self.__class__ D = self.d*other.denominator() return C(self.n*other.denominator()-self.d*other.numerator(),D, self.parent()) def _mul_(self, other): C = self.__class__ return C(self.n*other.numerator(), self.d*other.denominator(), self.parent()) def _div_(self, other): C = self.__class__ return C(self.n*other.denominator(), self.d*other.numerator(), self.parent()) /// }}}

Thanks to the single underscore methods, some basic arithmetics works, if we stay inside our parent structure:

{{{id=339| P = MyFrac(ZZ) a = MyElement(3,4,P) b = MyElement(1,2,P) /// }}} {{{id=340| a+b; a-b; a*b; a/b /// (10):(8) (2):(8) (3):(8) (6):(4) }}} {{{id=343| a-b == MyElement(1,4,P) /// True }}}

We didn't implement exponentiation - but it just works:

{{{id=342| a^3 /// (27):(64) }}}

There is a default implementation of element tests. We can already do

{{{id=350| a in P /// True }}}

since a is defined as an element of P.

But we can not verify yet that the integers are contained in the fraction field of the ring of integers:

{{{id=352| 1 in P /// Traceback (most recent call last): File "", line 1, in File "_sage_input_115.py", line 10, in exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("MSBpbiBQ"),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))' + '\n', '', 'single') File "", line 1, in File "/tmp/tmpNYO8Ii/___code___.py", line 3, in exec compile(u'_sage_const_1 in P' + '\n', '', 'single') File "", line 1, in File "parent.pyx", line 1121, in sage.structure.parent.Parent.__contains__ (build/cythonized/sage/structure/parent.c:8678) File "parent.pyx", line 942, in sage.structure.parent.Parent.__call__ (build/cythonized/sage/structure/parent.c:7916) NotImplementedError }}}

We will take care of that later.

Chosing a category

Sometimes the base classes do not reflect the mathematics:

The set of m by n  matrices over a field forms, in general, not more than a vector space. Hence, they are not implemented on top of  sage.rings.ring.Ring.

However, if m=n then the matrix space is an algebra, thus, in particular is a ring.

But their (Cython) classes coincide:

{{{id=299| MS1 = MatrixSpace(QQ,2,3) isinstance(MS1, Ring) /// False }}} {{{id=301| MS2 = MatrixSpace(QQ,2) isinstance(MS2, Ring) /// False }}} {{{id=370| MS1.__class__ is MS2.__class__ /// True }}}

Sage's category framework can differentiate the two cases:

{{{id=313| Rings() /// Category of rings }}} {{{id=303| MS1 in Rings() /// False }}} {{{id=304| MS2 in Rings() /// True }}}

Surprisingly, MS2 has more methods than MS1, even though their classes coincide:

{{{id=320| import inspect len([s for s in dir(MS1) if inspect.ismethod(getattr(MS1,s,None))]) /// 55 }}} {{{id=321| len([s for s in dir(MS2) if inspect.ismethod(getattr(MS2,s,None))]) /// 77 }}}

Below, we will explain how this can be taken advantage of.

It is no surprise that our parent P defined above knows that it belongs to the category of fields, as it is derived from the base class of fields.

{{{id=34| P.category() /// Category of fields }}}

However, we could choose a smaller category, namely the category of quotient fields.

Why should one choose a category?

One can provide default methods for all objects of a category, and for all elements of such objects. Hence:

It is an alternative way of inheriting useful stuff.

It does not rely on implementation details, but on mathematical concepts.

In addition, the categories define test suites for their objects and elements. Hence, one also gets basic sanity tests for free.

 

How does this so-called category framework work?

Abstract base classes for the objects ("parent_class") and the elements of objects ("element_class") are provided by attributes of the category

During initialisation of a parent, the class of the parent is dynamically changed into a sub-class of the category's parent class.

Likewise, sub–classes of the category’s element class are available for the creation of elements of the parent.

 

Dynamic change of classes does not work in Cython. Nevertheless, method inheritance still works, by virtue of a __getattr__ method.

=>  It is strongly recommended to use the category framework both in Python and in Cython.

Let us see whether there is any gain in chosing the category of quotient fields instead of the category of fields:

{{{id=33| QuotientFields().parent_class, QuotientFields().element_class /// (, ) }}} {{{id=37| [p for p in dir(QuotientFields().parent_class) if p not in dir(Fields().parent_class)] /// [] }}} {{{id=353| [p for p in dir(QuotientFields().element_class) if p not in dir(Fields().element_class)] /// ['_derivative', 'denominator', 'derivative', 'factor', 'numerator', 'partial_fraction_decomposition'] }}}

So, there is no immediate gain for the parent, but additional methods become available to our fraction field elements. Note that some of these methods are place-holders: There is no default implementation, but it is required (respectively is optional) to implement these methods:

{{{id=366| QuotientFields().element_class.denominator /// }}} {{{id=368| from sage.misc.abstract_method import abstract_methods_of_class abstract_methods_of_class(QuotientFields().element_class)['optional'] /// ['_add_', '_mul_'] }}} {{{id=369| abstract_methods_of_class(QuotientFields().element_class)['required'] /// ['__nonzero__', 'denominator', 'numerator'] }}}

Hence, when implementing elements of a quotient field, it is required to implement methods returning the denominator and the numerator, and a method that tells whether the element is nonzero, and in addition, it is optional (but certainly recommended) to provide some arithmetic methods. If one forgets to implement the required methods, the test suites of the category framework will complain—see below.

Implementing the category framework for the parent

We simply need to declare the correct category by an optional argument of the field constructor, where we provide the possibility to override the default category:

{{{id=39| class MyFrac(MyFrac): def __init__(self, base, category=None): if base not in IntegralDomains(): raise ValueError, "%s is no integral domain"%base Field.__init__(self, base, category=category or QuotientFields()) /// }}}

When constructing instances of MyFrac, their class is dynamically changed into a new class MyFrac_with_category.

It is a common sub-class of MyFrac and of the category's parent class.

{{{id=38| P = MyFrac(ZZ) type(P); isinstance(P,MyFrac); isinstance(P,QuotientFields().parent_class) /// True True }}}

P inherits additional methods:

The base class <Field> does not have a method `sum`. But P inherits such method from the category of commutative additive monoids

{{{id=371| hasattr(MyFrac, 'sum') /// False }}} {{{id=48| P.sum.__module__ /// 'sage.categories.commutative_additive_monoids' }}}

We have seen above that we can add elements. Nevertheless, the sum method does not work, yet:

{{{id=51| a = MyElement(3,4,P) b = MyElement(1,2,P) c = MyElement(-1,2,P) P.sum([a,b,c]) /// Traceback (most recent call last): File "", line 1, in File "_sage_input_135.py", line 10, in exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("YSA9IE15RWxlbWVudCgzLDQsUCkKYiA9IE15RWxlbWVudCgxLDIsUCkKYyA9IE15RWxlbWVudCgtMSwyLFApClAuc3VtKFthLGIsY10p"),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))' + '\n', '', 'single') File "", line 1, in File "/tmp/tmpXaSUsu/___code___.py", line 6, in exec compile(u'P.sum([a,b,c])' + '\n', '', 'single') File "", line 1, in File "/home/simon/SAGE/prerelease/sage-5.10.rc1/local/lib/python2.7/site-packages/sage/categories/commutative_additive_monoids.py", line 141, in sum return sum(args, self.zero()) File "ring.pyx", line 841, in sage.rings.ring.Ring.zero_element (build/cythonized/sage/rings/ring.c:7487) File "parent.pyx", line 942, in sage.structure.parent.Parent.__call__ (build/cythonized/sage/structure/parent.c:7916) NotImplementedError }}} {{{id=398| P.sum?? ///

File: /home/simon/SAGE/prerelease/sage-5.10.rc1/local/lib/python2.7/site-packages/sage/categories/commutative_additive_monoids.py

Source Code (starting at line 120):

def sum(self, args):
    r"""
    n-ary sum

    INPUT:

     - ``args`` -- a list (or iterable) of elements of ``self``

    Returns the sum of the elements in `args`, as an element of `self`.

    EXAMPLES::

        sage: S = CommutativeAdditiveMonoids().example()
        sage: (a,b,c,d) = S.additive_semigroup_generators()
        sage: S.sum((a,b,a,c,a,b))
        3*a + c + 2*b
        sage: S.sum(())
        0
        sage: S.sum(()).parent() == S
        True
    """
    return sum(args, self.zero())
}}}

The reason is that the sum method starts with the return value of P.zero_element(), which defaults to P(0)—but the conversion of integers into P is not implemented, yet.

 

Implementing the category framework for the elements

Similar to what we have seen for parents, a new class is dynamically created that combines the element class of the parent’s category with the class that we have implemented above. However, the category framework is implemented in a different way for elements than for parents:

  • Provide the parent P (or its class) with an attribute called "Element", whose value is a concrete class.
  • The parent automatically obtains an attribute "P.element_class", that subclasses both P.Element and the abstract class P.category().element_class.

 Hence, for providing our fraction fields with their own element classes, we just need to add a single line to our class:

{{{id=54| class MyFrac(MyFrac): Element = MyElement /// }}}

That little change has several benefits:

  • We can now create elements by simply calling the parent:
{{{id=53| P = MyFrac(ZZ) P(1); P(2,3) /// (1):(1) (2):(3) }}}
  • There is a method zero_element returning the expected result:
{{{id=63| P.zero_element() /// (0):(1) }}}
  • The sum method mentioned above suddenly works:
{{{id=62| a = MyElement(9,4,P) b = MyElement(1,2,P) c = MyElement(-1,2,P) P.sum([a,b,c]) /// (36):(16) }}}

What did happen behind the scenes to make this work?

We provided "P.Element", and get the class "P.element_class" (stored as a lazy attribute) as reward.

It is another dynamic class, a simultaneous sub-class of MyElement and of `P.category().element_class`:

{{{id=328| P.__class__.element_class /// }}} {{{id=329| P.element_class; type(P.element_class) /// }}} {{{id=64| issubclass(P.element_class, MyElement); issubclass(P.element_class,P.category().element_class) /// True True }}}

The default __call__ method of P passes the arguments to P.element_class, adding the argument "parent=P".

This is why we are now able to create elements by calling the parent, yielding instances of the new dynamic class.

{{{id=66| type(P(2,3)) /// }}}

Note: All elements of P should use the element class. In order to make sure that this also holds for the result of arithmetic operations, we created them as instances of self.__class__ in the arithmetic methods of MyElement.

P.zero_element() merely does P(0) and thus returns an instance of P.element_class. Since P.sum([...]) starts with P.zero_element(), we have:

{{{id=59| type(a); isinstance(a,P.element_class); type(P.sum([a,b,c])) /// False }}}

The method factor() inherited from P.category().element_class (see above) simply works:

{{{id=74| a; a.factor(); P(6,4).factor() /// (9):(4) 2^-2 * 3^2 2^-1 * 3 }}}

But that's surprising: The element "a" is just an instance of  MyElement, not of P.element_class, and its class does not know about the factor method.

In fact, we see the above-mentioned __getattr__ at work.

{{{id=85| hasattr(type(a), 'factor'); hasattr(P.element_class, 'factor'); hasattr(a, 'factor') /// False True True }}}

A first note on performance

The category framework is sometimes blamed for speed regressions (see trac tickets #9138 versus #11900).

But if the category framework is used properly, then it is fast. For illustration, we determine the time needed to access an attribute inherited from the element class. First, we consider an element that uses the class that we implemented above, but does not use the category framework properly:

{{{id=80| timeit('a.factor',number=1000); type(a) # Here, the category is NOT properly used /// 1000 loops, best of 3: 1.54 µs per loop }}}

Now, we consider an element that is equal to a, but uses the category framework properly.

{{{id=82| a2 = P(9,4) # Here, it IS properly used a2 == a /// True }}} {{{id=399| type(a), type(a2) /// (, ) }}} {{{id=83| timeit('a2.factor',number=1000); type(a2) /// 1000 loops, best of 3: 378 ns per loop }}}

Recall

{{{id=402| class MyElement(FieldElement): # Input: Numerator and denominator, that need to belong to the base of the given parent def __init__(self, n,d=None, parent=None): if parent is None: raise ValueError, "The parent must be provided" B = parent.base() # Default denominator is 1 if d is None: d = B.one_element() # Numerator and denominator belong to the base if n not in B or d not in B: raise ValueError, "Numerator and denominator must be elements of %s"%B # Normalise the denominator if d==0: raise ZeroDivisionError, "The denominator must not be zero" if d<0: self.n = -n self.d = -d else: self.n = n self.d = d FieldElement.__init__(self,parent) # These methods are required! See below def numerator(self): return self.n def denominator(self): return self.d # Single underscore again def _repr_(self): return "(%s):(%s)"%(self.n,self.d) # FIRST USE OF COERCION MODEL: # We can assume that both to-be-compared elements live in the same parent. def __cmp__(self, other): return cmp(self.n*other.denominator(), other.numerator()*self.d) # Single underscore arithmetic methods # NOTE: Elements will later be sub-classes of MyElement. We make sure that the # result will use the same sub-classes def _add_(self, other): C = self.__class__ D = self.d*other.denominator() return C(self.n*other.denominator()+self.d*other.numerator(),D, self.parent()) def _sub_(self, other): C = self.__class__ D = self.d*other.denominator() return C(self.n*other.denominator()-self.d*other.numerator(),D, self.parent()) def _mul_(self, other): C = self.__class__ return C(self.n*other.numerator(), self.d*other.denominator(), self.parent()) def _div_(self, other): C = self.__class__ return C(self.n*other.denominator(), self.d*other.numerator(), self.parent()) /// }}} {{{id=400| class MyFrac(UniqueRepresentation, Field): # UniqueRepresentation provides a weak cache Element = MyElement def __init__(self, base, category=None): if base not in IntegralDomains(): raise ValueError, "%s is no integral domain"%base Field.__init__(self, base, category=category or QuotientFields()) def _repr_(self): # Single underscore method for string representation return "NewFrac(%s)"%repr(self.base()) # These are implicitly used in the automated test suites below def base_ring(self): return self.base().base_ring() def characteristic(self): return self.base().characteristic() /// }}} {{{id=403| P = MyFrac(ZZ); P /// NewFrac(Integer Ring) }}} {{{id=404| P(1), P.zero(), P.sum([P(1,2), P(3,4)]) /// ((1):(1), (0):(1), (10):(8)) }}} {{{id=408| P(1)/P(1,2) /// (2):(1) }}}

Creating a sub-category

We aim at implementing a generic `latex` method for fraction field elements, and a method for faction fields that turns a list defining a continued fraction into the corresponding fraction. For this purpoe, we create a sub-category of the category of fraction fields. Admittedly, it doesn't make much sense, mathematically; this is to show how to implement generic code in the category.

When we want to create a sub-category, we need to provide a method `super_categories`, that returns a list of all immediate super categories (here: category of quotient fields). The parent and element methods of a category are provided as methods of a class `ParentMethods` and `Element Methods`, as follows:

{{{id=405| latex(P(1)) /// \verb|(1):(1)| }}} {{{id=407| class QuotientFieldsWithLatex(Category): # DO NOT create a sub-class of QuotientFields!!!!! # Instead, declare that QuotientFields() is a super-category. def super_categories(self): return [QuotientFields()] class ParentMethods: def continued_fraction(self, L): p1 = self.one() p2 = self.zero() q1 = self.zero() q2 = self.one() for a in L: P = self(a)*p1 + p2 Q = self(a)*q1 + q2 p2 = p1 q2 = q1 p1 = P q1 = Q return P/Q class ElementMethods: def _latex_(self): return r"\frac{%s}{%s}"%(self.numerator(), self.denominator()) /// }}} {{{id=417| P = MyFrac(ZZ, category=QuotientFieldsWithLatex()) /// }}} {{{id=433| latex(P(1,2)) /// \frac{1}{2} }}} {{{id=416| show(latex(P(1,2))) /// }}} {{{id=415| P.continued_fraction([3,7,15,1,292]) /// (103993):(33102) }}} {{{id=414| RR(103993/33102) /// 3.14159265301190 }}}

The Test Suites

The category framework does not only provide functionality but  also a test framework.

"Abstract" methods

A category can require/suggest certain parent or element methods, that the user must/should implement. This is in order to smoothly blend with the methods that already exist in Sage.

The methods that ought to be provided are called "abstract methods". Let us see what methods are needed for quotient fields and their elements:

 
{{{id=413| from sage.misc.abstract_method import abstract_methods_of_class /// }}} {{{id=412| abstract_methods_of_class(QuotientFields().element_class) /// {'required': ['__nonzero__', 'denominator', 'numerator'], 'optional': ['_add_', '_mul_']} }}}

Hence, the elements must provide denominator() and numerator() methods, may provide Sage's single underscore arithmetic methods (actually any ring element should provide them).

_test_... methods

If a parent or element method's name start with "_test_", it gives rise to a test in the automatic test suite.

For example, it is tested

  • whether a parent P actually is an instance of the parent class of the category of P,
  • whether the user hase implemented the required abstract methods,
  • whether some defining structural properties (e.g., commutativity) hold.

Here are the tests that form the test suite of quotient fields:

{{{id=411| TestSuite(P).run(verbose=True) /// running ._test_additive_associativity() . . . pass running ._test_an_element() . . . pass running ._test_associativity() . . . pass running ._test_category() . . . pass running ._test_characteristic() . . . pass running ._test_characteristic_fields() . . . pass running ._test_distributivity() . . . pass running ._test_elements() . . . Running the test suite of self.an_element() running ._test_category() . . . pass running ._test_eq() . . . pass running ._test_nonzero_equal() . . . pass running ._test_not_implemented_methods() . . . pass running ._test_pickling() . . . pass pass running ._test_elements_eq_reflexive() . . . pass running ._test_elements_eq_symmetric() . . . pass running ._test_elements_eq_transitive() . . . pass running ._test_elements_neq() . . . pass running ._test_eq() . . . pass running ._test_not_implemented_methods() . . . pass running ._test_one() . . . pass running ._test_pickling() . . . pass running ._test_prod() . . . pass running ._test_some_elements() . . . pass running ._test_zero() . . . pass }}}

As one can see, tests are also performed on elements. There are methods that return one element or a list of some elements, relying on "typical" elements that can be found in most algebraic structures.

{{{id=410| P.an_element(); P.some_elements() /// (2):(1) [(2):(1)] }}}

Unfortunately, the list of elements that is returned by the default method is of length one, and that single element could also be a bit more interesting.

The method an_element relies on a method _an_element_, so, we implement that. We also override the some_elements method.

{{{id=424| class MyFrac(MyFrac): def _an_element_(self): a = self.base().an_element() b = self.base_ring().an_element() if (a+b)!=0: return self(a)**2/(self(a+b)**3) if b != 0: return self(a)/self(b)**2 return self(a)**2*self(b)**3 def some_elements(self): return [self.an_element(),self(self.base().an_element()),self(self.base_ring().an_element())] /// }}} {{{id=423| P = MyFrac(ZZ['x']) P.an_element(); P.some_elements() /// (x^2):(x^3 + 3*x^2 + 3*x + 1) [(x^2):(x^3 + 3*x^2 + 3*x + 1), (x):(1), (1):(1)] }}} {{{id=436| TestSuite(P).run() /// }}}

We would now like to add a method that tests the `factor` method. But for this, it is needed to make the following work:

{{{id=431| P(2)^-1 /// Traceback (most recent call last): File "", line 1, in File "_sage_input_39.py", line 10, in exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("UCgyKV4tMQ=="),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))' + '\n', '', 'single') File "", line 1, in File "/tmp/tmpgUpv1j/___code___.py", line 3, in exec compile(u'P(_sage_const_2 )**-_sage_const_1 ' + '\n', '', 'single') File "", line 1, in File "element.pyx", line 1790, in sage.structure.element.RingElement.__pow__ (sage/structure/element.c:14919) File "element.pyx", line 3385, in sage.structure.element.generic_power_c (sage/structure/element.c:26367) File "element.pyx", line 1847, in sage.structure.element.RingElement.__invert__ (sage/structure/element.c:15744) File "element.pyx", line 1813, in sage.structure.element.RingElement.__div__ (sage/structure/element.c:15142) File "coerce.pyx", line 856, in sage.structure.coerce.CoercionModel_cache_maps.bin_op (sage/structure/coerce.c:8115) TypeError: unsupported operand parent(s) for '/': '' and 'NewFrac(Univariate Polynomial Ring in x over Integer Ring)' }}}

In other words, we need that the integer 1 is automatically converted into an element of our fraction field

Coercion - the basics

Coercion is involved if one wants to be able to do arithmetic, comparisons, etc. between elements of distinct parents.

Theoretical background

Dissociation from type conversion

In C: "coercion" means "automatic type conversion".

In Sage: Coercion is not about a change of types, but about a change of parents.

Elements of the same type may have very different parents, such as here:

{{{id=77| P1 = QQ['v,w']; P2 = ZZ['w,v'] type(P1.gen()) == type(P2.gen()); P1==P2 /// True False }}}

P2 naturally is a sub-ring of P1. So, it makes sense to be able to add elements of the two rings - the result should then live in P1:

{{{id=73| (P1.gen()+P2.gen()).parent() is P1 /// True }}}

It would be rather inconvenient if one needed to explicitly convert an element of P2 into P1 before adding. The coercion system does that conversion automatically.

Coercion versus conversion

A coercion happens implicitly, without being explicitly requested by the user.

Hence, coercion must be based on mathematical rigour.

1. A coercion is a map, a conversion may be a partial map

For example, a polynomial of degree zero over the integers can be interpreted as an integer - but there is no general conversion of a polynomial into an integer. So, that must not be a coercion.

Hence, coercion maps are defined on the level of parents, and they can be obtained from the following methods:

{{{id=71| P1.has_coerce_map_from(P2) /// True }}} {{{id=70| P1.coerce_map_from(P2) /// Call morphism: From: Multivariate Polynomial Ring in w, v over Integer Ring To: Multivariate Polynomial Ring in v, w over Rational Field }}} {{{id=68| P2.has_coerce_map_from(P1) /// False }}} {{{id=81| P2.coerce_map_from(P1) is None /// True }}}
2. A coercion is a morphism, i.e., structure preserving

Any real number can be converted to an integer, namely by rounding. However, such a conversion is not useful in arithmetic operations:

{{{id=94| int(1.6)+int(2.7) == int(1.6+2.7) /// False }}}

It depends on the parents which structure is to be preserved. For example, the coercion from the integers into the rational field is a homomorphism of euclidean domains:

{{{id=93| QQ.coerce_map_from(ZZ).category_for() /// Category of euclidean domains }}}

Hence, categories show up in coercion, too.

3. If a coercion exists, it has to be unique, and must coincide with conversion
4. Coercions can be composed

If there is a coercion φ from P1 to P2 and another coercion ψ from P2 to P3, then the composition of φ followed by ψ must yield a (the) coercion from P1 to P3.

5. The identity is a coercion

Together with the two preceding requirements, it follows: If there are conversions from P1 to P2 and from P2 to P1, then they are mutually inverse.

 

Implementing conversion

We implement some conversions into our fraction fields by simply providing the attribute "Element".

However, we can not convert elements of a fraction field into elements of another fraction field, yet:

 

{{{id=218| P(2/3) /// Traceback (most recent call last): File "", line 1, in File "_sage_input_48.py", line 10, in exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("UCgyLzMp"),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))' + '\n', '', 'single') File "", line 1, in File "/tmp/tmpmkunMP/___code___.py", line 3, in exec compile(u'P(_sage_const_2 /_sage_const_3 )' + '\n', '', 'single') File "", line 1, in File "parent.pyx", line 961, in sage.structure.parent.Parent.__call__ (sage/structure/parent.c:8070) File "coerce_maps.pyx", line 82, in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (sage/structure/coerce_maps.c:3821) File "coerce_maps.pyx", line 77, in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (sage/structure/coerce_maps.c:3723) File "/home/simon/SAGE/prerelease/sage-5.9.rc0/local/lib/python2.7/site-packages/sage/categories/sets_cat.py", line 339, in _element_constructor_from_element_class return self.element_class(parent = self, *args, **keywords) File "", line 13, in __init__ ValueError: Numerator and denominator must be elements of Univariate Polynomial Ring in x over Integer Ring }}}

For implementing a conversion, the default __call__ method should (almost) never be overridden. Again, some old parents violate that rule - please help to refactor them!

Instead, implement the method _element_constructor_, that should return an instance of the parent's element class.

{{{id=111| class MyFrac(MyFrac): def _element_constructor_(self, *args,**kwds): # If numerator and denominator are given, then # no preprocessing is needed if len(args)!=1: return self.element_class(*args,parent=self,**kwds) # Only one argument is given---analyse it! x = args[0] try: # Does it have a parent? P = x.parent() except AttributeError: # If not, fall back to the default return self.element_class(x,parent=self,**kwds) # If x belongs to a "friendly" quotient field, then use its numerator/denominator if P in QuotientFields() and P != self.base(): return self.element_class(x.numerator(),x.denominator(),parent=self,**kwds) return self.element_class(x,parent=self,**kwds) /// }}}

In addition to the conversion from the base ring and from pairs of base ring elements, we now also have a conversion from the rationals to our fraction field of ZZ:

{{{id=242| P = MyFrac(ZZ) P(2); P(2,3); P(3/4) /// (2):(1) (2):(3) (3):(4) }}}

Recall that above, the test "1 in P" failed with an error. Since we can now convert the integer 1 into P, the error has vanished. But there is still a negative outcome:

{{{id=292| 1 in P /// False }}}

The technical reason: We have a conversion P(1) of 1 into P, but this is not a coercion.

{{{id=129| P.has_coerce_map_from(ZZ), P.has_coerce_map_from(QQ) /// (False, False) }}}

How to turn a conversion into a coercion

  • Could use P.register_coercion during initialisation (see documentation of that method).
  • More flexible: Provide a method _coerce_map_from_ 

_coerce_map_from_ accepts a parent as argument. If it returns "True", then conversion is used for coercion (but it may return an actual map).

Note that we need a special case for the rational field, since QQ.base() is not the ring of integers.

{{{id=136| class MyFrac(MyFrac): def _coerce_map_from_(self, S): # Coercion from the base ring: if self.base().has_coerce_map_from(S): return True # Coercion from the fraction field of a "good" ring if S in QuotientFields(): if self.base().has_coerce_map_from(S.base()): return True # QQ is special if hasattr(S,'ring_of_integers') and self.base().has_coerce_map_from(S.ring_of_integers()): return True /// }}}

By the method above, a parent coercing into the base ring will also coerce into the fraction field, and a fraction field coerces into another fraction field if there is a coercion of the corresponding base rings. Now, we have:

{{{id=126| P = MyFrac(QQ['x']) P.has_coerce_map_from(ZZ['x']), P.has_coerce_map_from(Frac(ZZ['x'])), P.has_coerce_map_from(QQ) /// (True, True, True) }}}

We can now use coercion from ZZ['x'] and from QQ into P for arithmetic operations between the two rings:

{{{id=125| 3/4+P(2)+ZZ['x'].gen(); (P(2)+ZZ['x'].gen()).parent() is P /// (4*x + 11):(4) True }}}

Equality and element containment

Recall that above, the test "1 in P" had a negative outcome. Let us repeat the test now:

{{{id=124| 1 in P /// True }}}

Why is that?

The default element containment test "x in P" is based on the interplay of three building blocks: conversion, coercion and equality test.

  1. Clearly, if the conversion P(x) raises an error, then x can not be seen as an element of P. On the other hand, a conversion P(x) can in general do very nasty things. So, the fact that P(x) works does not mean that x is in P.
  2. If x is in P, then the conversion P(x) should not change x (at least, that's the default). Hence, we will have x==P(x).
  3. Sage uses coercion not only for arithmetic operations, but also for comparison. Hence, if there is a coercion between the parent of x and P, then it will be applied. If there is a coercion from x.parent() to P then x==P(x) reduces to P(x)==P(x). Otherwise, x==P(x) will evaluate as false.

That leads to the following default implementation of element containment testing:

"x in P" holds if and only if "x==P(x)" does not raise an error and evaluates as true

If the user is not happy with that behaviour, the "magical" Python method __contains__ can be overridden.

Coercion - the advanced parts

So far, we are able to add integers and rational numbers to elements of our new implementation of the fraction field of ZZ.

{{{id=123| P = MyFrac(ZZ) /// }}} {{{id=122| 1/2+P(2,3)+1 /// (13):(6) }}}

Surprisingly, we can even add a polynomial over the integers to an element of P, even though the result lives in a new parent, namely in a polynomial ring over P:

{{{id=121| P(1/2) + ZZ['x'].gen(), (P(1/2) + ZZ['x'].gen()).parent() is P['x'] /// ((1):(1)*x + (1):(2), True) }}}

In the next, seemingly more easy example, there "obviously" is a coercion from the fraction field of ZZ to the fraction field of ZZ['x'].

However, Sage does not know enough about our new implementation of fraction fields. Hence, it does not recognise the coercion:

{{{id=120| Frac(ZZ['x']).has_coerce_map_from(P) /// False }}}

How / why has the new ring been constructed above?

How can we establish a coercion from P to Frac(ZZ['x'])?

Most parents can be constructed from simpler pieces.

If we are lucky, a parent can tell how it has been constructed:

{{{id=119| Poly,R = QQ[x].construction() Poly,R /// (Poly[x], Rational Field) }}} {{{id=118| Poly(R) is QQ['x']; Poly(ZZ) is ZZ['x']; Poly(P) is P['x'] /// True True True }}} {{{id=117| Fract,R = QQ.construction() Fract,R /// (FractionField, Integer Ring) }}}

These constructions are functorial:

Frac: IntegralDomains() --> Fields()

Poly[x]: Rings() --> Rings()

In particular, the construction functors can be composed:

{{{id=116| Poly*Fract /// Poly[x](FractionField(...)) }}} {{{id=115| (Poly*Fract)(ZZ) is QQ[x] /// True }}}

In addition, it is assumed that we have a coercion from input to output of the construction functor:

{{{id=356| ((Poly*Fract)(ZZ))._coerce_map_from_(ZZ) /// Composite map: From: Integer Ring To: Univariate Polynomial Ring in x over Rational Field Defn: Natural morphism: From: Integer Ring To: Rational Field then Polynomial base injection morphism: From: Rational Field To: Univariate Polynomial Ring in x over Rational Field }}}

Construction functors do not necessarily commute:

{{{id=164| (Fract*Poly)(ZZ) /// Fraction Field of Univariate Polynomial Ring in x over Integer Ring }}}

Given:

We have parents P1, P2, R and construction functors F1, F2, such that

P1 = F1(R) and P2 = F2(R)

Wanted:

Find new construction functor F3, such that both P1 and P2 coerce into P3=F3(R).

In analogy to a notion of category theory, P3 is called the pushout of P1 and P2; and similarly F3 is called the pushout of F1 and F2.

{{{id=110| from sage.categories.pushout import pushout pushout(Fract(ZZ),Poly(ZZ)) /// Univariate Polynomial Ring in x over Rational Field }}}

F1*F2 and F2*F1 are natural candidates for the pushout of F1 and F2. However, the result must not depend on the order

=> We need a consistent choice of order: "indecomposable" construction functors have a rank.

If F1.rank is smaller than F2.rank, then the pushout is F2*F1 (hence, F1 is applied first).

We have

{{{id=137| Fract.rank, Poly.rank /// (5, 9) }}}

and thus the pushout is

{{{id=152| Fract.pushout(Poly), Poly.pushout(Fract) /// (Poly[x](FractionField(...)), Poly[x](FractionField(...))) }}}

This is why the example above has worked.

However, only "elementary" construction functors have a rank:

{{{id=170| (Fract*Poly).rank /// Traceback (most recent call last): File "", line 1, in File "_sage_input_71.py", line 10, in exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("KEZyYWN0KlBvbHkpLnJhbms="),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))' + '\n', '', 'single') File "", line 1, in File "/tmp/tmpUZ2aqs/___code___.py", line 2, in exec compile(u'(Fract*Poly).rank' + '\n', '', 'single') File "", line 1, in AttributeError: 'CompositeConstructionFunctor' object has no attribute 'rank' }}}

What do we do with two chains of construction functors?

Shuffle the functors from the two chains (F1,F2,...) and (G1,G2,...):

If F1.rank < G1.rank: Apply F1, and proceed with (F2,F3,...) and (G1,G2,...).

If F1.rank > G1.rank: Apply G1, and proceed with (F1,F2,...) and (G2,G3,...).

If F1.rank == G1.rank, then we need other techniques (see below).

As an illustration, we first get us some functors and then see how chains of functors are shuffled.

{{{id=169| AlgClos, R = CC.construction(); AlgClos /// AlgebraicClosureFunctor }}} {{{id=168| Compl, R = RR.construction(); Compl /// Completion[+Infinity] }}} {{{id=167| Matr, R = (MatrixSpace(ZZ,3)).construction(); Matr /// MatrixFunctor }}} {{{id=166| AlgClos.rank, Compl.rank, Fract.rank, Poly.rank, Matr.rank /// (3, 4, 5, 9, 10) }}}

When we apply Fract, AlgClos, Poly and Fract to the ring of integers, we obtain

{{{id=194| (Fract*Poly*AlgClos*Fract)(ZZ) /// Fraction Field of Univariate Polynomial Ring in x over Algebraic Field }}}

When we apply Compl, Matr and Poly to the ring of integers, we obtain

{{{id=205| (Poly*Matr*Compl)(ZZ) /// Univariate Polynomial Ring in x over Full MatrixSpace of 3 by 3 dense matrices over Real Field with 53 bits of precision }}}

Applying the shuffling procedure yields

{{{id=204| (Poly*Matr*Fract*Poly*AlgClos*Fract*Compl)(ZZ) /// Univariate Polynomial Ring in x over Full MatrixSpace of 3 by 3 dense matrices over Fraction Field of Univariate Polynomial Ring in x over Complex Field with 53 bits of precision }}}

and this is indeed equal to the pushout found by Sage:

{{{id=202| pushout((Fract*Poly*AlgClos*Fract)(ZZ), (Poly*Matr*Compl)(ZZ)) /// Univariate Polynomial Ring in x over Full MatrixSpace of 3 by 3 dense matrices over Fraction Field of Univariate Polynomial Ring in x over Complex Field with 53 bits of precision }}}

The case F1.rank==G1.rank

Sage's pushout constructions offers two ways to proceed:

  1. Construction functors have a method `merge()` that either returns None or returns a construction functor. If either F1.merge(G1) or G1.merge(F1) return a functor H1, then apply H1 and proceed with (F2,F3,...) and (G2,G3,...).
  2. Construction functors have a method `commutes()`. If F1.commutes(G1) or G1.commutes(F1) returns True, then apply both F1 and G1 in any order, and proceed with (F2,F3,...) and (G2,G3,...).

By default, F1.merge(G1) returns F1 if F1==G1, and returns None otherwise.

The `commutes()` method exists, but it seems that so far nobody has implemented two functors of the same rank that commute.

The typical application of `merge()` is:

Provide coercion between different implementations of the same algebraic structure

If F1(P) and F2(P) are different implementations of the same thing, then F1.merge(F2)(P) should be the default implementation of that thing.

Here:

  • Implement an alternative to the "usual" fraction field functor, having the same rank, but returning our new implementation.
  • Make our new implementation the default, by providing a merge method.

Remark:

  • Do not override the default __call__ method -- implement `_apply_functor` instead.
  • Declare domain and codomain of the functor.
{{{id=200| from sage.categories.pushout import ConstructionFunctor class MyFracFunctor(ConstructionFunctor): rank = 5 def __init__(self): ConstructionFunctor.__init__(self, IntegralDomains(), Fields()) def _apply_functor(self, R): return MyFrac(R) def merge(self, other): if isinstance(other, (type(self), sage.categories.pushout.FractionField)): return self /// }}} {{{id=312| MyFracFunctor() /// MyFracFunctor }}}

We verify that our functor can really be used to construct our implementation of fraction fields, and that it can be merged with either itself or the usual fraction field constructor:

{{{id=198| MyFracFunctor()(ZZ) /// NewFrac(Integer Ring) }}} {{{id=197| MyFracFunctor().merge(MyFracFunctor()) /// MyFracFunctor }}} {{{id=196| MyFracFunctor().merge(Fract) /// MyFracFunctor }}}

There remains to let our new fraction fields know about the new construction functor:

{{{id=229| class MyFrac(MyFrac): def construction(self): return MyFracFunctor(), self.base() /// }}} {{{id=235| MyFrac(ZZ['x']).construction() /// (MyFracFunctor, Univariate Polynomial Ring in x over Integer Ring) }}}

Due to merging, we have:

{{{id=195| pushout(MyFrac(ZZ['x']), Frac(QQ['x'])) /// NewFrac(Univariate Polynomial Ring in x over Rational Field) }}}
Adding a new test

Now, as we have more  interesting elements, we may also add a test for the "factor" method. Recall that the method was inherited from the category, but it appears that it is not tested.

Normally, a test for a method defined by a category should be provided by the same category. Hence, since `factor()` is defined in the category of quotient fields, a test should be added there. But we won't change source code here and will instead create another sub-category.

Apparently, the product of the factors returned be `e.factor()` should be equal to `e`. For forming the product, we use the `prod()` method, that, no surprise, is inherited from another category.

{{{id=271| P.prod.__module__ /// 'sage.categories.monoids' }}}

We provide an instance of our quotient field implementation with that new category. Note that categories have a default _repr_ method, that guesses a good string representation from the name of the class: QuotientFieldsWithTest becomes "quotient fields with test".

{{{id=438| from sage.categories.category import Category class QuotientFieldsWithTest(Category): # do *not* inherit from QuotientFields, but ... def super_categories(self): return [QuotientFields()] # ... declare QuotientFields as a super category! class ParentMethods: # Simply keep the stuff inherited from the super category pass class ElementMethods: # Add the new test def _test_factorisation(self, **options): P = self.parent() assert self == P.prod([P(b)**e for b,e in self.factor()]) /// }}} {{{id=278| P = MyFrac(ZZ['x'], category=QuotientFieldsWithTest()) P.category() /// Category of quotient fields with test }}}

The new test is inherited from the category. Since an_element() is returning a complicated element, _test_factorisation is a serious test.

{{{id=279| P.an_element()._test_factorisation /// }}} {{{id=272| P.an_element().factor() /// (x + 1)^-3 * x^2 }}}

Last, we observe that the new test has automatically become part of the test suite. We remark that the existing test became more serious as well, by an_element() returning something more interesting.

{{{id=273| TestSuite(P).run(verbose=True) /// running ._test_additive_associativity() . . . pass running ._test_an_element() . . . pass running ._test_associativity() . . . pass running ._test_category() . . . pass running ._test_characteristic() . . . pass running ._test_characteristic_fields() . . . pass running ._test_distributivity() . . . pass running ._test_elements() . . . Running the test suite of self.an_element() running ._test_category() . . . pass running ._test_eq() . . . pass running ._test_factorisation() . . . pass running ._test_nonzero_equal() . . . pass running ._test_not_implemented_methods() . . . pass running ._test_pickling() . . . pass pass running ._test_elements_eq_reflexive() . . . pass running ._test_elements_eq_symmetric() . . . pass running ._test_elements_eq_transitive() . . . pass running ._test_elements_neq() . . . pass running ._test_eq() . . . pass running ._test_not_implemented_methods() . . . pass running ._test_one() . . . pass running ._test_pickling() . . . pass running ._test_prod() . . . pass running ._test_some_elements() . . . pass running ._test_zero() . . . pass }}} {{{id=443| /// }}}