Algebra
We are first introduced to 'algebra' as a part of mathematics where we can use letters (variables) to stand in for numbers that are unknown or we dont wish to use the literal value. We can then use this to express axioms like: x+y =y+x.
Here we will talk about 'an algebra' to talk about specific mathematical 'equational theories' (The theory of fields is not equational because not every element has a multipicative inverse).
An 'equational theory' is called a 'TAlgebra'. This gives rise to a free  forgetful adjunction between sets and the category of models of the theory.
 forgetful functor U: TAlg > Sets
 free functor F: Sets > TAlg
The 'initial algebra' for an endofunctor P:S>S is a 'least fixed point' for P. Such algebras can be used in computer science to model 'recursive datatypes'.
Monads and Algebras
There is a connection between monads, adjunctions and algebras. 

An algebra can have two levels:
 An algebraic theory  defines function signatures and axioms.
 A model of that theory  defines the implementation of the functions.
Algebras and Coalgebras
Algebras have a structure based on products, so a subalgebra is a quotent. Coalgebras have a structure and substructure based on sum.
Monad as Algebraic Theory
A monad <T,η,µ> can represent an algebraic theory as might be given by function signatures and axioms.
Algebra for a Monad
An 'algebra for a monad' represents a model for the algebraic theory as discussed above, that is, an implementation of it.
More formally: An algebra for a monad <T,η,µ> is an object AC equiped with an 'action': a morphism θ:TA>A so that the following diagrams commute:
Category of Algebras
We can generalise this concept to a category of algebras (alg T) where the objects are the morphisms θ:TA>A
Monadisity
Given any category 'C', is it an alg T for some T?
There is a whole category of algebras with two extreems:
 The EilenbergMoore algebra (C^{T}) is terminal in this category of algebras. It has different objects but the same arrows as C.
 The Kleisli algebra is initial (C_{T})in this category of algebras. It has the same objects but different arrows as C.
Falgebras
Falgebras are discussed on this page.
Monads and Adjunction
Given a monad T on C is there an adjunction giving rise to it?
Every monad comes from an adjunction via its category of algebras
Example 1  Set
For a finite set we can have seperate constructors for each element. In the infinite examples below the underlying set is defined inductivly but since this example is finite then we only need 'X' on the left side of the equation only. 


Kleisli 
EilenbergMoore 

initial 
terminal
onepoint algebra 
Object 
X = a() + b() + c() 
T XX 
Arrow 
T = X^{ X} 
X→X 



Syntax 


Axioms 


Example 2  Natural Numbers
If we start with the natural numbers and some endofunction on them, then we can generate the initial and terminal algebras. 


Kleisli 
EilenbergMoore 

initial 
terminal 
Object 
X = Zero()  Succ(X)
If we put in the usual notation for 'algebraic data types then we have to make:
 Zero=(1 > N)
 Succ=(N > N)
The algebraic type for natural numbers is:
N = 1+N
Although this notation is confusing in this case since, '1' represents zero and '+' represents disjoint union and not addition. 
T AA 
Arrow 
T(X) = least fixpoint of above
Zero+Succ(Zero())+Succ(Succ(Zero()))+... 
A→A 



Axioms 
if X=Y
then succ(X)=succ(Y) 
0+A = A + 0 = A
A+B=B+A
(A+B)+C=A+(B+C) 

The functions zero and succ generate a carrier set, this has a structure in that it is ordered. 
Any algebra that obeys the axioms can represent the natural numbers. 
Example 3  Integers
Now extend the natural numbers example by adding negative numbers. 


Kleisli 
EilenbergMoore 

initial 
terminal 
Object 
A 
T AA 
Arrow 
T 
A→A 



Syntax 
A=zero()
A=succ(A)
A=pre(A) 
0()→T
+(T,T)→T
T→T 
Axioms 
if A=B
then succ(A)=succ(B)
and pre(A)=pre(B)
pre(succ(A)) = A
succ(pre(A)) = A 
0+A = A + 0 = A
A+(A) = 0
A+B=B+A
(A+B)+C=A+(B+C) 

