48

Can someone explain in simple terms the difference between the two? I'm not fully understanding the part where monads are endofunctors versus being just functors.

tharindu_DG
  • 8,900
  • 6
  • 52
  • 64
Jonathan Dunlap
  • 2,581
  • 3
  • 19
  • 22

1 Answers1

63

A functor may go from one category to a different one, an endofunctor is a functor for which start and target category are the same.

Same as with endomorphisms versus morphisms.

Now, why must monads be endofunctors?

There is the famous quote that "Monads are just monoids in the category of endofunctors". Fortunately, somebody else has already explained that rather well in this answer.

The key point why a monad has to be an endofunctor, is that join, as it is called in Haskell, or µ, as it is usually called in category theory, is part of the definition¹ of a monad. Now

Prelude Control.Monad> :t join
join :: Monad m => m (m a) -> m a

so the result of applying the functor m to an object (in Hask, the category of Haskell types as objects and functions as morphisms, a type) must be an object that m can again be applied to. That means it must belong to the category that is the domain of the functor m.

A functor can only be composed with itself if its domain and codomain are the same [strictly, if its codomain is a subcategory of its domain], in other words, if it is an endofunctor. Since composability with itself is part of the definition of a monad, monads are a fortiori endofunctors.

¹ One definition, one can alternatively define a monad using (>>=) or bind and have join as a derived property.

Community
  • 1
  • 1
Daniel Fischer
  • 181,706
  • 17
  • 308
  • 431
  • 6
    Are there any functors in Haskell that aren't endofunctors? (Don't they all map Hask to Hask?) – huon Apr 26 '12 at 23:58
  • 6
    Right, all Haskell functors are endo. – Daniel Fischer Apr 27 '12 at 00:04
  • 3
    Non-endofunctors are available in packages such as http://hackage.haskell.org/packages/archive/categories/1.0/doc/html/Control-Categorical-Functor.html – sdcvvc Apr 27 '12 at 01:12
  • The `Functor` class corresponds to endofunctors. But it's possible to have non-endofunctors in Haskell, I think: `arr` from `Control.Arrow` may be one. – Ben Millwood Apr 27 '12 at 11:33
  • So to put it all together: the prelude `Functor` class are endofunctors in the category Hask (the category of haskell types as objects, functions as morphisms)... is that right? – jberryman Apr 27 '12 at 17:11
  • @jberryman Yes, that's right (perhaps modulo some problems with nonstrictness, I'm not quite sure whether Hask strictly is a category). – Daniel Fischer Apr 27 '12 at 17:20
  • >> But, monoids are not functors... explain more please? – Jonathan Dunlap Apr 27 '12 at 19:33
  • 1
    @JonathanDunlap It just occurred to me, did you mistype and actually mean _monads_, and not monoids? As in, "Monads are monoids in the category of Endofunctors", or what the saying was? – Daniel Fischer Apr 27 '12 at 19:34
  • @DanielFischer, you're correct sir... fixed the question. However, don't monoids also apply since monads are just a special form of monoids? – Jonathan Dunlap Apr 27 '12 at 19:36
  • 2
    @JonathanDunlap Okay, going to update the answer accordingly (will take a while, though, I'm slow). Monoids are a different kind of beast, it's just that some functors (monads, for instance) are also monoids (in some category). Sort of incidental. – Daniel Fischer Apr 27 '12 at 19:40
  • @JonathanDunlap Updated answer, surprisingly fast. – Daniel Fischer Apr 27 '12 at 20:03
  • Assuming `[]` is an endofunctor in Hask. Does it mean that it maps types to types in Hask as `a -> [a]`, and morphisms to morphisms in Hask as `(a -> b) -> [(a -> b)]`? Thus does that mean all polymorphic constructors in Haskell functors. But what is stopping me from creating a function in Hask `a -> b` and then just assigning b to be `[a]`? Doesn't that mean `a -> [a]` could be conceptualised as a functor or a morphism? – CMCDragonkai Mar 10 '15 at 11:57
  • 1
    @CMCDragonkai It maps types `a ~> [a]` indeed, but morphisms are mapped `(a -> b) ~> ([a] -> [b])` [via `f ~> map f`]. Not all polymorphic constructors are functors, `newtype Foo a = Foo { unFoo :: a -> Integer }` is contravariant, so not a functor but a cofunctor. `newtype Bar a = Bar { unBar :: a -> a }` has mixed variance, so is neither functor nor cofunctor. I'm not sure what you mean in the last questions, can you clarify them? – Daniel Fischer Mar 10 '15 at 12:13
  • My last question was more about thinking that functors and morphisms seem awfully the same. But I remember another resource mentioning that a functor is a like a collection of morphisms. So the `[]` functor is not just a single morphism `a -> [a]` but all of the morphisms including `b -> [b]` and `c -> [c]` and so on... thus the idea that "a functor is a polymorphic function". Furthermore I am reminded of the commutative diagram of the functor visualising a functor mapping morphism to morphism as 2 morphisms mapping source to source and target to target. – CMCDragonkai Mar 10 '15 at 12:58