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

Question

Who first said the following      A monad is just a monoid in the   category of endofunctors  what s the   problem    And on a less important note  is this true and if so could you give an explanation  hopefully one that can be understood by someone who doesn t have much Haskell experience

User · Answer

Note  No  this isn t true  At some point there was a comment on this answer from Dan Piponi himself saying that the cause and effect here was exactly the opposite  that he wrote his article in response to James Iry s quip  But it seems to have been removed  perhaps by some compulsive tidier   Below is my original answer     It s quite possible that Iry had read From Monoids to Monads  a post in which Dan Piponi  sigfpe  derives monads from monoids in Haskell  with much discussion of category theory and explicit mention of  the category of endofunctors on Hask    In any case  anyone who wonders what it means for a monad to be a monoid in the category of endofunctors might benefit from reading this derivation

User · Answer

I came to this post by way of better understanding the inference of the infamous quote from Mac Lane s Category Theory For the Working Mathematician   In describing what something is  it s often equally useful to describe what it s not   The fact that Mac Lane uses the description to describe a Monad  one might imply that it describes something unique to monads   Bear with me   To develop a broader understanding of the statement  I believe it needs to be made clear that he is not describing something that is unique to monads  the statement equally describes Applicative and Arrows among others  For the same reason we can have two monoids on Int  Sum and Product   we can have several monoids on X in the category of endofunctors  But there is even more to the similarities   Both Monad and Applicative meet the criteria    endo    any arrow  or morphism that starts and ends in the same place functor    any arrow  or morphism between two Categories  e g   in day to day Tree a - gt  List b  but in Category Tree - gt  List  monoid    single object  i e   a single type  but in this context  only in regards to the external layer  so  we can t have Tree - gt  List  only List - gt  List     The statement uses  Category of     This defines the scope of the statement  As an example  the Functor Category describes the scope of f   - gt  g    i e   Any functor - gt  Any functor  e g   Tree   - gt  List   or Tree   - gt  Tree     What a Categorical statement does not specify describes where anything and everything is permitted  In this case  inside the functors    - gt    aka a - gt  b is not specified which means Anything - gt  Anything including Anything else  As my imagination jumps to Int -  String  it also includes Integer - gt  Maybe Int  or even Maybe Double - gt  Either String Int where a    Maybe Double  b    Either String Int     So the statement comes together as follows    functor scope     f a - gt  g b  i e   any parameterized type to any parameterized type  endo   functor    f a - gt  f b  i e   any one parameterized type to the same parameterized type      said differently  a monoid in the category of endofunctor    So  where is the power of this construct  To appreciate the full dynamics  I needed to see that the typical drawings of a monoid  single object with what looks like an identity arrow     single object - gt  single object   fails to illustrate that I m permitted to use an arrow parameterized with any number of monoid values  from the one type object permitted in Monoid  The endo    identity arrow definition of equivalence ignores the functor s type value and both the type and value of the most inner   payload  layer   Thus  equivalence returns true in any situation where the functorial types match  e g   Nothing - gt  Just   - gt  Nothing is equivalent to Just   - gt  Just   - gt  Just   because they are both Maybe - gt  Maybe - gt  Maybe     Sidebar    outside is conceptual  but is the left most symbol in f a  It also describes what  Haskell  reads-in first  big picture   so Type is  outside  in relation to a Type Value  The relationship between layers  a chain of references  in programming is not easy to relate in Category  The Category of Set is used to describe Types  Int  Strings  Maybe Int etc   which includes the Category of Functor  parameterized Types   The reference chain  Functor Type  Functor values  elements of that Functor s set  e g   Nothing  Just   and in turn  everything else each functor value points to  In Category the relationship is described differently  e g   return    a - gt  m a is considered a natural transformation from one Functor to another Functor  different from anything mentioned thus far    Back to the main thread  all in all  for any defined tensor product and a neutral value  the statement ends up describing an amazingly powerful computational construct born from its paradoxical structure     on the outside it appears as a single object  e g      List   static but inside  permits a lot of dynamics   any number of values of the same type  e g   Empty    NonEmpty  as fodder to functions of any arity  The tensor product will reduce any number of inputs to a single value    for the external layer   fold that says nothing about the payload  infinite range of both the type and values for the inner most layer    In Haskell  clarifying the applicability of the statement is important  The power and versatility of this construct  has absolutely nothing to do with a monad per se  In other words  the construct does not rely on what makes a monad unique    When trying to figure out whether to build code with a shared context to support computations that depend on each other  versus computations that can be run in parallel  this infamous statement  with as much as it describes  is not a contrast between the choice of Applicative  Arrows and Monads  but rather is a description of how much they are the same  For the decision at hand  the statement is moot     This is often misunderstood  The statement goes on to describe join    m  m a  - gt  m a as the tensor product for the monoidal endofunctor  However  it does not articulate how  in the context of this statement    lt   gt   could also have also been chosen  It truly is a an example of six half dozen  The logic for combining values are exactly alike  same input generates the same output from each  unlike the Sum and Product monoids for Int because they generate different results when combining Ints      So  to recap  A monoid in the category of endofunctors describes        t    m   - gt  m   - gt  m      and a neutral value for m       lt   gt   and   gt  gt    both provide simultaneous access to the two m values in order to compute the the single return value  The logic used to compute the return value is exactly the same   If it were not for the different shapes of the functions they parameterize  f    a - gt  b versus k    a - gt  m b  and the position of the parameter with the same return type of the computation  i e   a - gt  b - gt  b versus b - gt  a - gt  b for each respectively   I suspect we could have parameterized the monoidal logic  the tensor product  for reuse in both definitions   As an exercise to make the point  try and implement  t  and you end up with   lt   gt   and   gt  gt    depending on how you decide to define it forall a b   If my last point is at minimum conceptually true  it then explains the precise  and only computational difference between Applicative and Monad  the functions they parameterize   In other words  the difference is external to the implementation of these type classes   In conclusion  in my own experience  Mac Lane s infamous quote provided a great  goto  meme  a guidepost for me to reference while navigating my way through Category to better understand the idioms used in Haskell  It succeeds at capturing the scope of a powerful computing capacity made wonderfully accessible in Haskell     However  there is irony in how I first misunderstood the statement s applicability outside of the monad  and what I hope conveyed here  Everything that it describes turns out to be what is similar between Applicative and Monads  and Arrows among others    What it doesn t say is precisely the small but useful distinction between them   - E