The functions zero,succ and pre seem to generate the elements. 

Example 4  Rational Numbers
Now extend the natural numbers example by adding negative numbers. 


Kleisli 
EilenbergMoore 

initial 
terminal 
Object 
X =
f(0) = 1
f(n+1) = ½ f(n) 
T AA 
Arrow 
T 
A→A 



Syntax 
A=zero()
A=succ(A)
A=pre(A) 
0()→T
+(T,T)→T
T→T 
Axioms 
if A=B
then succ(A)=succ(B)
and pre(A)=pre(B)
pre(succ(A)) = A
succ(pre(A)) = A 
0+A = A + 0 = A
A+(A) = 0
A+B=B+A
(A+B)+C=A+(B+C)


The functions zero,succ and pre seem to generate the elements. 

Example 5  Algebra from Syntax
Can we create an algebraic theory from a (BNF) abstract syntax tree like this:
BNF 
Element (Example) 
E ::= E  E '+' E  E '*' E  '' E  N
N ::=
(0..9)+
where:
 E is an expression in N.
 N is a number.


How can we construct an expression? Can we form a monad? 

So a unit for a monad could be:
N > E N
Can this construct an expression using this? This does not appear to specify where in the heirarchy of the expression where to put this value.
Stack
it is only a tree if your base functor is a product functor. When you have a sum functor as the base functor it more closely resembles a stack machine  http://stackoverflow.com/questions/13352205/whatarefreemonads
We could perhaps represent this with using multicategories like this: 

Example 6  Words  Monad for Monoid
On this page we discuss monoids in terms of a binary operation and an identity element, but there is another way to approach monoids (especially free monoids), that is as a singly linked list. 

We can convert between these notions of monoid using a 'fold' operation. 

The underlying category has objects which are either:
 characters
 lists of characters
 lists of lists of characters
 … and so on.
The endofunctor 'T' maps from this object to itself, in this case it maps:
 a character to a list of characters
 and a list of characters to a list of list of characters
 and so on.
This endofunctor is equipped with two natural transformations:
 unit µ: 1 > T
 multiplication (join) η: T×T > T
Where,
 µ removes the inner set of brackets  takes a list of lists and joins the inner lists
 η_{T} adds brackets to each of the inner elements
 T η adds brackets around the outside of an instance.


So from this we can see the effect of various transformations:
x 
T> 
(x) 

T wraps element in list 
x 
η_{x}> 
(x) 

η at x wraps element in list 
(x,y) 
T> 
((x),(y)) 

T takes each element of list and wraps it in a sublist 
(x,y) 
η_{Tx}> 
((x,y)) 

η at T takes the whole list and wraps it in a sublist 
(x,y) 
Tη_{x}> 
((x),(y)) 

T•η at x takes each element of list and wraps it in a sublist 
((x,y)) 
µ_{x}> 
(x,y) 

µ removes brackets  takes a list of lists and joins the inner lists 
(((x,y))) 
µ_{Tx}> 
((x,y)) 



T> 




T> 




T> 



This satisfies the left and right triangle identities: 

and the associative square: 

Example 7  Monad on Poset
An endofunctor on posets models closure. Posets don't have loops, therefore defined by fixpoints.
Define T: P > P
with
gives
T² <= T (that is it is idempotent) 

Which gives an adjunction: t i
This is discussed as an adjunction on page here.
Monads for Different Theories

Monad for Monoid 
Monad for Small Categories 

C 
List 
Graph 

1 
empty list 


T 
list of elements 
free category on a graph 

T² 
list of list of elements 


unit (in algebra not monad) 
wrap in a list 
identity functor 

multiplication (in algebra not monad) 
flatten (remove inner brackets) 
composition of two functors 

unit µ for monad 



multiplication η for monad 














