A new Python package for Applied Category Theory

On this blog, I posted frequently about the Python package Opycleid for transformational music theory which I’ve developed. From the beginning, I envisioned Opycleid to be as general as possible, for example by not limiting itself to group and group actions, but to categories as well. Ultimately, this meant coding a way to manipulate faithful functors \mathbf{C} \to \mathbf{Rel} in Python. However, in its current form Opycleid is not a category theory package: functors \mathbf{C} \to \mathbf{Rel} are manipulated as atomic, indecomposable entities (via the CategoryAction class). For the purpose of transformational music theory, this works ok up to a point: morphisms of such functors can be still be defined but the code complexity increases, and it reaches its maximum when it comes to network transformations via global and local homographies.

These remarks, along with recent discussions I had with applied category theorists on Twitter made me think about developing a new, independent Python package for applied category theory (ACT). Now, the use of Python for ACT may be a surprising choice (did you say “duck typing” ?) : one encounters Haskell more often in this field. But my experience on Opycleid along with some ideas I wanted to test made me want to see how far one could go with Python.

And thus I present Colubridae, a Python package for ACT. Why this name ? Because this is the taxonomic family with the most “cat snakes” (ha ha). In the rest of this post, I’ll briefly explain the key concepts behind Colubridae, and show some examples.

Note: the examples below are given for the very first version of colubridae, version number 0.0.1.

 

Objects, morphisms, categories

Briefly and informally said, a category is a bunch of objects, and a bunch of morphisms between them that can be composed. Thus all we really need from Python is a way to ‘multiply’ stuff, and to ‘compare’ it, i.e. say whether two things (in this case morphisms) are equal or not. Let’s see how a category is coded in Colubridae:

class Category(object):
    def __init__(self,objects,generators):
        if len(set([x.__class__ for x in objects]))>1:
            raise Exception("Objects must be of the same class")
        if len(set([x.__class__ for x in generators]))>1:
            raise Exception("Generators must be of the same class")

        self.objects = set(objects)
        self.object_type = objects[0].__class__
        self.morphism_type = generators[0].__class__

        for f in generators:
            if not f.source in self.objects:
                raise Exception("Generator source not in objects")
            if not f.target in self.objects:
                raise Exception("Generator target not in objects")

        self.generators = generators
        for x in self.objects:
            self.generators.append(self.morphism_type.get_identity_morphism(x))

        self.generators = set(self.generators)
        self.morphisms = []
        self.generate_category()

    def _itergenerate(self,new_maps):
        x=[g*x for g in self.generators for x in new_maps if ((not g*x is None) and (not g*x in self.morphisms))]
        if len(x):
            self.morphisms += x
            self._itergenerate(x)
        else:
            return None

    def __eq__(self,rhs):
        return (self.objects == rhs.objects) and (self.morphisms == rhs.morphisms)

    def __hash__(self):
        hash_val = sum([hash(x) for x in self.objects])
        hash_val += sum([hash(x) for x in self.morphisms])
        return hash_val

    def generate_category(self):
        new_maps = list(self.generators)

        self._itergenerate(new_maps)
        self.morphisms = set(self.morphisms)

A category is a Python class which we instantiates with two parameters: a list of objects and a list of generating morphisms (‘generators’, not to be confused with this definition). After a few checks (whether the generators have their domain and codomain in the given list of objects, etc.), a naïve algorithm is called to enumerate all morphisms in this category. So, yes, to answer the first question: our package is only able to deal with categories having finite sets of objects and morphisms. Notice the important line in the morphism generation code:


x=[g*x for g in self.generators for x in new_maps
       if ((not g*x is None) and (not g*x in self.morphisms))]

To be able to compose morphisms, we have to overload the infix operator ‘*’ in Python for any class that wants to be a morphism. What’s also hidden in ‘not g*x in’ is that we also have to overload the infix operator ‘==’ in Python so that two morphisms can be said equal or not.

So let’s see with a very basic example: sets and functions. First, we define a set object :

class SetObject(object):
    def __init__(self,elems,name=None):
        self.elems = set(elems)
        self.name = name

    def __mul__(self,setobj2):
        return SetObject([(x,y) for x in self.elems for y in setobj2.elems])

    def __eq__(self,set2):
        if not isinstance(set2,SetObject):
            raise Exception("RHS is not a valid SetObject class\n")
        return self.elems==set2.elems

    def __hash__(self):
        return sum([hash(x) for x in self.elems])

    def __repr__(self):
        if self.name is None:
            return str(self.elems)
        else:
            return self.name

Luckily in Python, we already have a ‘set‘ type, so we are just wrapping it in a class.
In this case, the infix operator ‘*’ has been overloaded, but this does not mean that we are considering this class as a morphism. However, we overload ‘==’ and ‘__hash__’ because these classes will be used in lists, sets, and in dictionaries (think natural transformations).

