Set factories


A set factory \(F\) is a device for constructing some Parent \(P\) that models subsets of a big set \(S\). Typically, each such parent is constructed as the subset of \(S\) of all elements satisfying a certain collection of constraints \(cons\). In such a hierarchy of subsets, one needs an easy and flexible control on how elements are constructed. For example, one may want to construct the elements of \(P\) in some subclass of the class of the elements of \(S\). On other occasions, one also often needs \(P\) to be a facade parent, whose elements are represented as elements of \(S\) (see FacadeSets).

The role of a set factory is twofold:

  • Manage a database of constructors for the different parents \(P = F(cons)\) depending on the various kinds of constraints \(cons\). Note: currently there is no real support for that. We are gathering use cases before fixing the interface.
  • Ensure that the elements \(e = P(...)\) created by the different parents follows a consistent policy concerning their class and parent.

Basic usage: constructing parents through a factory

The file sage.structure.set_factories_example shows an example of a SetFactory together with typical implementation. Note that the written code is intentionally kept minimal, many things and in particular several iterators could be written in a more efficient way.

Consider the set \(S\) of couples \((x,y)\) with \(x\) and \(y\) in \(I:=\{0,1,2,3,4\}\). We represent an element of \(S\) as a 2-elements tuple, wrapped in a class XYPair deriving from ElementWrapper. You can create a XYPair with any Parent:

sage: from sage.structure.set_factories import *
sage: from sage.structure.set_factories_example import *
sage: p = XYPair(Parent(), (0,1)); p
(0, 1)

Now, given \((a, b)\in S\) we want to consider the following subsets of \(S\)

\[ \begin{align}\begin{aligned}S_a := \{(x,y) \in S \mid x = a\},\\S^b := \{(x,y) \in S \mid y = b\},\\S_a^b := \{(x,y) \in S \mid x = a, y = b\}.\end{aligned}\end{align} \]

The constraints considered here are admittedly trivial. In a realistic example, there would be much more of them. And for some sets of constraints no good enumeration algorithms would be known.

In Sage, those sets are constructed by passing the constraints to the factory. We first create the set with no constraints at all:

sage: XYPairs
Factory for XY pairs
sage: S = XYPairs(); S.list()
[(0, 0), (1, 0), ..., (4, 0), (0, 1), (1, 1), ..., (3, 4), (4, 4)]
sage: S.cardinality()
25

Let us construct \(S_2\), \(S^3\) and \(S_2^3\):

sage: Sx2 = XYPairs(x=2); Sx2.list()
[(2, 0), (2, 1), (2, 2), (2, 3), (2, 4)]
sage: Sy3 = XYPairs(y=3); Sy3.list()
[(0, 3), (1, 3), (2, 3), (3, 3), (4, 3)]
sage: S23 = XYPairs(x=2, y=3); S23.list()
[(2, 3)]

Set factories provide an alternative way to build subsets of an already constructed set: each set constructed by a factory has a method subset() which accept new constraints. Sets constructed by the factory or the subset() methods are identical:

sage: Sx2s = S.subset(x=2); Sx2 is Sx2s
True
sage: Sx2.subset(y=3) is S23
True

It is not possible to change an already given constraint:

sage: S23.subset(y=5)
Traceback (most recent call last):
...
ValueError: Duplicate value for constraints 'y': was 3 now 5

Constructing custom elements: policies

We now come to the point of factories: constructing custom elements. The writer of XYPairs() decided that, by default, the parents Sx2, Sy3 and S23 are facade for parent S. This means that each element constructed by those subsets behaves as if they where directly constructed by S itself:

sage: Sx2.an_element().parent()
AllPairs
sage: el = Sx2.an_element()
sage: el.parent() is S
True
sage: type(el) is S.element_class
True

This is not always desirable. The device which decides how to construct an element is called a policy (see SetFactoryPolicy). Each factory should have a default policy. Here is the policy of XYPairs():

sage: XYPairs._default_policy
Set factory policy for <class 'sage.structure.set_factories_example.XYPair'> with parent AllPairs[=Factory for XY pairs(())]

