Lambda the Ultimate

• The relationship between these is that "unit" is already given by the Functor typeclass in Haskell (all Monads are Functors) and is called fmap, and "multiply" (also called "join") and "bind" (aka '>>=') can be translated into each other (when you use fmap, coming from the Functor class):
  

  join :: Monad m => m (m a) -> m a
  join x = x >>= id

  (>>=) :: Monad m => m a -> (a -> m b) -> m b
  x >>= f = join (fmap f x)
  

• it doesn't lift a value, it "lift" a function; meaning that it maps a function to a function who do "the same thing" (in a category-theoric sense), but inside the monad.
• Yes, with usual categorical interpretations of types, "one object" would mean "one type".

Btw, this wikibook is quite nice at explaining category theory as far as it concern Haskell.

A monoid is "a small category of one object". Is "one object" used here to mean something like "values of only one type"?

In a monoid, you can multiply any two elements together to get a third element. There are no restrictions on what you can multiply.

In a category, each arrow points from one object to another - from the domain to the range. If we want to multiply (ie. compose) two arrows, f and g, to get fg, then the range of g must equal the domain of f. This is a restriction which prevents us from just multiplying arrows arbitrarily. However, if a category as just one object, this constraint is redundant as every arrow will have a range that equals the domain of every other arrow. At this point we can multiply freely and have a monoid. The "smallness" is a technical issue that ensures that the set of arrows forms a bona fide set (as opposed to a class).

Why is the (sub)category of (small) one object categories not isomorphic to the category of monoids and monoid homomorphisms? (It is equivalent.)

1) η is, as should be clear, return. μ is join in Haskell and is related to (>>=) as demonstrated by renaud.

2) You can often think something like that, but not always. At any rate, it's probably best to be precise with language in this case. "The monad" is the triple (T,η,μ). It is probably best not to add any baggage to η or μ and instead see what the properties of them imply and to look at examples with the understanding that they are just particular cases.

3) It would be more like having only one type, but really the object is just there so we can have arrows, it's not important what it is. See the exercise I mentioned in different part of this thread.

η is, as should be clear, return. μ is join in Haskell and is related to (>>=) as demonstrated by renaud.

Is η also fmap as suggested by renaud?

3) It would be more like having only one type, but really the object is just there so we can have arrows, it's not important what it is. See the exercise I mentioned in different part of this thread.

So, when one says 'only one object' it's sort of like saying: "We only need one letter to show you what's going on here -- whereas we need more letters for general categories, since the letters help us sort out what's on the end of the arrows." ?

η is not fmap. fmap is usually written by applying the functor to an arrow so for an object A, TA is the action of the functor T on A and for an arrow f : A → B, Tf : FA → FB is the action of the functor on arrows. These correspond respectively to applying a type constructor to another type and applying fmap to a function.

I'm not quite sure what you mean by "letter" but if you mean it in an abstract way, then yes. A category is a generalization of a monoid (it's also a generalization of a pre-ordered set, and usually this latter view is more useful). It can be viewed as a "typed" monoid.

I don't know if these kind of videotaped class are useful for outsiders, the problem is that they rely on many knowledge which isn't available: in the first 5 minute: what's difference between a function and a functor? 'There is a double arrow because it's a natural transformation', ok what is a natural transformation? Etc.

I, for one, have a great deal more patience with listening to things I can't understand, and piecing them together as I go, than I do with reading things I don't understand and piecing them together later. It's fair to say there's not enough videos out there now to fill in the gaps left by all the other videos -- but that is likely to change in even 5 years time.

Wikipedia does a reasonably good job of explaining functors although it might be useful to read morphism first.

Natural, often canonical, means that there are no choices involved. It's one of those annoying ideas that is really simple but strangely difficult to communicate. My aha-moment was with this example:

If V is a two dimensional real vector space then linear maps from V to the reals (V* said V dual) is also a two dimensional real vector space but to map between them you need to make a choice (of coordinates).

Now, abstractly and with no coordinates, if p is in V, then for any f or g in V* we can take f or g to the reals by evaluation (e.g. f(p) or g(p)). In fact,p is linear map of V* (e.g. in V**) as f(p)+g(p) = (f+g)(p), O(p)=0, etc. As such there is a canonical map from V to V**.

If you have a pair of functors, F and G, then a natural transformation gives you a mapping from FX to GX for every choice of object X, and those mappings have to satisfy certain conditions.

Consider a polymorphic Haskell function like

f :: a -> [a]
f x = [x]

For each choice of type a you get a function from a to [a]. So this is like a natural transformation from the identity functor to the list functor [].

The compatibility conditions say that if you have a function p:X -> Y, then it shouldn't matter whether you do f or p first, you'll get the same result.

So we'd like f (p x) = fmap p (f x).

This is easy to prove. It works because f is polymorphic in a natural way - it doesn't do any kind of special case handling that might treat one type differently from another. For example, it'd break if we somehow overrode f so that when f was applied to an Int it returned [] but in every other case it returned [x]. So in Haskell 'natural', means a polymorphic function that handles all types in a 'uniform' way. The correct term is 'parametricity' and the naturality conditions turn out to be Theorems for Free. And of course this works with any functors and polymorphic functions, not just x -> [x].

You can kinda see the parallel with vector spaces. A linear map is natural if it doesn't make use of knowledge about a specific basis. Similarly a natural polymorphic function shouldn't use any knowledge about the type it is applied to.

I find the polymorphic function example so compelling that it is now my mental protoype for naturality despite having come through a traditional mathematical training (including linear algebra and algebraic topology).