Next, we define functions between sets as such :

class Function(object):
    def __init__(self,source,target,mapping):
        if not isinstance(source,SetObject):
            raise Exception("Source is not a valid SetObject class\n")
        if not isinstance(target,SetObject):
            raise Exception("Source is not a valid SetObject class\n")
        self.source = source
        self.target = target

        if not self.source.elems == set(mapping.keys()):
            raise Exception("Not a valid function mapping\n")
        if not set(mapping.values()).issubset(self.target.elems):
            raise Exception("Not a valid function mapping\n")
        self.mapping = {k:v for k,v in mapping.items()}

    def __eq__(self,rhs):
        if rhs is None:
            return False
        if not isinstance(rhs,Function):
            raise Exception("RHS is not a valid Function class\n")
        return (self.mapping==rhs.mapping) and \
               (self.source == rhs.source) and \
               (self.target == rhs.target)

    def __mul__(self,rhs):
        if not isinstance(rhs,Function):
            raise Exception("RHS is not a valid Function class\n")
        if not self.source==rhs.target:
            return None
        new_map = {x:self(y) for x,y in rhs.mapping.items()}
        return Function(rhs.source,self.target,new_map)

    def __call__(self,x):
        return self.mapping.get(x)

    def __hash__(self):
        hash_val = hash(self.source)
        hash_val += hash(self.target)
        hash_val += sum([hash(x) for x in self.mapping.items()])
        return hash_val

    @staticmethod
    def get_identity_morphism(X):
        if not isinstance(X,SetObject):
            raise Exception("Not a valid SetObject class\n")
        return Function(X,X,{x:x for x in X.elems})

OK, this one is a bit more complicated. First of all, notice how we overloaded the infix operator ‘*’ : this is were we define actual function composition, after a few checks. We also overloaded the infix operator ‘==’ : two functions are equal if they share the same domain, codomain, and mapping of elements. We also overload ‘__hash__’ so that two identical functions have the same hash (again, useful for using it in lists, sets, and dictionaries). Since it is a function, we should be able to call it to get the image of an element of the set, and this is why we also overloaded ‘__call__’ (and see how useful it is in the definition of ‘__mul__’).

Finally, there is a piece of code which may be surprising: the definition of a class method ‘get_identity_morphism‘. If you look at the code for the Category class, you’ll see that we need to define identity morphisms for all objects of the category. But why is this not a instance method of SetObject ? That’s because this object can be the domain or codomain of many types of morphisms: functions, relations, etc. so it is only normal that this should be a class method for the type of morphism being considered, which takes an object and returns the identity morphism on it.

I have included in colubridae.sets the code for sets, functions, partial functions and relations. Of course, you can define your own, as long as you overload the same methods and define the class method ‘get_identity_morphism‘.

I won’t go into the details, but if you look at the code for colubridae.category, you’ll find that functors and natural transformations are coded as classes which overload the same methods, making it possible to use them both as objects and morphisms. Also, since natural transformations have two composition laws, I’ve overloaded the ‘*’ operator for vertical composition, and the ‘^’ operator for horizontal composition.

 

Examples

OK, time for some examples of use now. First, a basic one : let’s define the cyclic group \mathbb{Z}_8 as a single object category.


from colubridae.category import Category
from colubridae.sets import SetObject,Function

X=SetObject(["a","b","c","d","e","f","g","h"])
t = Function(X,X,{"a":"b","b":"c","c":"d",
                  "d":"e","e":"f","f":"g",
                  "g":"h","h":"a"})
Z8 = Category([X],[t])
print(len(Z8.morphisms))
## prints '8'

Next, let’s determine the automorphism group of \mathbb{Z}_8. An automorphism is defined by the image of the generators, so we can check all possible images since there are few morphisms :

for x in list(Z8.morphisms):
    print(Category([X],[x])==Z8)
    print(x.mapping)

#prints
# True
# {'a': 'd', 'b': 'e', 'c': 'f', 'd': 'g', 'e': 'h', 'f': 'a', 'g': 'b', 'h': 'c'}
# False
# {'a': 'e', 'b': 'f', 'c': 'g', 'd': 'h', 'e': 'a', 'f': 'b', 'g': 'c', 'h': 'd'}
# False
# {'a': 'g', 'b': 'h', 'c': 'a', 'd': 'b', 'e': 'c', 'f': 'd', 'g': 'e', 'h': 'f'}
# False
# {'a': 'c', 'b': 'd', 'c': 'e', 'd': 'f', 'e': 'g', 'f': 'h', 'g': 'a', 'h': 'b'}
# True
# {'a': 'b', 'b': 'c', 'c': 'd', 'd': 'e', 'e': 'f', 'f': 'g', 'g': 'h', 'h': 'a'}
# True
# {'a': 'f', 'b': 'g', 'c': 'h', 'd': 'a', 'e': 'b', 'f': 'c', 'g': 'd', 'h': 'e'}
# False
# {'g': 'g', 'a': 'a', 'c': 'c', 'd': 'd', 'e': 'e', 'h': 'h', 'f': 'f', 'b': 'b'}
# True
# {'a': 'h', 'b': 'a', 'c': 'b', 'd': 'c', 'e': 'd', 'f': 'e', 'g': 'f', 'h': 'g'}

