What is the relationship between a monoid and a functor?

908 views Asked by At

I'm trying to understand the relationship between a functor and a monoid. They are often mentioned together but I haven't been able to quite connect the dots.

I understand that, simply speaking, in programming a monoid can be thought of as a structure or data type with an associative append/concat function used to combine elements in the structure as well as an identity element where if you commutatively combine the identity value with an element in your structure it will always return the same element.

I also recognize that in programming a functor can be thought of as a collection-like structure with a map operation similar to Array.prototype.map().

Could anyone help me see the big picture here? Also, please feel free to let me know if I'm missing anything in my understanding of these concepts.

2

There are 2 answers

0
JArgente On

Both of these terms came from category theory a Math branch that study the cathegories of elements, the relations among them and the composability of functions between the elements. This discipline has strong influence in functional programming and because of that usually these terms appear in discussions about these paradigm.

In practical terms the translation of functor and monoid terms into programming is the following:

Functor preserves the structure and relations between elements of two different cathegories, this means that a Functor is a "structure" that provides a constructor of one element.(preserves the structure because each element is mapped into a element of the other cathegory) and a map function (preserves the relations "functions" mapping each function of the original cathegory into the target one)

Monoid it is an endofunctor (functor that origin and target cathegory is the same) that defines and identiy operation and associative operation for example a list is a monoid because it defines an identity operation (empty list) and associative operation (append)

0
atis On

A functor is a structure-preserving transformation between categories.

It

  1. map objects from one category to objects of another
  2. while also preserving the arrows between objects

Sort of like homomorphisms between categories.

In FP language like Haskell, the definition of Functor class has two parts:

class Functor f where 
  fmap :: (a -> b) -> (f a -> f b) 

The type f is what maps objects (Haskell types) to other objects in the same category (Haskell types). It maps a to f a.


A monoid (semigroups with identity)

  1. A set, S
  2. combined with an operation, • : S × S → S
  3. and an element of S, e : 1 → S

Defined in Haskell as following

class Semigroup s => Monoid s where
  mempty  :: s
  
  mappend :: s -> s -> s
  mappend = (<>)

They are two different things but

They are often mentioned together but I haven't been able to quite connect the dots.

they are often mentioned together because of one another thing, a Monad.


A monad (special cases of monoids or monoids among endofunctors) is

  1. An endofunctor, T : S → S (An endofunctor is simply a functor from a category to itself)
  2. along with a natural transformation, μ : S × S → S, where × means functor composition (join)
  3. and η : I → S, where I is the identity endofunctor on S (return)

which essentially combines those two concepts.

In Haskell

(>>=)       :: m a -> (a -> m b) -> m b
(>>)        :: m a -> m b -> m b
return      :: a -> m a

implies

fmap f m  =  m >>= return . f

More succinctly put,

A monad is just a monoid in the category of endofunctors, what's the problem?

which you might have seen jokingly used all over FP forums. It's a version of

a monad in X is just a monoid in the category of endofunctors of X

originally from Mac Lane's Categories for the Working Mathematician.