This means that with the current policy, the parent builds elements with class XYPair and parent AllPairs which is itself constructed by calling the factory XYPairs() with constraints (). There is a lot of flexibility to change that. We now illustrate how to make a few different choices.

1 - In a first use case, we want to add some methods to the constructed elements. As illustration, we add here a new method sum which returns \(x+y\). We therefore create a new class for the elements which inherits from XYPair:

sage: class NewXYPair(XYPair):
....:     def sum(self):
....:         return sum(self.value)

Here is an instance of this class (with a dummy parent):

sage: el = NewXYPair(Parent(), (2,3))
sage: el.sum()
5

We now want to have subsets generating those new elements while still having a single real parent (the one with no constraint) for each element. The corresponding policy is called TopMostParentPolicy. It takes three parameters:

  • the factory;
  • the parameters for void constraint;
  • the class used for elements.

Calling the factory with this policy returns a new set which builds its elements with the new policy:

sage: new_policy = TopMostParentPolicy(XYPairs, (), NewXYPair)
sage: NewS = XYPairs(policy=new_policy)
sage: el = NewS.an_element(); el
(0, 0)
sage: el.sum()
0
sage: el.parent() is NewS
True
sage: isinstance(el, NewXYPair)
True

Newly constructed subsets inherit the policy:

sage: NewS2 = NewS.subset(x=2)
sage: el2 = NewS2.an_element(); el2
(2, 0)
sage: el2.sum()
2
sage: el2.parent() is NewS
True

2 - In a second use case, we want the elements to remember which parent created them. The corresponding policy is called SelfParentPolicy. It takes only two parameters:

  • the factory;
  • the class used for elements.

Here is an example:

sage: selfpolicy = SelfParentPolicy(XYPairs, NewXYPair)
sage: SelfS = XYPairs(policy=selfpolicy)
sage: el = SelfS.an_element()
sage: el.parent() is SelfS
True

Now all subsets are the parent of the elements that they create:

sage: SelfS2 = SelfS.subset(x=2)
sage: el2 = SelfS2.an_element()
sage: el2.parent() is NewS
False
sage: el2.parent() is SelfS2
True

3 - Finaly, a common use case is to construct simple python object which are not Sage sage.structure.Element. As an example, we show how to build a parent TupleS which construct pairs as tuple. The corresponding policy is called BareFunctionPolicy. It takes two parameters:

  • the factory;
  • the function called to construct the elements.

Here is how to do it:

sage: cons = lambda t, check: tuple(t) # ignore the check parameter
sage: tuplepolicy = BareFunctionPolicy(XYPairs, cons)
sage: P = XYPairs(x=2, policy=tuplepolicy)
sage: P.list()
[(2, 0), (2, 1), (2, 2), (2, 3), (2, 4)]
sage: el = P.an_element()
sage: type(el)
<... 'tuple'>

Here are the currently implemented policies:

  • FacadeParentPolicy: reuse an existing parent together with its element_class
  • TopMostParentPolicy: use a parent created by the factory itself and provide a class Element for it. In this case, we need to specify the set of constraints which build this parent taking the ownership of all elements and the class which will be used for the Element.
  • SelfParentPolicy: provide systematically Element and element_class and ensure that the parent is self.
  • BareFunctionPolicy: instead of calling a class constructor element are passed to a function provided to the policy.

Todo

Generalize TopMostParentPolicy to be able to have several topmost parents.

Technicalities: how policies inform parents

Parents built from factories should inherit from ParentWithSetFactory. This class provide a few methods related to factories and policies. The __init__ method of ParentWithSetFactory must be provided with the set of constraints and the policy. A parent built from a factory must create elements through a call to the method _element_constructor_. The current way in which policies inform parents how to builds their elements is set by a few attributes. So the class must accept attribute adding. The precise details of which attributes are set may be subject to change in the future.

How to write a set factory

See also

set_factories_example for an example of a factory.

Here are the specifications:

A parent built from a factory should

  • inherit from ParentWithSetFactory. It should accept a policy argument and pass it verbatim to the __init__ method of ParentWithSetFactory together with the set of constraints;
  • create its elements through calls to the method _element_constructor_;
  • define a method ParentWithSetFactory.check_element which checks if a built element indeed belongs to it. The method should accept an extra keyword parameter called check specifying which level of check should be performed. It will only be called when bool(check) evaluates to True.

