The FunctorM library
Ross Paterson
ross at soi.city.ac.uk
Thu Mar 24 06:04:29 EST 2005
On Thu, Mar 24, 2005 at 10:24:50AM +0100, Thomas Jäger wrote:
> The following distributive laws [1] might be postulated:
> 1) fsequence . fmap return === return
> 2) fsequence . return === fmap return
> 3) fsequence . fmap join === join . fmap fsequence . fsequence
also
4) fsequence . join === fmap join . fsequence . fmap fsequence
These are all necessary for the composition to be a monad.
> Identity, Maybe, Either e and Writer w (for monoids w) are perfect
> instances; the list monad doesn't obey law 3. I don't believe any of
> the monads that is based a function type can be made an instance of
> FunctorM, and if we impose additional restrictions, such as a finite
> domain in case of the reader monad, we lose laws 2 and 3.
M1 o M2 is a monad if M2 is one of those you mentioned, or if M1 is
a reader monad.
> The laws 1 and 3 can be formulated without requiring f to be a monad
> (and law 2 only needs return),
Yes, laws 1 and 3 are equivalent to saying that fmapM defines a functor
on the Kleisli category, i.e.
fmapM return = return
fmapM (f >>> g) = fmapM f >>> fmapM g
where
(>>>) :: Monad m => (a -> m b) -> (b -> m c) -> a -> m c
(f >>> g) a = f a >>= g
> but Array i, the only non-monad that
> can be made a FunctorM I'm currently aware of, only satisfies law 1.
Isn't Array i a reader monad with a finite domain? (i.e. return fills
the array with copies, and join selects the diagonal)
> [1] Barr, Wells: Toposes, Triples and Theories
> http://www.cwru.edu/artsci/math/wells/pub/ttt.html, p. 298
More information about the Libraries
mailing list