如何在Sage中实现新的代数结构

Sage的范畴与强制框架

本教程的目的是解释在实现新的代数结构时如何从Sage的范畴框架和强制模型中获益。它基于2011年创建的一份工作表。

我们通过一个具体的例子,即分数域的玩具实现,说明了Sage的范畴框架和强制模型的概念。代码是一步一步地开发的,这样读者就可以在本教程的每一部分中关注一个细节。完整的代码可以在附录中找到。

大纲

  • 使用现有基类

    为了使用Sage的强制系统,必须使用 sage.structure.parent.Parentsage.structure.element.Element 分别是。它们提供了许多“神奇的”双下划线Python方法的默认实现,这些方法不能被重写。相反,实际的实现应该在 单下划线 方法,如 _add__mul_ .

  • 将父结构转换为类别的对象

    在初始化期间声明类别--父结构将继承更多有用的方法和一致性测试。

  • 为父结构提供元素类

    给它分配一个名为 Element ---元素将从类别继承更多有用的方法。此外,一些基本的转换将立即生效。

  • 执行进一步的转换

    永远不要覆盖父对象的 __call__ 方法!提供方法 _element_constructor_ 相反。

  • 宣布胁迫

    如果一个转换碰巧是一个态射,你可以考虑把它变成一个强制。到时候会的 隐含地 用于算术运算。

  • 高级强制:为父结构定义构造函子

    当需要时,Sage会自动为你创建新的父母 sage.categories.pushout.pushout() 施工。

  • 运行自动测试套件

    每种方法都应该被记录下来并提供一个doc测试(我们在这里没有给出例子)。此外,为一个类别的对象或元素定义的任何方法都应该由一个测试方法支持,该方法在运行测试套件时执行。

基类

在Sage中,“父”是一个类别的对象,包含元素。父母应该继承 sage.structure.parent.Parent 以及他们的元素 sage.structure.element.Element .

Sage提供适当的子类 ParentElement 对于各种更具体的代数结构,例如群、环或域及其元素。但是Sage里的一些老东西不使用它。 欢迎志愿者进行重构!

亲本

因为我们希望实现一种特殊类型的字段,即分数字段,所以在基类之上构建是有意义的 sage.rings.ring.Field 由Sage提供。:

sage: from sage.rings.ring import Field

这个基类提供了比一般父类多得多的方法:

sage: [p for p in dir(Field) if p not in dir(Parent)]
['__fraction_field',
 '__ideal_monoid',
 '__iter__',
 '__len__',
 '__pow__',
 '__rpow__',
 '__rtruediv__',
 '__rxor__',
 '__truediv__',
 '__xor__',
 '_an_element_impl',
 '_coerce_',
 '_coerce_c',
 '_coerce_impl',
 '_coerce_try',
 '_default_category',
 '_gens',
 '_ideal_class_',
 '_latex_names',
 '_list',
 '_one_element',
 '_pseudo_fraction_field',
 '_random_nonzero_element',
 '_unit_ideal',
 '_zero_element',
 '_zero_ideal',
 'algebraic_closure',
 'base_extend',
 'class_group',
 'content',
 'derivation',
 'derivation_module',
 'divides',
 'epsilon',
 'extension',
 'fraction_field',
 'frobenius_endomorphism',
 'gcd',
 'gen',
 'gens',
 'ideal',
 'ideal_monoid',
 'integral_closure',
 'is_commutative',
 'is_field',
 'is_integral_domain',
 'is_integrally_closed',
 'is_noetherian',
 'is_prime_field',
 'is_subring',
 'krull_dimension',
 'localization',
 'ngens',
 'one',
 'order',
 'prime_subfield',
 'principal_ideal',
 'quo',
 'quotient',
 'quotient_ring',
 'random_element',
 'unit_ideal',
 'zero',
 'zero_ideal',
 'zeta',
 'zeta_order']

下面是分数字段的一个非常基本的实现,后面需要补充。:

sage: from sage.structure.unique_representation import UniqueRepresentation
sage: class MyFrac(UniqueRepresentation, Field):
....:     def __init__(self, base):
....:         if base not in IntegralDomains():
....:             raise ValueError("%s is no integral domain" % base)
....:         Field.__init__(self, base)
....:     def _repr_(self):
....:         return "NewFrac(%s)"%repr(self.base())
....:     def base_ring(self):
....:         return self.base().base_ring()
....:     def characteristic(self):
....:         return self.base().characteristic()

此基本实现由以下步骤组成:

  • 萨奇的任何环都有 base 和A 底座环 . 环的“普通”分数域 R 有基础 R 还有基环 R.base_ring() ::

    sage: Frac(QQ['x']).base(), Frac(QQ['x']).base_ring()
    (Univariate Polynomial Ring in x over Rational Field, Rational Field)
    

    声明基很容易:我们只需将它作为参数传递给字段构造函数。:

    sage: Field(ZZ['x']).base()
    Univariate Polynomial Ring in x over Integer Ring
    

    我们正在实现一个返回基环的单独方法。

  • Python使用双下划线方法来表示算术方法和字符串。Sage的基类通常有一个默认的实现,它被要求 implement SINGLE underscore methods _repr_, and similarly _add_, _mul_ etc.

  • 我们鼓励你 让你的父母“与众不同” . 也就是说,父母只有在完全相同的情况下才应该评价相等。Sage提供了创建独特父类的框架。这里我们使用最简单的方法:从类继承 sage.structure.unique_representation.UniqueRepresentation 够了。使父对象唯一对于高效实现非常重要,因为重复创建“相同”父对象将花费大量时间。

  • 分数域只为整数域定义。因此,如果给定的环不属于积分域的范畴,我们将提出一个错误。这是我们的第一个类别用例。

  • 最后,我们添加了一个返回字段特征的方法。我们不详细讨论,但下面我们研究的一些自动化测试隐含地依赖于这种方法。

我们不正确地认为,基本域不是一个积分

sage: MyFrac(ZZ['x'])
NewFrac(Univariate Polynomial Ring in x over Integer Ring)
sage: MyFrac(Integers(15))
Traceback (most recent call last):
...
ValueError: Ring of integers modulo 15 is no integral domain

注解

继承自 UniqueRepresentation 自动为我们的类提供酸洗,保留唯一的父条件。如果我们在某个外部模块或交互式会话中定义了类,pickling将立即工作。

但是,为了使下面的示例在Sage的doctesting框架中工作,我们需要将类指定为 __main__ 模块,以便在取消拾取期间可以查找类。

sage: import __main__
sage: __main__.MyFrac = MyFrac
sage: loads(dumps(MyFrac(ZZ))) is MyFrac(ZZ)
True

注解