The constructor of the elements of a parent from a factory should:

  • receive the parent as first mandatory argument;
  • accept an extra optional keyword parameter called check which is meant to tell if the input must be checked or not. The precise meaning of check is intentionally left vague. The only intent is that if bool(check) evaluates to False, no check is performed at all.

A factory should

  • define a method __call__ which is responsible for calling the appropriate parent constructor given the constraints;
  • define a method overloading SetFactory.add_constraints() which is responsible of computing the union of two sets of constraints;
  • optionally define a method or an attribute _default_policy passed to the ParentWithSetFactory if no policy is given to the factory.

Todo

There is currently no support for dealing with sets of constraints. The set factory and the parents must cooperate to consistently handle them. More support, together with a generic mechanism to select the appropriate parent class from the constraints, will be added as soon as we have gathered sufficiently enough use-cases.

AUTHORS:

  • Florent Hivert (2011-2012): initial revision
class sage.structure.set_factories.BareFunctionPolicy(factory, constructor)

Bases: sage.structure.set_factories.SetFactoryPolicy

Policy where element are constructed using a bare function.

INPUT:

  • factory – an instance of SetFactory
  • constructor – a function

Given a factory F and a function c, returns a policy for parent P creating element using the function f.

EXAMPLES:

sage: from sage.structure.set_factories import BareFunctionPolicy
sage: from sage.structure.set_factories_example import XYPairs
sage: cons = lambda t, check: tuple(t) # ignore the check parameter
sage: tuplepolicy = BareFunctionPolicy(XYPairs, cons)
sage: P = XYPairs(x=2, policy=tuplepolicy)
sage: el = P.an_element()
sage: type(el)
<... 'tuple'>
element_constructor_attributes(constraints)

Return the element constructor attributes as per SetFactoryPolicy.element_constructor_attributes().

INPUT:

  • constraints – a bunch of constraints
class sage.structure.set_factories.FacadeParentPolicy(factory, parent)

Bases: sage.structure.set_factories.SetFactoryPolicy

Policy for facade parent.

INPUT:

Given a factory F and a class E, returns a policy for parent P creating elements as if they were created by parent.

EXAMPLES:

sage: from sage.structure.set_factories import SelfParentPolicy, FacadeParentPolicy
sage: from sage.structure.set_factories_example import XYPairs, XYPair

We create a custom standard parent P:

sage: selfpolicy = SelfParentPolicy(XYPairs, XYPair)
sage: P = XYPairs(x=2, policy=selfpolicy)
sage: pol = FacadeParentPolicy(XYPairs, P)
sage: P2 = XYPairs(x=2, y=3, policy=pol)
sage: el = P2.an_element()
sage: el.parent() is P
True
sage: type(el) is P.element_class
True

If parent is itself a facade parent, then transitivity is correctly applied:

sage: P =  XYPairs()
sage: P2 = XYPairs(x=2)
sage: P2.category()
Category of facade finite enumerated sets
sage: pol = FacadeParentPolicy(XYPairs, P)
sage: P23 = XYPairs(x=2, y=3, policy=pol)
sage: el = P2.an_element()
sage: el.parent() is P
True
sage: type(el) is P.element_class
True
element_constructor_attributes(constraints)

Return the element constructor attributes as per SetFactoryPolicy.element_constructor_attributes().

INPUT:

  • constraints – a bunch of constraints
class sage.structure.set_factories.ParentWithSetFactory(constraints, policy, category=None)

Bases: sage.structure.parent.Parent

Abstract class for parent belonging to a set factory.

INPUT:

  • constraints – a set of constraints
  • policy – the policy for element construction
  • category – the category of the parent (default to None)

Depending on the constraints and the policy, initialize the parent in a proper category to set up element construction.

EXAMPLES:

sage: from sage.structure.set_factories_example import XYPairs, PairsX_
sage: P = PairsX_(3, XYPairs._default_policy)
sage: P is XYPairs(3)
True
sage: P.category()
Category of facade finite enumerated sets
check_element(x, check)

Check that x verifies the constraints of self.

INPUT:

  • x – an instance of self.element_class.
  • check – the level of checking to be performed (usually a boolean).

