"""
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))