Ross Paterson ross@soi.city.ac.uk
Sat, 23 Aug 2003 13:32:43 +0100

```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).

```