Functor => Pointed => Applicative => Monad

[wren ng thornton]

On 12/2/10 4:41 PM, Tyson Whitehead wrote:
> On November 30, 2010 00:32:18 wren ng thornton wrote:
>> Essentially, for T :: * ->  *, pointedness is saying that there is a
>> trivial embedding of the parameter, a, into T a; whereas functoriality
>> is saying that T is structural over its parameter. Surely the latter is
>> "more complicated", but they're rather different concepts.
>
> Hi Wren,
>
> I always enjoy your input.

Thanks :)

> Would you be able to expound on the intuition
> behind "functoriality is saying that T is structural over its parameter"?
>
> (I don't think I'm following what you mean by "stuctural over its parameter")

Well the paradigmatic (programming) examples of functors are all 
container-like structures: sets, multisets, lists, trees,...

If we look at those functors more closely, they all have a familiar 
form. In particular they are all some kind of "structure", typically a 
set-theoretic or graphical structure built on top of some values of the 
parameter type. But the structure itself does not care what the 
parameter type is because it never peers inside those values--- it's 
just some kind of scaffolding that sits atop the parametric holes. So 
functors just build up some kind of structure on top of its parameter.[1]

This sort of parametricity is required for all functors, in fact it is 
exactly this requirement that is captured by the type fmap at F :: forall a 
b. (a->b) -> F a -> F b, with the associated functor laws. The functor 
laws are there to prevent vacuous or trivial definitions of the type 
(e.g., taking every F a to the empty F b), in order to ensure that the 
definition of fmap behaves in the way we expect for structures over an 
arbitrary type.

The intuition of functors capturing structure is closely related to the 
intuition of monads capturing structure[2]. The dual intuition is that 
functors capture context (a la comonads capture context). When expressed 
as an intuition about functors, these are the same idea, since we like 
to think of contexts as structures with holes in them where the 
structure doesn't care about what fills the holes.


[1] Though note that these aren't necessarily structures over the 
*values* of the parameter. For example, the vacuous functor:

     data Vac a = Vac

     instance Functor Vac where
         fmap f Vac = Vac

But there are more interesting examples too (non-pointed ones even):

     data SliceOver a b = SliceOver (a->b)

     instance Functor (SliceOver a) where
         fmap f (SliceOver g) = SliceOver (f . g)


     data SliceUnder a b = SliceUnder (b->a)

     instance Functor (SliceUnder a) where
         fmap f (SliceUnder g) = SliceUnder (g . f)


[2] As opposed to the intuition of monads as capturing control.

-- 
Live well,
~wren