在下面的部分中,我们将依次添加或更改 MyFrac . 我们没有在每个步骤中给出完整的类定义,而是定义 MyFrac 从以前定义的版本继承 MyFrac . 我们相信这将有助于读者专注于每一部分相关的单个细节。

完整的代码可以在附录中找到。

元素

我们使用基类 sage.structure.element.FieldElement . 请注意,在创建字段元素时,不会测试给定父级是否为字段:

sage: from sage.structure.element import FieldElement
sage: FieldElement(ZZ)
Generic element of a structure

我们的分数场元素的玩具实现基于以下考虑:

  • 元素和分母都需要定义。应该有返回分子resp的方法。分母。

  • 分母不能为零,并且(假设基是有序环)我们可以使它非负,而不会失去一般性。默认情况下,分母为1。

  • 字符串表示由单个--下划线方法返回 _repr_ . 为了使我们的分数字段元素与Sage中已经存在的元素区分开来,我们使用了不同的字符串表示。

  • 算法采用单下划线方法实现 _add__mul_ 等。 We do not override the default double underscore __add__, __mul__ ,否则,我们就不能使用Sage的强制模型。

  • 比较可以使用 _richcmp__cmp_ . 这会自动使关系运算符 ==< 工作。 当心 :在这些方法中,只调用Python2 cmp 为了与Python3兼容,应该避免使用函数。您可以使用 richcmp sage提供的功能。

    请注意 _cmp__richcmp_ 应提供,否则比较无效:

    sage: class Foo(sage.structure.element.Element):
    ....:  def __init__(self, parent, x):
    ....:      self.x = x
    ....:  def _repr_(self):
    ....:      return "<%s>" % self.x
    sage: a = Foo(ZZ, 1)
    sage: b = Foo(ZZ, 2)
    sage: a <= b
    Traceback (most recent call last):
    ...
    NotImplementedError: comparison not implemented for <class '__main__.Foo'>
    
  • 在单下划线方法中,我们可以假设 两个参数属于同一个父级 . 这是强制模式的一个好处。

  • 当构造作为算术运算结果的新元素时,我们不直接命名我们的类,但是我们使用 self.__class__ . 稍后,这个会派上用场。

这就产生了以下代码:

sage: class MyElement(FieldElement):
....:     def __init__(self, parent,n,d=None):
....:         B = parent.base()
....:         if d is None:
....:             d = B.one()
....:         if n not in B or d not in B:
....:             raise ValueError("Numerator and denominator must be elements of %s"%B)
....:         # Numerator and denominator should not just be "in" B,
....:         # but should be defined as elements of B
....:         d = B(d)
....:         n = B(n)
....:         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)
....:     def numerator(self):
....:         return self.n
....:     def denominator(self):
....:         return self.d
....:     def _repr_(self):
....:         return "(%s):(%s)"%(self.n,self.d)
....:     def _richcmp_(self, other, op):
....:         from sage.structure.richcmp import richcmp
....:         return richcmp(self.n*other.denominator(), other.numerator()*self.d, op)
....:     def _add_(self, other):
....:         C = self.__class__
....:         D = self.d*other.denominator()
....:         return C(self.parent(), self.n*other.denominator()+self.d*other.numerator(), D)
....:     def _sub_(self, other):
....:         C = self.__class__
....:         D = self.d*other.denominator()
....:         return C(self.parent(), self.n*other.denominator()-self.d*other.numerator(),D)
....:     def _mul_(self, other):
....:         C = self.__class__
....:         return C(self.parent(), self.n*other.numerator(), self.d*other.denominator())
....:     def _div_(self, other):
....:         C = self.__class__
....:         return C(self.parent(), self.n*other.denominator(), self.d*other.numerator())
基本实现的特点和局限性

由于使用了单下划线方法,一些基本算法可以工作, if 我们呆在单亲结构中:

sage: P = MyFrac(ZZ)
sage: a = MyElement(P, 3, 4)
sage: b = MyElement(P, 1, 2)
sage: a+b, a-b, a*b, a/b
((10):(8), (2):(8), (3):(8), (6):(4))
sage: a-b == MyElement(P, 1, 4)
True

有一个默认的元素测试实现。我们已经可以:

sage: a in P
True

自从 a 定义为 P . 然而,我们还不能证明整数是否包含在整数环的分数域中。它甚至不会给出错误的答案,但会导致错误:

sage: 1 in P
Traceback (most recent call last):
...
NotImplementedError: cannot construct elements of NewFrac(Integer Ring)

我们稍后再处理。

Sage中的类别

有时基类并不反映数学:集合 mtimes n 域上的矩阵一般不超过向量空间。因此,这个集合(称为 MatrixSpace )不是在上面实现的 sage.rings.ring.Ring . 然而,如果 m=n ,则矩阵空间是一个代数,因此,是一个环。

从Python基类的角度来看,这两种情况是相同的:

sage: MS1 = MatrixSpace(QQ,2,3)
sage: isinstance(MS1, Ring)
False
sage: MS2 = MatrixSpace(QQ,2)
sage: isinstance(MS2, Ring)
False

Sage的分类框架可以区分这两种情况:

sage: Rings()
Category of rings
sage: MS1 in Rings()
False
sage: MS2 in Rings()
True

事实上, MS2more 方法比 MS1 ::

sage: import inspect
sage: L1 = len([s for s in dir(MS1) if inspect.ismethod(getattr(MS1,s,None))])
sage: L2 = len([s for s in dir(MS2) if inspect.ismethod(getattr(MS2,s,None))])
sage: L1 < L2
True

这是因为 MS2 也从代数的父类继承:

sage: MS1.__class__.__bases__
(<class 'sage.matrix.matrix_space.MatrixSpace'>,
<class 'sage.categories.category.JoinCategory.parent_class'>)
sage: MS2.__class__.__bases__
(<class 'sage.matrix.matrix_space.MatrixSpace'>,
<class 'sage.categories.category.JoinCategory.parent_class'>)

下面,我们将解释如何利用这一点。

我们的父母 P 上面的定义知道它属于字段的类别,因为它是从字段的基类派生的。

sage: P.category()
Category of fields

然而,我们可以选择一个较小的范畴,即商场范畴。

为什么要选择一个类别?

One can provide default methods for all objects of a category, and for all elements of such objects. Hence, the category framework is a way to inherit useful stuff that is not present in the base classes. These default methods do not rely on implementation details, but on mathematical concepts.

此外,类别定义 测试套件 关于它们的对象和元素--见最后一节。因此,人们还可以免费获得基本的健全测试。

如何 类别框架 工作?

对象的抽象基类(“父类”)和对象的元素(“元素”类)由类别的属性提供。在初始化父级期间,父级的类是 动态变化的 放入类别父类的子类中。同样,类别元素类的子类可用于创建父元素,如下所述。