As expected, there are 4 automorphisms, sending t to t, t^3, t^5, and t^7 respectively. We thus can define the corresponding functors :

from colubridae.category import Functor

F = Functor(Z8,Z8,{X:X},{t:t*t*t},from_generators=True)
print(F(t*t).mapping)
# prints {'a': 'g', 'b': 'h', 'c': 'a', 'd': 'b', 'e': 'c', 'f': 'd', 'g': 'e', 'h': 'f'}

G = Functor(Z8,Z8,{X:X},{t:t*t*t*t*t},from_generators=True)
AutZ8 = Category([Z8],[F,G])
print(len(AutZ8.morphisms))
# prints '4'

Notice that we created a new category, the automorphism group(-as-category) of \mathbb{Z}_8, this time using the previous category as object, and the functors as morphisms.

Now, let’s see a more complex example with different types of morphisms. On one hand, we will define the group \mathbb{Z}_2 via its action on a two-element set, and on the other hand, we will define a monoid of relations on a four-element set.

from colubridae.sets import Relation

A=SetObject(["a","b"])
f = Function(A,A,{"a":"b","b":"a"})
Z2 = Category([A],[f])

B=SetObject(["p","q","r","s"])
g = Relation(B,B,{"p":{"q","r"},"q":{"p","s"},"r":{"r"},"s":{"r"}})
M = Category([B],[g])
for x in M.morphisms:
    print(x.mapping)

#prints
# {'p': {'p', 'r', 's'}, 'q': {'q', 'r'}, 'r': {'r'}, 's': {'r'}}
# {'p': {'q', 'r'}, 'q': {'p', 'r', 's'}, 'r': {'r'}, 's': {'r'}}
# {'q': {'p', 's'}, 'p': {'q', 'r'}, 'r': {'r'}, 's': {'r'}}
# {'q': {'q'}, 'p': {'p'}, 'r': {'r'}, 's': {'s'}}

No restrictions on morphism types when using functors :


F=Functor(M,Z2,{B:A},{g:f},from_generators=True)
F(g*g*g).mapping
# prints {'a': 'b', 'b': 'a'}

 

OK, on to a more complicated example with natural transformations. We are going to define a simple connected poset-as-category \Delta with three elements, as such:

U=SetObject(["u"])
V=SetObject(["v"])
W=SetObject(["w"])

fUV = Function(U,V,{"u":"v"})
fVW = Function(V,W,{"v":"w"})
Delta = Category([U,V,W],[fUV,fVW])

Functors from this category to \mathbb{Z}_8 corresponds to labeled posets where each arrow is labeled with an element of \mathbb{Z}_8. For example :

F1 = Functor(Delta,Z8,
             {U:X,V:X,W:X},
             {fUV:t,fVW:t*t},from_generators=True)
F2 = Functor(Delta,Z8,
             {U:X,V:X,W:X},
             {fUV:t*t,fVW:t*t},from_generators=True)

We can consider these two functors as objects in the functor category {\mathbb{Z}_8}^{\Delta}. As can be quickly verified, the set of morphisms (natural transformations) between any two objects in {\mathbb{Z}_8}^{\Delta} can be bijectively identified with the set of elements of \mathbb{Z}_8. Let’s verify this by defining two natural transformations which we will take as generators in the corresponding subcategory of {\mathbb{Z}_8}^{\Delta}.

N1 = NaturalTransformation(F1,F2,{U:t,V:t*t,W:t*t})
N2 = NaturalTransformation(F2,F1,{U:t*t,V:t,W:t})

func_cat = Category([F1,F2],[N1,N2])
print(len(func_cat.morphisms))
#prints '32'

As expected, we found 32=4*8 morphisms in this subcategory.

 

Conclusion

That’s it for this very brief introduction to this new package. As I said above, I wanted to see how far one could go in Python, and I was surprised to see that I could actually define categories of functors. The definition of objects and morphisms is quite flexible, so for example I guess one could easily define lenses and the corresponding categories.

A few words before concluding this post:

  • This is a super early version of Colubridae: that means probable bugs and uncommented code, and that many improvements are also possible.
  • Any help for the development is welcome !

 

One comment

  1. Would this usable for defining Multiple Value Logics (i.e., n>2; completely deterministically using lookup tables with the evaluation defined for each combination of operands and operator(s), and re-sequencing evaluations to match order of operations (a la Prolog or Lisp), and completing tables with the evaluations for all of the combinations)?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s