User · Answer

First  the extensions and libraries that we re going to use   -  LANGUAGE RankNTypes  TypeOperators  -   import Control Monad  join   Of these  RankNTypes is the only one that s absolutely essential to the below  I once wrote an explanation of RankNTypes that some people seem to have found useful  so I ll refer to that  Quoting Tom Crockett s excellent answer  we have   A monad is     An endofunctor  T   X - gt  X A natural transformation       T    T - gt  T  where    means functor composition A natural transformation      I - gt  T  where I is the identity endofunctor on X     satisfying these laws         T    T     T        T       T    T        T     T      T       How do we translate this to Haskell code  Well  let s start with the notion of a natural transformation  --   A natural transformations between two  Functor  instances   Law  -- --  gt  fmap f   eta g    eta g   fmap f -- -- Neat fact  the type system actually guarantees this law  -- newtype f  - gt  g       Natural   eta    forall x  f x - gt  g x    A type of the form f  - gt  g is analogous to a function type  but instead of thinking of it as a function between two types  of kind     think of it as a morphism between two functors  each of kind   - gt      Examples  listToMaybe        - gt  Maybe listToMaybe   Natural go     where go      Nothing           go  x      Just x  maybeToList    Maybe  - gt     maybeToList   Natural go     where go Nothing                go  Just x     x   reverse         - gt     reverse    Natural reverse  Basically  in Haskell  natural transformations are functions from some type f x to another type g x such that the x type variable is  quot inaccessible quot  to the caller  So for example  sort    Ord a   gt   a  - gt   a  cannot be made into a natural transformation  because it s  quot picky quot  about which types we may instantiate for a  One intuitive way I often use to think of this is the following   A functor is a way of operating on the content of something without touching the structure  A natural transformation is a way of operating on the structure of something without touching or looking at the content   Now  with that out of the way  let s tackle the clauses of the definition  The first clause is  quot an endofunctor  T   X - gt  X  quot  Well  every Functor in Haskell is an endofunctor in what people call  quot the Hask category  quot  whose objects are Haskell types  of kind    and whose morphisms are Haskell functions  This sounds like a complicated statement  but it s actually a very trivial one  All it means is that that a Functor f      - gt    gives you the means of constructing a type f a       for any a      and a function fmap f    f a - gt  f b out of any f    a - gt  b  and that these obey the functor laws  Second clause  the Identity functor in Haskell  which comes with the Platform  so you can just import it  is defined this way  newtype Identity a   Identity   runIdentity    a    instance Functor Identity where     fmap f  Identity a    Identity  f a   So the natural transformation     I - gt  T from Tom Crockett s definition can be written this way for any Monad instance t  return     Monad t   gt  Identity  - gt  t return    Natural  return   runIdentity   Third clause  The composition of two functors in Haskell can be defined this way  which also comes with the Platform   newtype Compose f g a   Compose   getCompose    f  g a     --   The composition of two  Functor s is also a  Functor   instance  Functor f  Functor g    gt  Functor  Compose f g  where     fmap f  Compose fga    Compose  fmap  fmap f  fga   So the natural transformation      T    T - gt  T from Tom Crockett s definition can be written like this  join     Monad t   gt  Compose t t  - gt  t join    Natural  join   getCompose   The statement that this is a monoid in the category of endofunctors then means that Compose  partially applied to just its first two parameters  is associative  and that Identity is its identity element  I e   that the following isomorphisms hold   Compose f  Compose g h     Compose  Compose f g  h Compose f Identity    f Compose Identity g    g  These are very easy to prove because Compose and Identity are both defined as newtype  and the Haskell Reports define the semantics of newtype as an isomorphism between the type being defined and the type of the argument to the newtype s data constructor  So for example  let s prove Compose f Identity    f  Compose f Identity a        f  Identity a                  -- newtype Compose f g a   Compose  f  g a          f a                            -- newtype Identity a   Identity a Q E D

