Maths - Category Theory and Computing

Mathematics and computing are linked at various levels. On these pages we look at the relationship between category theory and computing and the relationship between these and algebra. I am interested in these both:

In particular it would be interesting to see how the mathematical concept of an 'algebra' could be modeled on a computer.

Category theory and Computing

The diagram on the right represents a category with the following objects:

  • N - a set of numbers.
  • (N,N) - a tuple of two numbers
  • Ω- a boolean value (true or false).
  • 1 - final value.

Note: further down the page the symbol 'Ω' Omega is used differently to represent the whole set of function signatures. In the literature you may find Ω being used for either of these things so its best to check.

The 'functions' between these objects are:

  • + - add, takes two numbers and returns their sum
  • = - equals, takes two numbers and returns true if they are equal and false otherwise.
  • isZero - returns true if the number is zero and false otherwise.
  • construct - creates a number with a specified value.
category theory and computing

In a programming language we often use a construction with a set of function signatures such as those on the right, for example:

  • Java- interface
  • Scala - trait
  • Haskell - typeclass

+(N,N)->N
construct(int) -> N
iszero(N) -> boolean
=(N,N) -> boolean

So these programming constructs appear to have the same information as a category diagram. Of course there are differences, in a category we might have additional diagrams to express axioms such as associatively, in an interface/trait/typeclass there is no way to enforce axioms.

Also, in a computer program, functions don't always have the same properties a mathematical functions. A mathematical function should always produce the same output for a given set of inputs. In a program a function will often depend on an input, or a state value, or something like that. In the programming world the first case is known as a 'pure function' and the other cases are known as 'side effects' or just 'effects'.

Computer Languages and Algebras

Computer languages incorporate algebras and algebra-like structures into the language, for instance they have fundamental types such as Integers and float which approximate the corresponding algebras. The users can then build up more complex algebras such as complex, vectors and so on (or use pre-build mathematical libraries).

However, in a mathematical program, it would be good to be able to work with algebras as first class entities in their own right. That is, instead of only being able to construct new algebras by recompiling, we would want to construct algebras dynamically from within the program(this may be related to the idea of category as a first class object?). What we want to do is be able to manipulate these algebras to say, generate its dual or generate the product, sum or exponent of two algebras, or to work with whole families of algebras.

Most languages allow us to construct instances of an algebra, for example '1' as an instance of Integer and then combine them together using functions and operations like '+' however there is no obvious way to treat the whole algebra as a whole entity.

Constructs like 'lists' represent functors, that is it is not a category itself but it maps from a category 'Integer' to a category 'List Integer'.

  List  
Integer
->
List Integer
This comes close to the idea of dealing with a whole algebra, for instance we can work with elements of the list such as 'a', 'b' and 'c' and we can work with the whole list as a single entity: myAlgebra:Set A := ['a','b','c'].
So what would it take to turn this into an algebra? Many algebras are built on the concept of set rather than list so we can use 'set' as the functor:
  Set  
Element
->
SetElement
Then we need to add structure to the set in the form of functions with signatures like: mult: (a:myAlgebra, b:myAlgebra):myAlgebra

Algebra Types

Ω-Algebra

A set of operator symbols, each operator has an arity and all operators act only on the elements of the algebra.

F-Algebra and F-Coalgebra

F-Algebras and F-Coalgebras are the same as Ω-(co)algebras except we denote all the operator signatures by a single functor.

If I may misuse notation then I will notate this as:

Poly := () } n0 times
/\ (%) } n1 times
/\ (%,%) } n2 times
/\ (%,%,%) } n3 times
...

So we can use this to define a free, pure algebra and a pure coalgebra as follows:

UniversalAlgebra() : Metacategory == with
Poly % -> %

UniversalCoalgebra() : Metacategory == with
% -> Poly %

These represent free algebras and a particular instance can be formed by choosing values for the 'components': n0,n1,n2...

F-algebras and F-coalgebras are themselves categories. They can also be defined over an arbitrary category % where Poly % -> % is an endofunctor from % to itself.

On their own pure algebra or coalgebra would not be much use, they don't have a way to interact with other algebras, but perhaps we could add that later.

Monads and T-Algebras

A T-Algebra is an F-Algebra, as defined above, together with a set of equations (axioms) built from the F-Algebra operations.

So we have the endofunctor but what are the two natural transformations to construct a monad from it?

Let T be a (finitary) equational theory, consisting of finitely many operational symbols, each of some arity and a set of equations between terms built from these operations.

Algebra and Coalgebra

If we look at an equation like a+b=c we can interpret this in either a static or dynamic way:

sheep coalgebra

Dynamic (coalgebra)

We could look at an equation like 2+3=5 as meaning that we start with say, 3 sheep then we add 2 more to get 5.

sheep algebra

Static (algebra)

Or we could look at 2+3=5 statically (not changing over time) for instance, if there are 2 sheep in one field and 3 sheep in another field, then that is equal to 5 sheep in another field.

Algebras tend to be associated with the static situation and coalgebras with dynamic systems.

  Coalgebra Algebra
  dynamic behavior oriented systems static data oriented systems
information semantics syntax
language type object oriented functional

Algebra

Here is an example of a simple calculator that implements a pure algebra (well almost, I've had to compromise a bit). The idea is that the two operands are on the left and the result of adding, subtracting and multiplying them are shown separately on the right. So the whole thing should be stateless, that is the result only depends on the current input, not some particular sequence. I compromised a bit on this in that I did not want to keep checking if the inputs have changed so I added buttons to trigger calculation of +, - and *.

inputs   outputs
 

Coalgebra

This is more like a conventional calculator which is a state machine, that is the inputs act on the state machine.

inputs
state machine
 

This state machine is similar to an object in object oriented programming. So when we want to add something to it, we pass the quantity to be added, and its state changes to reflect that, its original state is lost. In this case there are additional states associated with the memory and back functions.

Concepts

Here are some of the concepts involved and a non-rigorous indication about where there may be links.

concepts

 


metadata block
see also:
Correspondence about this page

Book Shop - Further reading.

Where I can, I have put links to Amazon for books that are relevant to the subject, click on the appropriate country flag to get more details of the book or to buy it from them.

flag flag flag flag flag flag The Princeton Companion to Mathematics - This is a big book that attempts to give a wide overview of the whole of mathematics, inevitably there are many things missing, but it gives a good insight into the history, concepts, branches, theorems and wider perspective of mathematics. It is well written and, if you are interested in maths, this is the type of book where you can open a page at random and find something interesting to read. To some extent it can be used as a reference book, although it doesn't have tables of formula for trig functions and so on, but where it is most useful is when you want to read about various topics to find out which topics are interesting and relevant to you.

 

Terminology and Notation

Specific to this page here:

 

This site may have errors. Don't use for critical systems.

Copyright (c) 1998-2016 Martin John Baker - All rights reserved - privacy policy.