Source code for libutilitaspy.categories.categories

"""
This module is provides a representation for categories from Category Theory.

For a definition of categories, see
    http://en.wikipedia.org/wiki/Category_theory 
and
    http://en.wikipedia.org/wiki/Category_(mathematics)
"""

from libutilitaspy.metaclassconfig import MetaClass
from libutilitaspy.data_structures.graphs import Node, Edge, Graph
import diagrams


[docs]class Object(Node): """ Instances of this class represent objects in some category. """ __metaclass__ = MetaClass def __init__(self, obj=None, category=None): Node.__init__(self, obj) assert isinstance(category, Category) category.add_object(self) def valid(self): assert isinstance(self.category, Category) return self.category.valid_object(self) def __eq__(self, other): return self.obj == other.obj def __hash__(self): return hash(self.obj)
[docs]class Arrow(Edge): """ Instances of this class represent arrows or morphisms between objects in some category. """ __metaclass__ = MetaClass def __init__(self, source, target, label=None, category=None): assert isinstance(category, Category) assert isinstance(source, Object) assert isinstance(target, Object) Edge.__init__(self, source, target, label) category.add_arrow(self) def valid(self): assert isinstance(self.category, Category) return self.category.valid_arrow(self) # def __call__(self, arg): # """This method should be overriden. It is intended to 'apply' the # arrow to an element of the source, when the source can be seen as a set # and the arrow as a function. # # This is optional, as not all arrows are 'functional'. # """ # pass #
[docs] def dual(self): """Warning: this does not compute inverse functions.""" return Arrow(self.target, self.source)
[docs] def compose(self, other): """ Returns the composition of this arrow with another arrow, where this arrow goes first. :param Arrow other: some arrow :returns: self.category.composite(self, other) """ return self.category.composite(self, other)
def __mul__(self, other): """ Returns the composition of this arrow with another arrow, where the other arrow goes first. :param Arrow other: some arrow :returns: self.category.composite(other, self) """ return other.compose(self) def __rshift__(self, other): """ Returns the composition of this arrow with another arrow, where this arrow goes first. :param Arrow other: some arrow :returns: self.category.composite(self, other) """ return self.compose(other) def __eq__(self, other): """This should be overriden in cases where a weaker equivalence is required or desired. E.g. function equality.""" return id(self) == id(other) def __hash__(self): return id(self)
[docs]class Category(object): """ Instances of this class are intended to represent categories. A category consists of: 1) a class :math:`O` of objects :math:`A, B, ...` 2) a class :math:`M` of arrows (or morphisms) between objects :math:`f, g, ...` where :math:`f:A \\to B` is an arrow with source :math:`A` and target :math:`B`, in which case we define :math:`src(f) = A` and :math:`trg(f) = B` 3) a composition operation :math:`\\circ` between arrows 4) an 'identity' arrow :math:`{id}_{A}` for each object :math:`A` And it must satisfy the following: 1) for every pair of arrows :math:`f` and :math:`g`, if the target of :math:`f` is the source of :math:`g`, then their composition, written :math:`g \\circ f`, exists, and is an arrow whose source is the source of :math:`f` and whose target is the target of :math:`g`. In short: if :math:`f:A \\to B \\in M` and :math:`g:B \\to C \\in M` then :math:`g \\circ f:A \\to C \\in M` 2) for each object :math:`A`, the identity arrow :math:`{id}_{A}:A \\to A` is the identity with respect to composition. This is, a) for any arrow :math:`f:A \\to B \\in M`, :math:`f \\circ {id}_{A} = f` b) for any arrow :math:`g:B \\to A \\in M`, :math:`{id}_{A} \\circ g = g` 3) Composition is associative: for any arrows :math:`f:A \\to B`, :math:`g:B \\to C`, :math:`h:C \\to D` :math:`f \\circ (g \\circ h) = (f \\circ g) \\circ h` Instances of the Category class are intended to implement these categories, where objects are any Python objects and arrows are instances of the Arrow class (or any subclass). This class is intended to be subclassed. In particular, a subclass should implement the `composition` and `identity` methods. Then to obtain the composition, a user calls the :py:meth:`composite` method and to obtaind the identity, the user calls the :py:meth:`ident` method of this class. The :py:meth:`composite` method is normally called via the :py:meth:`Arrow.__mul__` method so if :math:`f:A \\to B \\in M` and :math:`g:B \\to C \\in M` then we can obtain :math:`g \\circ f:A \\to C \\in M` by calling:: g * f instead of:: cat.composite(f,g) """ __metaclass__ = MetaClass def __init__(self, object_class, arrow_class): #, composition=None, identity=None): """ The constructor creates a category whose objects and arrows belong to the given classes. :param object_class: :type object_class: subclass of :py:class:`Object` :param arrow_class: :type arrow_class: subclass of :py:class:`Arrow` """ assert issubclass(object_class, Object) assert issubclass(arrow_class, Arrow) self.object_class = object_class self.arrow_class = arrow_class self.mem_comp = {} # A table to cache arrow compositions; indexed by pairs of composite arrows: self.mem[f,g] = f * g self.mem_id = {} # A table to cache identity arrows; indexed by object def valid_object(self, obj): return type(obj) == self.object_class def valid_arrow(self, f): return type(f) == self.arrow_class \ and type(f.source) == self.object_class \ and type(f.target) == self.object_class
[docs] def composite(self, f, g, memoize=True): """Returns the arrow g * f. Note that this intends to be f first, then g: f: A -> B and g: B -> C, then g * f == f >> g : A -> C Note: it does not apply the composition, just computes and returns the composite arrow.""" if memoize and (f,g) in self.mem_comp: return self.mem_comp[f,g] assert self.valid_arrow(f) assert self.valid_arrow(g) assert f.target == g.source c = self.composition(f,g) assert self.valid_arrow(c) assert c.source == f.source assert c.target == g.target if memoize: self.mem_comp[f, g] = c return c
[docs] def ident(self, obj, memoize=True): """Returns the identity arrow of the object given. This method however, does not check that the arrow is indeed the identity. """ if memoize and obj in self.mem_id[obj]: return self.mem_id[obj] assert self.valid_object(obj) i = self.identity(obj) assert self.valid_arrow(i) assert i.source == i.target if memoize: self.mem_id[obj] = i return i
[docs] def hom(self, A, B): """Should return the set of all arrows between A and B""" pass
def source(self, arrow): return arrow.source def target(self, arrow): return arrow.target def commute(self, f, g, h): assert self.valid_arrow(f) assert self.valid_arrow(g) assert self.valid_arrow(h) return h == g * f def is_identity(self, f): return self.valid_arrow(f) \ and f.source == f.target \ and f in self.mem_id[f.source] def limit(self, diagram): return diagram.limit() def final(self): return diagrams.Empty(self).final() def product(self, A, B): return diagrams.Pair(A, B, self).limit() def equalizer(self, f, g): return diagrams.ParallelArrows(f, g, self).limit() def pullback(self, f, g): assert isinstance(f, Arrow) assert isinstance(g, Arrow) assert f.target == g.target C = f.target return diagrams.CoSpan(C, [f,g], self).limit()
[docs] def colimit(self, diagram): """Abstract method: should compute the colimit of the diagram in the category.""" return diagram.colimit()
def initial(self): return diagrams.Empty(self).initial() def coproduct(self, A, B): return diagrams.Pair(A, B, self).colimit() def coequalizer(self, f, g): return diagrams.ParallelArrows(f, g, self).colimit() def pushout(self, f, g): assert isinstance(f, Arrow) assert isinstance(g, Arrow) assert f.source == g.source C = f.source return diagrams.Span(C, [f,g], self).colimit() def is_initial(self, obj): pass def is_final(self, obj): pass
[docs]class FiniteCategory(Category, Graph): """ Instances of this subclass of :py:class:`Category` make the assumption that the sets of objects and arrows are finite. """ __metaclass__ = MetaClass def __init__(self, object_class, arrow_class, objects=None, arrows=None): #, composition=None, identity=None): if objects is None: objects = [] if arrows is None: arrows = [] assert all(isinstance(obj, object_class) for obj in objects) assert all(isinstance(arr, arrow_class) for arr in arrows) Category.__init__(self, object_class, arrow_class) #, composition, identity) Graph.__init__(self, objects, arrows) self.objects = self.nodes self.arrows = self.edges assert set(objects) >= set(f.source for f in arrows) | set(f.target for f in arrows) self.close() def add_object(self, obj): assert isinstance(obj, Object) assert Category.valid_object(self, obj) self.add_node(obj) obj.category = self def add_arrow(self, arrow): assert isinstance(arrow, Arrow) assert Category.valid_arrow(self, arrow) self.add_edge(arrow) arrow.category = self def valid_object(self, obj): return Category.valid_object(self, obj) and obj in self.objects def valid_arrow(self, f): return Category.valid_arrow(self, f) and f in self.arrows def composite(self, f, g): c = Category.composite(self, f, g) self.add_edge(c) return c
[docs] def hom(self, A, B): """Should return the set of all arrows between A and B""" return set(f for f in self.A.outgoing if f.target == B) # return set(f for f in self.arrows if f.source == A and f.target == B)
def is_identity(self, f): return Category.is_identity(f) \ and all(h == h * f for h in f.source.outgoing) \ and all(h == f * h for h in f.source.incoming) def valid_category(self): pass # return all( for obj in self.objects)
[docs] def close(self): """Compute the closure: generates all compositions and identities. TODO: check whether this indeed computes the closure: add_edge adds new edges to self.arrows, but does this guarantee that all newly added edges will be traversed? If not, we may replace it with something like this: arrow_list = list(self.arrows) new_arrows = [] for f in arrow_list: for g in f.target.outgoing: new_arrow = self.compose(f, g) new_arrows.append(new_arrow) arrow_list.append(new_arrow) for f in new_arrows: self.add_edge(f) """ # self.arrows |= set(self.ident(obj) for obj in self.objects) for obj in self.objects: self.add_edge(self.ident(obj)) # self.arrows |= set(self.composite(f, g) \ # for f in self.arrows \ # for g in f.target.outgoing) for f in self.arrows: for g in f.target.outgoing: self.add_edge(self.composite(f, g))