User · Answer

That particular phrasing is by James Iry  from his highly entertaining Brief  Incomplete and Mostly Wrong History of Programming Languages  in which he fictionally attributes it to Philip Wadler  The original quote is from Saunders Mac Lane in Categories for the Working Mathematician  one of the foundational texts of Category Theory  Here it is in context  which is probably the best place to learn exactly what it means  But  I ll take a stab  The original sentence is this   All told  a monad in X is just a monoid in the category of endofunctors of X  with product    replaced by composition of endofunctors and unit set by the identity endofunctor   X here is a category  Endofunctors are functors from a category to itself  which is usually all Functors as far as functional programmers are concerned  since they re mostly dealing with just one category  the category of types - but I digress   But you could imagine another category which is the category of  quot endofunctors on X quot   This is a category in which the objects are endofunctors and the morphisms are natural transformations  And of those endofunctors  some of them might be monads  Which ones are monads  Exactly the ones which are monoidal in a particular sense  Instead of spelling out the exact mapping from monads to monoids  since Mac Lane does that far better than I could hope to   I ll just put their respective definitions side by side and let you compare  A monoid is     A set  S An operation        S    S   S An element of S  e   1   S     satisfying these laws    a     b      c   a      b     c   for all a  b and c in S e     a   a     e   a  for all a in S  A monad is     An endofunctor  T   X   X  in Haskell  a type constructor of kind   - gt    with a Functor instance  A natural transformation       T    T   T  where    means functor composition     is known as join in Haskell  A natural transformation      I   T  where I is the identity endofunctor on X    is known as return in Haskell      satisfying these laws         T             T       T           T   1  the identity natural transformation   With a bit of squinting you might be able to see that both of these definitions are instances of the same abstract concept

User · Answer