This method may assume that x was properly constructed by self or a possible super-set of self for which self is a facade. It should return nothing if x verifies the constraints and raise a ValueError explaining which constraints x fails otherwise.

The method should accept an extra parameter check specifying which level of check should be performed. It will only be called when bool(check) evaluates to True.

Todo

Should we always call check element and let it decide which check has to be performed ?

EXAMPLES:

sage: from sage.structure.set_factories_example import XYPairs
sage: S = XYPairs()
sage: el = S((2,3))
sage: S.check_element(el, True)
sage: XYPairs(x=2).check_element(el, True)
sage: XYPairs(x=3).check_element(el, True)
Traceback (most recent call last):
...
ValueError: Wrong first coordinate
sage: XYPairs(y=4).check_element(el, True)
Traceback (most recent call last):
...
ValueError: Wrong second coordinate
constraints()

Return the constraints defining self.

Note

Currently there is no specification on how constraints are passed as arguments.

EXAMPLES:

sage: from sage.structure.set_factories_example import XYPairs
sage: XYPairs().constraints()
()
sage: XYPairs(x=3).constraints()
(3, None)
sage: XYPairs(y=2).constraints()
(None, 2)
facade_policy()

Return the policy for parent facade for self.

EXAMPLES:

sage: from sage.structure.set_factories import SelfParentPolicy
sage: from sage.structure.set_factories_example import XYPairs, XYPair

We create a custom standard parent P:

sage: selfpolicy = SelfParentPolicy(XYPairs, XYPair)
sage: P = XYPairs(x=2, policy=selfpolicy)
sage: P.facade_policy()
Set factory policy for facade parent {(2, b) | b in range(5)}

Now passing P.facade_policy() creates parent which are facade for P:

sage: P3 = XYPairs(x=2, y=3, policy=P.facade_policy())
sage: P3.facade_for() == (P,)
True
sage: el = P3.an_element()
sage: el.parent() is P
True
factory()

Return the factory which built self.

EXAMPLES:

sage: from sage.structure.set_factories_example import XYPairs
sage: XYPairs().factory() is XYPairs
True
sage: XYPairs(x=3).factory() is XYPairs
True
policy()

Return the policy used when self was created.

EXAMPLES:

sage: from sage.structure.set_factories_example import XYPairs
sage: XYPairs().policy()
Set factory policy for <class 'sage.structure.set_factories_example.XYPair'> with parent AllPairs[=Factory for XY pairs(())]
sage: XYPairs(x=3).policy()
Set factory policy for <class 'sage.structure.set_factories_example.XYPair'> with parent AllPairs[=Factory for XY pairs(())]
subset(*args, **options)

Return a subset of self by adding more constraints.

Note

Currently there is no specification on how constraints are passed as arguments.

EXAMPLES:

sage: from sage.structure.set_factories_example import XYPairs
sage: S = XYPairs()
sage: S3 = S.subset(x=3)
sage: S3.list()
[(3, 0), (3, 1), (3, 2), (3, 3), (3, 4)]
class sage.structure.set_factories.SelfParentPolicy(factory, Element)

Bases: sage.structure.set_factories.SetFactoryPolicy

Policy where each parent is a standard parent.

INPUT:

Given a factory F and a class E, returns a policy for parent P creating elements in class E and parent P itself.

EXAMPLES:

sage: from sage.structure.set_factories import SelfParentPolicy
sage: from sage.structure.set_factories_example import XYPairs, XYPair, Pairs_Y
sage: pol = SelfParentPolicy(XYPairs, XYPair)
sage: S = Pairs_Y(3, pol)
sage: el = S.an_element()
sage: el.parent() is S
True

sage: class Foo(XYPair): pass
sage: pol = SelfParentPolicy(XYPairs, Foo)
sage: S = Pairs_Y(3, pol)
sage: el = S.an_element()
sage: isinstance(el, Foo)
True
element_constructor_attributes(constraints)

Return the element constructor attributes as per SetFactoryPolicy.element_constructor_attributes()

INPUT:

  • constraints – a bunch of constraints
class sage.structure.set_factories.SetFactory

