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@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