# Free structure

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

### Introduction

This article attempts to give a relatively informal understanding of "free" structures from algebra/category theory, with pointers to some of the formal material for those who desire it. The later sections make use of some notions from category theory, so some familiarity with its basics will be useful.

### Algebra

#### What sort of structures are we talking about?

The distinction between free structures and other, non-free structures, originates in abstract algebra, so that provides a good place to start. Some common structures considered in algebra are:

• Monoids
• consisting of
• A set $M$
• An identity $e \in M$
• A binary operation $* : M \times M \to M$
• And satisfying the equations
• $x * (y * z) = (x * y) * z$
• $e * x = x = x * e$
• Groups
• consisting of
• A monoid $(M, e, *)$
• An additional unary operation $\,^{-1} : M \to M$
• satisfying
• $x * x^{-1} = e = x^{-1} * x$
• Rings
• consisting of
• A set $R$
• A unary operation $- : R \to R$
• Two binary operations $+, * : R \times R \to R$
• Distinguished elements $0, 1 \in R$
• such that
• $(R, 0, +, -)$ is a group
• $(R, 1, *)$ is a monoid
• $x + y = y + x$
• $(x + y)*z = x*z + y*z$
• $x * (y + z) = x*y + x*z$

So, for algebraic structures, we have sets equipped with operations that are expected to satisfy equational laws.

#### Free algebraic structures

Now, given such a description, we can talk about the free structure over a particular set $S$ (or, possibly over some other underlying structure; but we'll stick with sets now). What this means is that given $S$, we want to find some set $M$, together with appropriate operations to make $M$ the structure in question, along with the following two criteria:

• There is an embedding $i : S \to M$
• The structure generated is as 'simple' as possible.
• $M$ should contain only elements that are required to exist by $i$ and the operations of the structure.
• The only equational laws that should hold for the generated structure are those that are required to hold by the equational laws for structures of that type.

So, in the case of a free monoid (from here on out, we'll assume that the structure in question is a monoid, since it's simplest), the equation $x * y = y * x$ should not hold unless $x = y$, $x = e$ or $y = e$. Further $i x \in M$, for all $x$, and $e \in M$, and $\forall x, y \in M.\,\, x * y \in M$ (and these should all be distinct, except as required by the monoid laws), but there should be no 'extra' elements of $M$ in addition to those.

For monoids, the free structure over a set is given by the monoid of lists of elements of that set, with concatenation as multiplication. It should be easy to convince yourself of the following (in pseudo-Haskell):

M = [S]
e = []
* = (++)

i : S -> [S]
i x = [x] -- i x = x : []

[] ++ xs = xs = xs ++ []
xs ++ (ys ++ zs) = (xs ++ ys) ++ zs

xs ++ ys = ys ++ xs iff xs == ys || xs == [] || ys == []
-- etc.


### The category connection

#### Free structure functors

One possible objection to the above description (even a more formal version thereof) is that the characterization of "simple" is somewhat vague. Category theory gives a somewhat better solution. Generally, structures-over-a-set will form a category, with arrows being structure-preserving homomorphisms. "Simplest" (in the sense we want) structures in that category will then either be initial or terminal,  and thus, freeness can be defined in terms of such universal constructions.

In its full categorical generality, freeness isn't necessarily categorized by underlying set structure, either. Instead, one looks at "forgetful" functors  from the category of structures to some other category. For our free monoids above, it'd be:

• $U : Mon \to Set$

The functor taking monoids $(M, e, *)$ to their underlying set $M$. Then, the relevant universal property is given by finding an adjoint functor:

• $F : Set \to Mon$, $F$ $U$ $F$ being the functor taking sets to the free monoids over those sets. So, free structure functors are left adjoint to forgetful functors. It turns out this categorical presentation also has a dual: cofree structure functors are right adjoint to forgetful functors.

#### Algebraic constructions in a category

Category theory also provides a way to extend specifications of algebraic structures to more general categories, which can allow us to extend the above informal understanding to new contexts. For instance, one can talk about monoid objects in an arbitrary monoidal category. Such categories have a tensor product $\otimes$ of objects, with a unit object $I$ (both of which satisfy various laws).

A monoid object in a monoidal category is then:

• An object $M$
• A unit 'element' $e : I \to M$
• A multiplication $m : M \otimes M \to M$

such that:

• $m \circ (id_{M} \otimes e) = u_l$
• $m \circ (e \otimes id_M) = u_r$
• $m \circ (id_M \otimes m) = m \circ (m \otimes id_M) \circ \alpha$

Where:

• $u_l : M \otimes I \to M$ and $u_r : I \otimes M \to M$ are the identity isomorphisms for the monoidal category, and
• $\alpha : M \otimes (M \otimes M) \to (M \otimes M) \otimes M$ is part of the associativity isomorphism of the category.

So, hopefully the connection is clear: we've generalized the carrier set to a carrier object, generalized the operations to morphisms in a category, and equational laws are promoted to being equations about composition of morphisms.

One example of a class of monoid objects happens to be monads. Given a base category $C$, we have the monoidal category $C^C$:

• Objects are endofunctors $F : C \to C$
• Morphisms are natural transformations  between the functors
• The tensor product is composition: $F \otimes G = F \circ G$
• The identity object is the identity functor, $I$, taking objects and morphisms to themselves

If we then specialize the definition of a monoid object to this situation, we get:

• An endofunctor $M : C \to C$
• A natural transformation $\eta : I \to M$
• A natural transformation $\mu : M \circ M \to M$

which satisfy laws that turn out to be the standard monad laws. So, monads turn out to be monoid objects in the category of endofunctors.

But, what about our intuitive understanding of free monoids above? We wanted to promote an underlying set, but we have switched from sets to functors. So, presumably, a free monad is generated by an underlying (endo)functor, $F : C \to C$. We then expect there to be a natural transformation $i : F \to M$, 'injecting' the functor into the monad.

data Free f a = Return a | Roll (f (Free f a))

instance Functor f => Monad (Free f) where
return a       = Return a
Return a >>= f = f a
Roll ffa >>= f = Roll $fmap (>>= f) ffa -- join (Return fa) = fa -- join (Roll ffa) = Roll (fmap join ffa) inj :: Functor f => f a -> Free f a inj fa = Roll$ fmap Return fa


This should bear some resemblance to free monoids over lists. Return is analogous to [], and Roll is analogous to (:). Lists let us create arbitrary length strings of elements from some set, while Free f lets us create structures involving f composed with itself an arbitrary number of times (recall, functor composition was the tensor product of our category). Return gives our type a way to handle the 0-ary composition of f (as [] is the 0-length string), while Roll is the way to extend the nesting level by one (just as (:) lets us create (n+1)-length strings out of n-length ones). Finally, both injections are built in a similar way:

inj_list x = (:) x []
inj_free fx = Roll (fmap Return fx)


This, of course, is not completely rigorous, but it is a nice extension of the informal reasoning we started with.