Bases: sage.structure.unique_representation.UniqueRepresentation, sage.structure.sage_object.SageObject

This class is currently just a stub that we will be using to add more structures on factories.

add_constraints(cons, *args, **opts)

Add constraints to the set of constraints \(cons\).

Should return a set of constraints.

Note

Currently there is no specification on how constraints are passed as arguments.

EXAMPLES:

sage: from sage.structure.set_factories_example import XYPairs
sage: XYPairs.add_constraints((3,),((None, 2), {}))
(3, 2)

sage: XYPairs.add_constraints((3,),((None, None), {'y': 2}))
(3, 2)
class sage.structure.set_factories.SetFactoryPolicy(factory)

Bases: sage.structure.unique_representation.UniqueRepresentation, sage.structure.sage_object.SageObject

Abstract base class for policies.

A policy is a device which is passed to a parent inheriting from ParentWithSetFactory in order to set-up the element construction framework.

INPUT:

Warning

This class is a base class for policies, one should not try to create instances.

element_constructor_attributes(constraints)

Element constructor attributes.

INPUT:

  • constraints – a bunch of constraints

Should return the attributes that are prerequisite for element construction. This is coordinated with ParentWithSetFactory._element_constructor_(). Currently two standard attributes are provided in facade_element_constructor_attributes() and self_element_constructor_attributes(). You should return the one needed depending on the given constraints.

EXAMPLES:

sage: from sage.structure.set_factories_example import XYPairs, XYPair
sage: pol = XYPairs._default_policy
sage: pol.element_constructor_attributes(())
{'Element': <class 'sage.structure.set_factories_example.XYPair'>,
 '_parent_for': 'self'}
sage: pol.element_constructor_attributes((1))
{'_facade_for': AllPairs,
 '_parent_for': AllPairs,
 'element_class': <class 'sage.structure.set_factories_example.AllPairs_with_category.element_class'>}
facade_element_constructor_attributes(parent)

Element Constructor Attributes for facade parent.

The list of attributes which must be set during the init of a facade parent with factory.

INPUT:

  • parent – the actual parent for the elements

EXAMPLES:

sage: from sage.structure.set_factories_example import XYPairs, XYPair
sage: pol = XYPairs._default_policy
sage: pol.facade_element_constructor_attributes(XYPairs())
{'_facade_for': AllPairs,
 '_parent_for': AllPairs,
 'element_class': <class 'sage.structure.set_factories_example.AllPairs_with_category.element_class'>}
factory()

Return the factory for self.

EXAMPLES:

sage: from sage.structure.set_factories import SetFactoryPolicy, SelfParentPolicy
sage: from sage.structure.set_factories_example import XYPairs, XYPair
sage: XYPairs._default_policy.factory()
Factory for XY pairs
sage: XYPairs._default_policy.factory() is XYPairs
True
self_element_constructor_attributes(Element)

Element Constructor Attributes for non facade parent.

The list of attributes which must be set during the init of a non facade parent with factory.

INPUT:

  • Element – the class used for the elements

EXAMPLES:

sage: from sage.structure.set_factories_example import XYPairs, XYPair
sage: pol = XYPairs._default_policy
sage: pol.self_element_constructor_attributes(XYPair)
{'Element': <class 'sage.structure.set_factories_example.XYPair'>,
 '_parent_for': 'self'}
class sage.structure.set_factories.TopMostParentPolicy(factory, top_constraints, Element)

Bases: sage.structure.set_factories.SetFactoryPolicy

Policy where the parent of the elements is the topmost parent.

INPUT:

  • factory – an instance of SetFactory
  • top_constraints – the empty set of constraints.
  • Element – a subclass of Element

Given a factory F and a class E, returns a policy for parent P creating element in class E and parent factory(*top_constraints, policy).

EXAMPLES:

sage: from sage.structure.set_factories_example import XYPairs, XYPair
sage: P = XYPairs(); P.policy()
Set factory policy for <class 'sage.structure.set_factories_example.XYPair'> with parent AllPairs[=Factory for XY pairs(())]
element_constructor_attributes(constraints)

Return the element constructor attributes as per SetFactoryPolicy.element_constructor_attributes().

INPUT:

  • constraints – a bunch of constraints