类的动态变化在Cython中不起作用。不过,方法继承仍然有效,因为 __getattr__ 方法。

注解

强烈建议在Python和Cython中同时使用category框架。

让我们看看选择商字段的类别而不是字段的类别是否有任何好处:

sage: QuotientFields().parent_class, QuotientFields().element_class
(<class 'sage.categories.quotient_fields.QuotientFields.parent_class'>,
 <class 'sage.categories.quotient_fields.QuotientFields.element_class'>)
sage: [p for p in dir(QuotientFields().parent_class) if p not in dir(Fields().parent_class)]
[]
sage: [p for p in dir(QuotientFields().element_class) if p not in dir(Fields().element_class)]
['_derivative',
 'denominator',
 'derivative',
 'numerator',
 'partial_fraction_decomposition']

所以,我们的分数场没有直接的增益,但是我们的分数场元素可以使用其他方法。请注意,其中一些方法是占位符:没有默认的实现,但却是 必修的 (分别是 可选择的 )要实现这些方法:

sage: QuotientFields().element_class.denominator
<abstract method denominator at ...>
sage: from sage.misc.abstract_method import abstract_methods_of_class
sage: abstract_methods_of_class(QuotientFields().element_class)['optional']
['_add_', '_mul_']
sage: abstract_methods_of_class(QuotientFields().element_class)['required'] # py2
['__nonzero__', 'denominator', 'numerator']
sage: abstract_methods_of_class(QuotientFields().element_class)['required'] # py3
['__bool__', 'denominator', 'numerator']

因此,当实现商字段的元素时,它是 必修的 实现返回分母和分子的方法,以及一个判断元素是否非零的方法,此外,它也是 可选择的 (当然推荐)提供一些算术方法。如果一个人忘记实现所需的方法,类别框架的测试套件会抱怨--见下文。

为父级实现类别框架

我们只需要通过字段构造函数的可选参数来声明正确的类别,在这里我们提供了重写默认类别的可能性:

sage: from sage.categories.quotient_fields import QuotientFields
sage: 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())

当构造 MyFrac ,它们的类被动态更改为一个名为 MyFrac_with_category . 它是 MyFrac 以及该类别的父类:

sage: P = MyFrac(ZZ)
sage: type(P)
<class '__main__.MyFrac_with_category'>
sage: isinstance(P,MyFrac)
True
sage: isinstance(P,QuotientFields().parent_class)
True

分数场 P 继承其他方法。例如,基类 Field 没有方法 sum . 但是 P 从交换加法幺半群范畴继承了这样的方法 sum() ::

sage: P.sum.__module__
'sage.categories.additive_monoids'

我们在上面已经看到我们可以添加元素。尽管如此 sum 方法不起作用,但:

sage: a = MyElement(P, 3, 4)
sage: b = MyElement(P, 1, 2)
sage: c = MyElement(P, -1, 2)
sage: P.sum([a, b, c])
Traceback (most recent call last):
...
NotImplementedError: cannot construct elements of NewFrac(Integer Ring)

原因是 sum 方法以返回值开始 P.zero() ,默认为 P(0) ---但是把整数转换成 P 尚未实现。

实现元素的类别框架

