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.
1 2 3 4 

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
:
1


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 “higherkinded 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:
1 2 3 

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

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:
1 2 3 

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
.
1


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:
1


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:
1 2 3 4 5 6 

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.
Comments