Functor => Pointed => Applicative => Monad
wren ng thornton
wren at freegeek.org
Sat Dec 4 07:25:26 CET 2010
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
More information about the Libraries
mailing list