与我们在父类中看到的类似,动态创建了一个新类,它将父类的元素类与我们上面实现的类结合起来。但是,类别框架对元素的实现方式与父元素不同:

  • 我们提供家长 P (或其类)具有名为“Element`”的属性,其值为类。

  • 亲本 自动地 获取属性 P.element_class ,这两个类都是子类 P.ElementP.category().element_class .

因此,为了给我们的分数字段提供它们自己的元素类, 我们只需要在课堂上加一行 ::

sage: class MyFrac(MyFrac):
....:     Element = MyElement

这个小小的改变带来了几个好处:

  • 我们现在可以通过简单地调用父对象来创建元素:

    sage: P = MyFrac(ZZ)
    sage: P(1), P(2,3)
    ((1):(1), (2):(3))
    
  • 有一种方法 zero 返回预期结果:

    sage: P.zero()
    (0):(1)
    
  • 这个 sum 上述方法突然奏效了:

    sage: a = MyElement(P, 9, 4)
    sage: b = MyElement(P, 1, 2)
    sage: c = MyElement(P, -1, 2)
    sage: P.sum([a,b,c])
    (36):(16)
    
  • 现在,使用我们定义的乘法,可以实现指数运算:

    sage: a^3
    (729):(64)
    
幕后发生了什么让这件事成功?

我们提供了 P.Element ,从而获得 P.element_class ,这是一个 惰性属性 . 它提供了一个 动态 类,它是两者的子类 MyElement 定义见上文和 P.category().element_class ::

sage: P.__class__.element_class
<sage.misc.lazy_attribute.lazy_attribute object at ...>
sage: P.element_class
<class '__main__.MyFrac_with_category.element_class'>
sage: type(P.element_class)
<class 'sage.structure.dynamic_class.DynamicInheritComparisonMetaclass'>
sage: issubclass(P.element_class, MyElement)
True
sage: issubclass(P.element_class,P.category().element_class)
True

这个 违约 __call__ 方法 P 将给定参数传递给 P.element_class ,添加参数 parent=P . 这就是为什么我们现在能够通过调用父元素来创建元素。

特别是,这些元素是新的动态类的实例:

sage: type(P(2,3))
<class '__main__.MyFrac_with_category.element_class'>

注解

All 要素 P 应该使用元素类。为了确保这也适用于算术运算的结果,我们将它们创建为 self.__class__ 在算术方法中 MyElement .

P.zero() 默认为返回 P(0) 从而返回 P.element_class . 自从 P.sum([...]) 开始求和 P.zero() 求和的类只依赖于第一个求和,通过我们的实现,我们得到:

sage: type(a)
<class '__main__.MyElement'>
sage: isinstance(a,P.element_class)
False
sage: type(P.sum([a,b,c]))
<class '__main__.MyFrac_with_category.element_class'>

方法 factor 提供的 P.category().element_class (见上文)简单易行:

sage: a; a.factor(); P(6,4).factor()
(9):(4)
2^-2 * 3^2
2^-1 * 3

但令人惊讶的是:元素 a is just an instance of MyElement, but not of P.element_class, and its class does not know about the factor method. In fact, this is due to a ``_ _为定义的getattruU``方法 sage.structure.element.Element . ::

sage: hasattr(type(a), 'factor')
False
sage: hasattr(P.element_class, 'factor')
True
sage: hasattr(a, 'factor')
True

关于性能的第一个注释

分类框架有时被认为是速度倒退的原因,如 :trac:`9138`:trac:`11900` . 但如果类别框架是 正确使用 ,那就快了。为了举例说明,我们确定访问从element类继承的属性所需的时间。首先,我们考虑一个元素,它使用了我们上面实现的类,但是没有正确使用类别框架:

sage: type(a)
<class '__main__.MyElement'>
sage: timeit('a.factor',number=1000)     # random
1000 loops, best of 3: 2 us per loop

现在,我们考虑一个元素,它等于 a ,但正确使用类别框架:

sage: a2 = P(9,4)
sage: a2 == a
True
sage: type(a2)
<class '__main__.MyFrac_with_category.element_class'>
sage: timeit('a2.factor',number=1000)    # random
1000 loops, best of 3: 365 ns per loop

所以, 不要害怕使用类别!

胁迫--基本原理

理论背景

不只是强迫 类型转换

“强制”在C编程语言中的意思是“自动类型转换”。然而,在Sage中,如果一个人想在不同父母的元素之间做算术、比较等,就涉及到强迫。因此, 强迫不是改变类型,而是改变父母。

作为一个例子,我们表明同一类型的元素很可能属于非常不同的父元素:

sage: P1 = QQ['v,w']; P2 = ZZ['w,v']
sage: type(P1.gen()) == type(P2.gen())
True
sage: P1 == P2
False

P_2 自然是一个 P_1 . 因此,能够添加两个环的元素是有意义的,结果应该存在于 P_1 确实如此:

sage: (P1.gen()+P2.gen()).parent() is P1
True

如果有必要的话,那是相当不方便的 手动 转换元素 P_2 进入之内 P_1 添加之前。强制系统会自动进行转换。

不是每一次皈依都是强迫

强制是隐式发生的,而不是由用户显式请求。因此,强制必须建立在数学严谨的基础上。在我们的示例中 P_2 可以自然地解释为 P_1 . 因此我们有:

sage: P1.has_coerce_map_from(P2)
True
sage: P1.coerce_map_from(P2)
Coercion map:
  From: Multivariate Polynomial Ring in w, v over Integer Ring
  To:   Multivariate Polynomial Ring in v, w over Rational Field

当有一个从 P_1P_2 (即仅限于带整系数的多项式),此转换不是强制:

sage: P2.convert_map_from(P1)
Conversion map:
  From: Multivariate Polynomial Ring in v, w over Rational Field
  To:   Multivariate Polynomial Ring in w, v over Integer Ring
sage: P2.has_coerce_map_from(P1)
False
sage: P2.coerce_map_from(P1) is None
True
强制要求的四条公理
  1. 强制是适当范畴中的一种态射。

    第一条公理有两个含义:

    1. 强制在父级的所有元素上定义。

      整数上的零次多项式可以解释为整数,但尝试转换非零次多项式会导致错误:

      sage: ZZ(P2.one())
      1
      sage: ZZ(P2.gen(1))
      Traceback (most recent call last):
      ...
      TypeError: not a constant polynomial
      

      因此,我们只有一个 部分的 地图。这对一个 转换 ,但部分映射不符合 强制 .

    2. 强制是结构保留。

      任何实数都可以转换成整数,即四舍五入。但是,这种转换在算术运算中没有用处,因为底层的代数结构没有保留:

      sage: int(1.6)+int(2.7) == int(1.6+2.7)
      False
      

      要保留的结构取决于相关父母的类别。例如,从整数到有理域的强制是欧几里德域的同态:

      sage: QQ.coerce_map_from(ZZ).category_for()
      Join of Category of euclidean domains and Category of infinite sets
      and Category of metric spaces
      
  2. 从父母一方到另一方最多只能有一次胁迫

    另外,如果 强制P_2P_1 然后 转换P_2P_1 为的所有元素定义 P_2 同时也与胁迫相吻合。尽管如此,用户公开的映射是内部使用的映射的副本,不同的实例化之间缺少标识:

    sage: P1.coerce_map_from(P2) is P1.convert_map_from(P2)
    False
    

    对于内部使用的贴图,这些贴图是相同的:

    sage: P1._internal_coerce_map_from(P2) is P1._internal_convert_map_from(P2)
    True
    
  3. 强迫是可以合成的

    如果有胁迫 varphi: P_1 to P_2 还有另一种胁迫 psi: P_2 to P_3 ,那么 varphi 然后 psi 必须从 P_1P_3 .

  4. 身份是一种胁迫

    再加上前面的两个公理,它是这样的:如果 P_1P_2P_2P_1 ,则它们是相互反转的。

实现转换

我们在上面已经看到,在提供属性之后,我们的分数字段的一些转换变得可用 Element . 但是,我们还不能将一个分数域的元素转换成另一个分数域的元素:

sage: P(2/3)
Traceback (most recent call last):
...
ValueError: Numerator and denominator must be elements of Integer Ring

为了实现转换, the default __call__ method should (almost) never be overridden. 相反, we implement the method _element_constructor_ ,它应该返回父元素类的一个实例。一些旧的父类违反了该规则--请帮助重构它们!:

sage: class MyFrac(MyFrac):
....:     def _element_constructor_(self, *args, **kwds):
....:         if len(args)!=1:
....:             return self.element_class(self, *args, **kwds)
....:         x = args[0]
....:         try:
....:             P = x.parent()
....:         except AttributeError:
....:             return self.element_class(self, x, **kwds)
....:         if P in QuotientFields() and P != self.base():
....:             return self.element_class(self, x.numerator(), x.denominator(), **kwds)
....:         return self.element_class(self, x, **kwds)

除了从基环和基环元素对的转换之外,我们现在也有了从有理数到分数域的转换 ZZ

sage: P = MyFrac(ZZ)
sage: P(2); P(2,3); P(3/4)
(2):(1)
(2):(3)
(3):(4)

回想一下上面的测试 1 in P 失败,出现错误。我们再试一次,发现错误已经消失了。这是因为我们现在可以转换整数 1 进入之内 P . 但遏制试验还是得出了一个错误的答案:

sage: 1 in P
False

技术原因:我们有一个转换 P(1) 属于 1 进入之内 P ,但这还不算是强迫!:

sage: P.has_coerce_map_from(ZZ), P.has_coerce_map_from(QQ)
(False, False)

建立胁迫

有两种主要的方法可以让Sage用一种特定的转换作为胁迫:

  • 一个人可以用 sage.structure.parent.Parent.register_coercion() ,通常在初始化父级时(参见方法文档)。

  • 更灵活的方法是提供一种方法 _coerce_map_from_ 对父母来说。

PR 做父母。如果 P._coerce_map_from_(R) 收益率 FalseNone ,那么就没有强迫 RP . 如果它返回一个带域的映射 R 和辅酶 P ,则此映射用于强制。如果它回来了 True ,然后从 RP 被用作胁迫。

注意,在下面的实现中,我们需要一个rational字段的特殊情况,因为 QQ.base() 不是整数环。:

sage: class MyFrac(MyFrac):
....:     def _coerce_map_from_(self, S):
....:         if self.base().has_coerce_map_from(S):
....:             return True
....:         if S in QuotientFields():
....:             if self.base().has_coerce_map_from(S.base()):
....:                 return True
....:             if hasattr(S,'ring_of_integers') and self.base().has_coerce_map_from(S.ring_of_integers()):
....:                 return True

通过上述方法,如果存在对应基环的强制,则父强制到基环也将强制到分数字段,并且分数字段强制到另一个分数字段中。现在,我们有:

sage: P = MyFrac(QQ['x'])
sage: P.has_coerce_map_from(ZZ['x']), P.has_coerce_map_from(Frac(ZZ['x'])), P.has_coerce_map_from(QQ)
(True, True, True)

我们现在可以从 ZZ[x]QQ 进入之内 P 对于两个环之间的算术运算:

sage: 3/4+P(2)+ZZ['x'].gen(), (P(2)+ZZ['x'].gen()).parent() is P
((4*x + 11):(4), True)
等式与元素包容

回想一下上面的测试 1 in P 回答错了。现在让我们重复测试:

sage: 1 in P
True

为什么?

默认元素包容测试 x in P 是基于三个构建块的相互作用:转换、强制和平等测试。

  1. 显然,如果 P(x) 然后引发一个错误 x 不能被视为 P . 另一方面,转换 P(x) 一般都会做一些很讨厌的事情。所以,事实上 P(x) 无误作业是必要的,但不足以 x in P .

  2. 如果 P 是的家长 x ,然后转换 P(x) 不会改变的 x (至少,这是默认值)。因此,我们将 x=P(x) .

  3. Sage不仅在算术运算中使用强制,还用于比较: If 有来自 xP ,然后是平等测试 x==P(x) 减少到 P(x)==P(x) . 否则, x==P(x) 将计算为false。

这将导致以下元素包含测试的默认实现:

注解

x in P 当且仅当测试 x==P(x) 不引发错误并计算为true。

如果用户对这种行为不满意,“神奇的”Python方法 __contains__ 可以重写。

强制--高级部件

到目前为止,我们已经能够将整数和有理数添加到 ZZ .

sage: P = MyFrac(ZZ)
sage: 1/2+P(2,3)+1
(13):(6)

令人惊讶的是,我们甚至可以在整数上加一个多项式到 P ,即使 结果住在一个新的父母 ,即在多项式环上 P ::

sage: P(1/2) + ZZ['x'].gen(), (P(1/2) + ZZ['x'].gen()).parent() is P['x']
((1):(1)*x + (1):(2), True)

在下一个看起来更简单的例子中,“显然”有一个来自分数域的强制 ZZ 到分数场 ZZ[x] . 然而,Sage对我们的分数域的新实现还知之甚少。因此,它不承认胁迫:

sage: Frac(ZZ['x']).has_coerce_map_from(P)
False

两个明显的问题出现了:

  1. 如何/为什么在上面的例子中构造了新的环?

  2. 我们怎么能从 Pmathrm{{Frac}}(ZZ[x]) 是吗?

回答这两个问题的关键是从更简单的部分构建父母,我们现在正在研究。第二个问题我们会注意到 not 通过强迫 Pmathrm{{Frac}}(ZZ[x]) 但是通过教Sage自动构建 mathrm{{MyFrac}}(ZZ[x]) 同时胁迫两者 Pmathrm{{Frac}}(ZZ[x]) 投入其中。

如果我们幸运的话,父母可以告诉我们它是如何建造的:

sage: Poly,R = QQ['x'].construction()
sage: Poly,R
(Poly[x], Rational Field)
sage: Fract,R = QQ.construction()
sage: Fract,R
(FractionField, Integer Ring)

在这两种情况下,返回的第一个值 construction() 是一种数学结构,叫做 构造函子 ---看到了吗 ConstructionFunctor . 第二个返回值是应用构造函子的更简单的父级。

作为函子,同样的构造可以应用于同一类别的不同对象:

sage: Poly(QQ) is QQ['x']
True
sage: Poly(ZZ) is ZZ['x']
True
sage: Poly(P) is P['x']
True
sage: Fract(QQ['x'])
Fraction Field of Univariate Polynomial Ring in x over Rational Field

让我们看看这些构造函子是在哪些类别上定义的:

sage: Poly.domain()
Category of rings
sage: Poly.codomain()
Category of rings
sage: Fract.domain()
Category of integral domains
sage: Fract.codomain()
Category of fields

特别地,构造函子可以组成:

sage: Poly*Fract
Poly[x](FractionField(...))
sage: (Poly*Fract)(ZZ) is QQ['x']
True

另外,我们经常假设我们有一个从输入到输出的强制构造函子:

sage: ((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

构造函子不一定通勤:

sage: (Fract*Poly)(ZZ)
Fraction Field of Univariate Polynomial Ring in x over Integer Ring

构造函子的推出

我们现在可以阐明我们的问题了。我们有父母 P_1P_2R ,和构造函子 F_1F_2 ,这样 P_1 = F_1(R)P_2 = F_2(R) . 我们想找到一个新的构造函子 F_3 ,这样两者都 P_1P_2 强迫 P_3 = F_3(R) .

类似于范畴理论的概念, P_3 被称为 pushout() 属于 P_1P_2 ;以及类似的 F_3 被称为推出 F_1F_2 . ::

sage: from sage.categories.pushout import pushout
sage: pushout(Fract(ZZ),Poly(ZZ))
Univariate Polynomial Ring in x over Rational Field

F_1circ F_2F_2circ F_1 很容易被淘汰 F_1F_2 . 但是,函子的顺序必须依赖于规范选择。”不可分解的构造函子有一个 rank ,这样可以对它们进行规范排序:

注解

如果 F1.rank 小于 F2.rank ,然后推出 F_2circ F_1 (因此, F_1 首先应用)。

我们有::

sage: Fract.rank, Poly.rank
(5, 9)

因此,推出的是:

sage: Fract.pushout(Poly), Poly.pushout(Fract)
(Poly[x](FractionField(...)), Poly[x](FractionField(...)))

这就是为什么上面的例子起作用了。

然而,只有“初等”构造函子才有秩:

sage: (Fract*Poly).rank
Traceback (most recent call last):
...
AttributeError: 'CompositeConstructionFunctor' object has no attribute 'rank'
混合结构函子

如果是复合结构的话 ...circ F_2circ F_1...circ G_2circ G_1 被给予,然后Sage决定他们的推出 洗牌 成分:

  • 如果 F1.rank < G1.rank 然后我们申请 F_1 首先,继续 ...circ F_3circ F_2...circ G_2circ G_1 .

  • 如果 F1.rank > G1.rank 然后我们申请 G_1 首先,继续 ...circ F_2circ F_1...circ G_3circ G_2 .

如果 F1.rank == G1.rank ,然后需要用其他方法打破这条领带(见下文)。

作为一个例子,我们首先得到一些函子,然后看看函子链是如何被洗牌的。:

sage: AlgClos, R = CC.construction(); AlgClos
AlgebraicClosureFunctor
sage: Compl, R = RR.construction(); Compl
Completion[+Infinity, prec=53]
sage: Matr, R = (MatrixSpace(ZZ,3)).construction(); Matr
MatrixFunctor
sage: AlgClos.rank, Compl.rank, Fract.rank, Poly.rank, Matr.rank
(3, 4, 5, 9, 10)

当我们申请的时候 FractAlgClosPolyFract 对于整数环,我们得到:

sage: (Fract*Poly*AlgClos*Fract)(ZZ)
Fraction Field of Univariate Polynomial Ring in x over Algebraic Field

当我们申请的时候 ComplMatrPoly 对于整数环,我们得到:

sage: (Poly*Matr*Compl)(ZZ)
Univariate Polynomial Ring in x over Full MatrixSpace of 3 by 3 dense matrices over Integer Ring

应用洗牌程序可以得到:

sage: (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 Algebraic Field

这确实相当于Sage发现的推出:

sage: 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 Algebraic Field
打破平局

如果 F1.rank==G1.rank 然后Sage的推出结构提供了两种方法:

  1. 构造函子有一种方法 merge() 要么回来 None 或者返回一个构造函子--见下文。如果其中之一 F1.merge(G1)G1.merge(F1) 返回构造函子 H_1 ,然后我们申请 H_1 然后继续 ...circ F_3circ F_2...circ G_3circ G_2 .

  2. 构造函子有一种方法 commutes() . 如果任一 F1.commutes(G1)G1.commutes(F1) 收益率 True ,然后两者都适用 F_1G_1 以任何顺序,并继续 ...circ F_3circ F_2...circ G_3circ G_2 .

默认情况下, F1.merge(G1) 收益率 F1 如果 F1==G1 并返回 None 否则。这个 commutes() 方法存在,但似乎到目前为止还没有人实现两个同级的通勤函子。

建立默认实现

的典型应用 merge() 是为了在 不同的实现相同的代数结构 .

注解

如果 F1(P)F2(P) 那么,是不是同一件事的不同实现 F1.merge(F2)(P) 应返回默认实现。

我们希望大胆地将分数字段的玩具实现转换为新的默认实现。因此:

  • 接下来,我们实现一个新版本的“普通”分数域函子,具有相同的秩,但返回我们的新实现。

  • 我们通过merge方法使新实现成为默认实现。

警告

  • 不要覆盖默认值 __call__ 方法 ConstructionFunctor ---实施 _apply_functor 相反。

  • 在初始化过程中声明函子的域和余域。

sage: from sage.categories.pushout import ConstructionFunctor
sage: 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
sage: MyFracFunctor()
MyFracFunctor

我们验证我们的函子真的可以用来构造分数域的实现,并且它可以与它本身或通常的分数域构造函数合并:

sage: MyFracFunctor()(ZZ)
NewFrac(Integer Ring)
sage: MyFracFunctor().merge(MyFracFunctor())
MyFracFunctor
sage: MyFracFunctor().merge(Fract)
MyFracFunctor

关于新的构造函子,我们还有待于让新的分数域知道:

sage: class MyFrac(MyFrac):
....:     def construction(self):
....:         return MyFracFunctor(), self.base()
sage: MyFrac(ZZ['x']).construction()
(MyFracFunctor, Univariate Polynomial Ring in x over Integer Ring)

由于合并,我们有:

sage: pushout(MyFrac(ZZ['x']), Frac(QQ['x']))
NewFrac(Univariate Polynomial Ring in x over Rational Field)

关于性能的第二个注意事项

能够进行涉及不同父元素的运算,并自动创建一个pushout来包含结果,这当然很方便,但是如果速度很重要,就不应该依赖它。简单地将元素转换为不同的父元素需要时间。此外,通过 :trac:`14058` ,弹出可能会受到Python循环垃圾回收的影响。因此,如果没有保持对它的强引用,可能会重复创建同一个父级,这是浪费时间。在下面的例子中,我们说明了由于盲目依赖强制而导致的减速:

sage: ZZxy = ZZ['x','y']
sage: a = ZZxy('x')
sage: b = 1/2
sage: timeit("c = a+b")    # random
10000 loops, best of 3: 172 us per loop
sage: QQxy = QQ['x','y']
sage: timeit("c2 = QQxy(a)+QQxy(b)") # random
10000 loops, best of 3: 168 us per loop
sage: a2 = QQxy(a)
sage: b2 = QQxy(b)
sage: timeit("c2 = a2+b2") # random
100000 loops, best of 3: 10.5 us per loop

因此,如果一个人避免显式或隐式转换为pushout,但立即在pushout中工作,则可以获得10倍以上的速度。

类别框架的测试套件

类别框架不仅提供了功能,而且还提供了一个测试框架。这一节逻辑上属于类别部分,但是如果没有我们在强制部分中实现的位,我们对分数字段的实现就不会通过测试。

“抽象”方法

我们已经在上面看到,一个类别可以要求/建议用户必须/应该实现的某些父或元素方法。这是为了与Sage中已经存在的方法顺利融合。

应该提供的方法称为 abstract_method() . 让我们看看商域及其元素需要什么方法:

sage: from sage.misc.abstract_method import abstract_methods_of_class
sage: abstract_methods_of_class(QuotientFields().parent_class)['optional']
[]
sage: abstract_methods_of_class(QuotientFields().parent_class)['required']
['__contains__']

因此,唯一需要的方法(实际上对于属于集合类别的所有父类都是必需的)是元素包含测试。很好,因为基类 Parent 提供默认的包容测试。

元素必须提供更多:

sage: abstract_methods_of_class(QuotientFields().element_class)['optional']
['_add_', '_mul_']
sage: abstract_methods_of_class(QuotientFields().element_class)['required'] # py2
['__nonzero__', 'denominator', 'numerator']
sage: abstract_methods_of_class(QuotientFields().element_class)['required'] # py3
['__bool__', 'denominator', 'numerator']

因此,这些元素必须提供 denominator()numerator() 方法,并且必须能够判断它们是否为零。基类 Element 提供默认值 __nonzero__() 方法。此外,元素可以提供Sage的单下划线算术方法(实际上是任何环元素) 应该 提供它们)。

这个 _test_... 方法

如果父方法或元素方法的名称以“_test_u”开头,则会在自动测试套件中生成一个测试。例如,对其进行测试

  • 是否为家长 P 实际上是类的父类的实例 P

  • 用户是否实现了所需的抽象方法,

  • 某些定义的结构性质(例如,交换性)是否成立。

例如,如果忘记实现所需的方法,则会得到以下错误:

sage: class Foo(Parent):
....:  Element = sage.structure.element.Element
....:  def __init__(self):
....:      Parent.__init__(self, category=QuotientFields())
sage: Bar = Foo()
sage: bar = Bar.element_class(Bar)
sage: bar._test_not_implemented_methods()
Traceback (most recent call last):
...
AssertionError: Not implemented method: denominator

以下是构成商字段测试套件的测试:

sage: [t for t in dir(QuotientFields().parent_class) if t.startswith('_test_')]
['_test_additive_associativity',
 '_test_an_element',
 '_test_associativity',
 '_test_cardinality',
 '_test_characteristic',
 '_test_characteristic_fields',
 '_test_distributivity',
 '_test_divides',
 '_test_elements',
 '_test_elements_eq_reflexive',
 '_test_elements_eq_symmetric',
 '_test_elements_eq_transitive',
 '_test_elements_neq',
 '_test_euclidean_degree',
 '_test_fraction_field',
 '_test_gcd_vs_xgcd',
 '_test_one',
 '_test_prod',
 '_test_quo_rem',
 '_test_some_elements',
 '_test_zero',
 '_test_zero_divisors']

我们实现了所有的抽象方法(或者从基类继承它们),我们使用类别框架,并且实现了强制。因此,我们确信测试套件运行时不会出错。事实上,确实如此!

注解

下面的技巧 __main__ 模块只在doctest中需要,在交互会话中或在外部定义类时不需要。

sage: __main__.MyFrac = MyFrac
sage: __main__.MyElement = MyElement
sage: P = MyFrac(ZZ['x'])
sage: TestSuite(P).run()

让我们看看实际执行了哪些测试:

sage: TestSuite(P).run(verbose=True)
running ._test_additive_associativity() . . . pass
running ._test_an_element() . . . pass
running ._test_associativity() . . . pass
running ._test_cardinality() . . . pass
running ._test_category() . . . pass
running ._test_characteristic() . . . pass
running ._test_characteristic_fields() . . . pass
running ._test_distributivity() . . . pass
running ._test_divides() . . . pass
running ._test_elements() . . .
  Running the test suite of self.an_element()
  running ._test_category() . . . pass
  running ._test_eq() . . . pass
  running ._test_new() . . . 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_euclidean_degree() . . . pass
running ._test_fraction_field() . . . pass
running ._test_gcd_vs_xgcd() . . . pass
running ._test_new() . . . pass
running ._test_not_implemented_methods() . . . pass
running ._test_one() . . . pass
running ._test_pickling() . . . pass
running ._test_prod() . . . pass
running ._test_quo_rem() . . . pass
running ._test_some_elements() . . . pass
running ._test_zero() . . . pass
running ._test_zero_divisors() . . . pass

使用附加测试实现新类别

正如我们所看到的,测试也在元素上执行。有些方法返回一个元素或一些元素的列表,依赖于大多数代数结构中的“典型”元素。:

sage: P.an_element(); P.some_elements()
(2):(1)
[(2):(1)]

不幸的是,默认方法返回的元素列表的长度为1,并且该单个元素也可能更有趣。元素依赖于方法的方法 _an_element_() ,所以,我们实现它。我们还重写someu elements方法。:

sage: 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())]
sage: P = MyFrac(ZZ['x'])
sage: 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)]

现在,由于我们有了更多有趣的元素,我们还可以为“factor”方法添加一个测试。回想一下,该方法是从类别继承的,但它似乎没有经过测试。

通常,由一个类别定义的方法的测试应该由同一个类别提供。因此,因为 factor 在商字段的类别中定义,则应在那里添加一个测试。但我们不会在这里更改源代码,而是创建一个子类别。

显然,如果 e 是商字段的一个元素,它是 e.factor() 应该等于 e . 为了形成产品,我们使用 prod 方法,这并不奇怪,它是从另一个类别继承的:

sage: P.prod.__module__
'sage.categories.monoids'

当我们想要创建一个子类别时,我们需要提供一个方法 super_categories() ,返回所有立即超类别的列表(这里:商字段的类别)。

警告

子类别 S 属于某一类 Cnot 作为 C.__class__ 你说什么? S 成为 C 只有 S.super_categories() 返回(的子类别) C 你说什么?

类别的父方法和元素方法是作为属性的类的方法提供的 ParentMethodsElement Methods 分类如下:

sage: from sage.categories.category import Category
sage: class QuotientFieldsWithTest(Category): # do *not* inherit from QuotientFields, but ...
....:     def super_categories(self):
....:         return [QuotientFields()]       # ... declare QuotientFields as a super category!
....:     class ParentMethods:
....:         pass
....:     class ElementMethods:
....:         def _test_factorisation(self, **options):
....:             P = self.parent()
....:             assert self == P.prod([P(b)**e for b,e in self.factor()])

我们提供了一个新类别的商字段实现实例。注意类别有一个默认值 _repr_ 方法,该方法根据类的名称猜测良好的字符串表示形式: QuotientFieldsWithTest 变成“带测试的商字段”。

注解

下面的技巧 __main__ 模块只在doctest中需要,在交互会话中或在外部定义类时不需要。

sage: __main__.MyFrac = MyFrac
sage: __main__.MyElement = MyElement
sage: __main__.QuotientFieldsWithTest = QuotientFieldsWithTest
sage: P = MyFrac(ZZ['x'], category=QuotientFieldsWithTest())
sage: P.category()
Category of quotient fields with test

新测试继承自类别。因为 an_element() 返回一个复杂的元素, _test_factorisation 是一个严峻的考验:

sage: P.an_element()._test_factorisation
<bound method MyFrac_with_category.element_class._test_factorisation of (x^2):(x^3 + 3*x^2 + 3*x + 1)>
sage: P.an_element().factor()
(x + 1)^-3 * x^2

最后,我们观察到新测试已经自动成为测试套件的一部分。我们注意到,自从我们 sage.structure.parent.Parent.an_element() 返回更有趣的东西。:

sage: TestSuite(P).run(verbose=True)
running ._test_additive_associativity() . . . pass
running ._test_an_element() . . . pass
running ._test_associativity() . . . pass
running ._test_cardinality() . . . pass
running ._test_category() . . . pass
running ._test_characteristic() . . . pass
running ._test_characteristic_fields() . . . pass
running ._test_distributivity() . . . pass
running ._test_divides() . . . 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_new() . . . 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_euclidean_degree() . . . pass
running ._test_fraction_field() . . . pass
running ._test_gcd_vs_xgcd() . . . pass
running ._test_new() . . . pass
running ._test_not_implemented_methods() . . . pass
running ._test_one() . . . pass
running ._test_pickling() . . . pass
running ._test_prod() . . . pass
running ._test_quo_rem() . . . pass
running ._test_some_elements() . . . pass
running ._test_zero() . . . pass
running ._test_zero_divisors() . . . pass

附录:完整代码

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
# Importing base classes, ...
import sage
from sage.rings.ring import Field
from sage.structure.element import FieldElement
from sage.categories.category import Category
# ... the UniqueRepresentation tool,
from sage.structure.unique_representation import UniqueRepresentation
# ... some categories, and ...
from sage.categories.fields import Fields
from sage.categories.quotient_fields import QuotientFields
from sage.categories.integral_domains import IntegralDomains
# construction functors
from sage.categories.pushout import ConstructionFunctor

# Fraction field elements
class MyElement(FieldElement):
    def __init__(self, parent, n, d=None):
        if parent is None:
            raise ValueError("The parent must be provided")
        B = parent.base()
        if d is None:
            # The default denominator is one
            d = B.one()
        # verify that both 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)
        # Numerator and denominator should not just be "in" B,
        # but should be defined as elements of B
        d = B(d)
        n = B(n)
        # the denominator must not be zero
        if d==0:
            raise ZeroDivisionError("The denominator must not be zero")
        # normalize the denominator: WLOG, it shall be non-negative.
        if d<0:
            self.n = -n
            self.d = -d
        else:
            self.n = n
            self.d = d
        FieldElement.__init__(self,parent)

    # Methods required by the category of fraction fields:
    def numerator(self):
        return self.n
    def denominator(self):
        return self.d

    # String representation (single underscore!)
    def _repr_(self):
        return "(%s):(%s)"%(self.n,self.d)

    # Comparison: We can assume that both arguments are coerced
    # into the same parent, which is a fraction field. Hence, we
    # are allowed to use the denominator() and numerator() methods
    # on the second argument.
    def _richcmp_(self, other, op):
        from sage.structure.richcmp import richcmp
        return richcmp(self.n*other.denominator(), other.numerator()*self.d, op)

    # Arithmetic methods, single underscore. We can assume that both
    # arguments are coerced into the same parent.
    # We return instances of self.__class__, because self.__class__ will
    # eventually be a sub-class of MyElement.
    def _add_(self, other):
        C = self.__class__
        D = self.d*other.denominator()
        return C(self.parent(), self.n*other.denominator()+self.d*other.numerator(),D)
    def _sub_(self, other):
        C = self.__class__
        D = self.d*other.denominator()
        return C(self.parent(), self.n*other.denominator()-self.d*other.numerator(),D)
    def _mul_(self, other):
        C = self.__class__
        return C(self.parent(), self.n*other.numerator(), self.d*other.denominator())
    def _div_(self, other):
        C = self.__class__
        return C(self.parent(), self.n*other.denominator(), self.d*other.numerator())

# Inheritance from UniqueRepresentation implements the unique parent
# behaviour. Moreover, it implements pickling (provided that Python
# succeeds to look up the class definition).
class MyFrac(UniqueRepresentation, Field):
    # Implement the category framework for elements, which also
    # makes some basic conversions work.
    Element = MyElement

    # Allow to pass to a different category, by an optional argument
    def __init__(self, base, category=None):
        # Fraction fields only exist for integral domains
        if base not in IntegralDomains():
            raise ValueError("%s is no integral domain" % base)
        # Implement the category framework for the parent
        Field.__init__(self, base, category=category or QuotientFields())

    # Single-underscore method for string representation
    def _repr_(self):
        return "NewFrac(%s)"%repr(self.base())

    # Two methods that are implicitly used in some tests
    def base_ring(self):
        return self.base().base_ring()
    def characteristic(self):
        return self.base().characteristic()

    # Implement conversions. Do not override __call__!
    def _element_constructor_(self, *args, **kwds):
        if len(args)!=1:
           return self.element_class(self, *args, **kwds)
        x = args[0]
        try:
            P = x.parent()
        except AttributeError:
            return self.element_class(self, x, **kwds)
        if P in QuotientFields() and P != self.base():
            return self.element_class(self, x.numerator(), x.denominator(), **kwds)
        return self.element_class(self, x, **kwds)

    # Implement coercion from the base and from fraction fields
    # over a ring that coerces into the base
    def _coerce_map_from_(self, S):
        if self.base().has_coerce_map_from(S):
            return True
        if S in QuotientFields():
            if self.base().has_coerce_map_from(S.base()):
                return True
            if hasattr(S,'ring_of_integers') and self.base().has_coerce_map_from(S.ring_of_integers()):
                return True
    # Tell how this parent was constructed, in order to enable pushout constructions
    def construction(self):
        return MyFracFunctor(), self.base()

    # return some elements of this parent
    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())]


# A construction functor for our implementation of fraction fields
class MyFracFunctor(ConstructionFunctor):
    # The rank is the same for Sage's original fraction field functor
    rank = 5
    def __init__(self):
        # The fraction field construction is a functor
        # from the category of integral domains into the category of
        # fields
        # NOTE: We could actually narrow the codomain and use the
        # category QuotientFields()
        ConstructionFunctor.__init__(self, IntegralDomains(), Fields())
    # Applying the functor to an object. Do not override __call__!
    def _apply_functor(self, R):
        return MyFrac(R)
    # Note: To apply the functor to morphisms, implement
    #       _apply_functor_to_morphism

    # Make sure that arithmetic involving elements of Frac(R) and
    # MyFrac(R) works and yields elements of MyFrac(R)
    def merge(self, other):
        if isinstance(other, (type(self), sage.categories.pushout.FractionField)):
            return self

# A quotient field category with additional tests.
# Notes:
# - Category inherits from UniqueRepresentation. Hence, there
#   is only one category for given arguments.
# - Since QuotientFieldsWithTest is a singleton (there is only
#   one instance of this class), we could inherit from
#   sage.categories.category_singleton.Category_singleton
#   rather than from sage.categories.category.Category
class QuotientFieldsWithTest(Category):
    # Our category is a sub-category of the category of quotient fields,
    # by means of the following method.
    def super_categories(self):
        return [QuotientFields()]

    # Here, we could implement methods that are available for
    # all objects in this category.
    class ParentMethods:
        pass

    # Here, we add a new test that is available for all elements
    # of any object in this category.
    class ElementMethods:
        def _test_factorisation(self, **options):
            P = self.parent()
            # The methods prod() and factor() are inherited from
            # some other categories.
            assert self == P.prod([P(b)**e for b,e in self.factor()])