The answers here do an excellent job in defining both monoids and monads  however  they still don t seem to answer the question      And on a less important note  is this true and if so could you give an explanation  hopefully one that can be understood by someone who doesn t have much Haskell experience     The crux of the matter that is missing here  is the different notion of  monoid   the so-called categorification more precisely  -- the one of monoid in a monoidal category  Sadly Mac Lane s book itself makes it very confusing      All told  a monad in X is just a monoid in the category of endofunctors of X  with product    replaced by composition of endofunctors and unit set by the identity endofunctor    Main confusion  Why is this confusing  Because it does not define what is  monoid in the category of endofunctors  of X  Instead  this sentence suggests taking a monoid inside the set of all endofunctors together with the functor composition as binary operation and the identity functor as a monoidal unit  Which works perfectly fine and turns into a monoid any subset of endofunctors that contains the identity functor and is closed under functor composition   Yet this is not the correct interpretation  which the book fails to make clear at that stage  A Monad f is a fixed endofunctor  not a subset of endofunctors closed under composition  A common construction is to use f to generate a monoid by taking the set of all k-fold compositions f k   f f       of f with itself  including k 0 that corresponds to the identity f 0   id  And now the set S of all these powers for all k gt  0 is indeed a monoid  with product    replaced by composition of endofunctors and unit set by the identity endofunctor     And yet    This monoid S can be defined for any functor f or even literally for any self-map of X  It is the monoid generated by f  The monoidal structure of S given by the functor composition and the identity functor has nothing do with f being or not being a monad    And to make things more confusing  the definition of  monoid in monoidal category  comes later in the book as you can see from the table of contents  And yet understanding this notion is absolutely critical to understanding the connection with monads    Strict  monoidal categories  Going to Chapter VII on Monoids  which comes later than Chapter VI on Monads   we find the definition of the so-called strict monoidal category as triple  B     e   where B is a category     B x B- gt  B a bifunctor  functor with respect to each component with other component fixed  and e is a unit object in B  satisfying the associativity and unit laws     a   b    c   a    b   c  a   e   e   a   a   for any objects a b c of B  and the same identities for any morphisms a b c with e replaced by id e  the identity morphism of e  It is now instructive to observe that in our case of interest  where B is the category of endofunctors of X with natural transformations as morphisms    the functor composition and e the identity functor  all these laws are satisfied  as can be directly verified   What comes after in the book is the definition of the  relaxed  monoidal category  where the laws only hold modulo some fixed natural transformations satisfying so-called coherence relations  which is however not important for our cases of the endofunctor categories   Monoids in monoidal categories  Finally  in section 3  Monoids  of Chapter VII  the actual definition is given      A monoid c in a monoidal category  B     e  is an object of B with two arrows  morphisms     mu  c   c - gt  c nu  e - gt  c   making 3 diagrams commutative  Recall that in our case  these are morphisms in the category of endofunctors  which are natural transformations corresponding to precisely join and return for a monad  The connection becomes even clearer when we make the composition   more explicit  replacing c   c by c 2  where c is our monad   Finally  notice that the 3 commutative diagrams  in the definition of a monoid in monoidal category  are written for general  non-strict  monoidal categories  while in our case all natural transformations arising as part of the monoidal category are actually identities  That will make the diagrams exactly the same as the ones in the definition of a monad  making the correspondence complete   Conclusion  In summary  any monad is by definition an endofunctor  hence an object in the category of endofunctors  where the monadic join and return operators satisfy the definition of a monoid in that particular  strict  monoidal category  Vice versa  any monoid in the monoidal category of endofunctors is by definition a triple  c  mu  nu  consisting of an object and two arrows  e g  natural transformations in our case  satisfying the same laws as a monad   Finally  note the key difference between the  classical  monoids and the more general monoids in monoidal categories  The two arrows mu and nu above are not anymore a binary operation and a unit in a set  Instead  you have one fixed endofunctor c  The functor composition   and the identity functor alone do not provide the complete structure needed for the monad  despite that confusing remark in the book    Another approach would be to compare with the standard monoid C of all self-maps of a set A  where the binary operation is the composition  that can be seen to map the standard cartesian product C x C into C  Passing to the categorified monoid  we are replacing the cartesian product x with the functor composition    and the binary operation gets replaced with the natural transformation mu from  c   c to c  that is a collection of the join operators   join  c c T  - gt c T    for every object T  type in programming   And the identity elements in classical monoids  which can be identified with images of maps from a fixed one-point-set  get replaced with the collection of the return operators   return  T- gt c T     But now there are no more cartesian products  so no pairs of elements and thus no binary operations

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

Examples related to haskell

Examples related to monads

Examples related to category-theory

Examples related to monoids