Monads and Maybe

[Ross Paterson]

On Thu, Aug 21, 2003 at 11:32:47AM +0100, C T McBride wrote:
> My point, however, is not to use <$> with that type, but the more general
> 
>   class Fun f where
>     eta :: x -> f x
>     (<$>) :: f (s -> t) -> f s -> f t
> 
> Is there a better name for Fun? Is it ancient and venerable? Am I an
> ignoramus twice over?

It seems that something this useful should have a name, but I've been
unable to find one.  This interface was first used for parsers by
Niklas Rojemo.  Doaitse Swierstra has developed a lot of interesting
parsers with this interface, roughly

	infixl 4 <$>, <*>

	class Functor f => Sequence f where
		eta :: a -> f a
		(<*>) :: f (a -> b) -> f a -> f b

		(<$>) :: (a -> b) -> f a -> f b
		(<$>) = fmap

One would expect this to satisfy identity and associativity laws:

	eta f <*> v = f <$> v
	u <*> eta y = ($ y) <$> u
	u <*> (v <*> w) = ((.) <$> u <*> v) <*> w

as well as naturality of eta and (<*>).

Several other choices of primitives are available.  One is:

	lift0 :: a -> f a
	lift1 :: (a -> b) -> f a -> f b
	lift2 :: (a -> b -> c) -> f a -> f b -> f c

	lift0 = eta
	lift1 = fmap
	lift2 f fa fb = f <$> fa <*> fb
	(<*>) = lift2 ($)

Another interface is eta plus

	mult :: f a -> f b -> f (a,b)

with axioms

	eta x `mult` v = fmap (\y -> (x,y)) v
	u `mult` eta y = fmap (\x -> (x,y)) u
	u `mult` (v `mult` w) = fmap assoc ((u `mult` v) `mult` w)
		where	assoc ((x,y),z) = (x,(y,z))

These are all equivalent (or would be, if Haskell had true products).

The last version generalizes to any symmetric monoidal category: it
requires that f be a lax monoidal functor, with eta_1 and mult as the
transformations, that eta is a transformation from the identity monoidal
functor to f, plus the symmetry condition

	eta x `mult` v = fmap swap (v `mult` eta x)

As you note, they're preserved under composition.  They also compose
with arrows (in the sense of Hughes) to make new arrows, and they're
preserved by products (as are arrows).