# Free Monoids and Free Monads

In a series of old posts, I once talked about the link between lists and monoids, as well as monoids and monads. Now I want to talk a little bit more about monoids and monads from the perspective of free structures.

`List` is a free monoid. That is, for any given type `A`, `List[A]` is a monoid, with list concatenation as the operation and the empty list as the identity element.

Being a free monoid means that it’s the minimal such structure. `List[A]` has exactly enough structure so that it is a monoid for any given `A`, and it has no further structure. This also means that for any given monoid `B`, there must exist a transformation, a monoid homomorphism from `List[A]` to `B`:

Given a mapping from `A` to a monoid `B`, we can collapse a value in the monoid `List[A]` to a value in `B`.

## Free monads

Now, if you followed my old posts, you already know that monads are “higher-kinded monoids”. A monoid in a category where the objects are type constructors (functors, actually) and the arrows between them are natural transformations. As a reminder, a natural transformation from `F` to `G` can be represented this way in Scala:

And it turns out that there is a free monad for any given functor `F`:

Analogous to how a `List[A]` is either `Nil` (the empty list) or a product of a `head` element and `tail` list, a value of type `Free[F,A]` is either an `A` or a product of `F[_]` and `Free[F,_]`. It is a recursive structure. And indeed, it has exactly enough structure to be a monad, for any given `F`, and no more.

When I say “product” of two functors like `F[_]` and `Free[F,_]`, I mean a product like this:

So we might expect that there is a monad homomorphism from a free monad on `F` to any monad that `F` can be transformed to. And indeed, it turns out that there is. The free monad catamorphism is in fact a monad homomorphism. Given a natural transformation from `F` to `G`, we can collapse a `Free[F,A]` to `G[A]`, just like with `foldMap` when given a function from `A` to `B` we could collapse a `List[A]` to `B`.

But what’s the equivalent of `foldRight` for `Free`? Remember, foldRight takes a unit element `z` and a function that accumulates into `B` so that `B` doesn’t actually have to be a monoid. Here, `f` is a lot like the monoid operation, except it takes the current `A` on the left:

The equivalent for `Free` takes a natural transformation as its unit element, which for a monad happens to be monadic `unit`. Then it takes a natural transformation as its `f` argument, that looks a lot like monadic `join`, except it takes the current `F` on the left:

In this case, `G` does not have to be a monad at all.

`Free` as well as natural transformations and product types are available in Scalaz.