[Haskell-cafe] The mother of all functors/monads/categories

[Max Bolingbroke]

I'm wondering if someone can cast some light on a pattern I've come
across, which I'm calling the "mother of all X" pattern after Dan
Piponi's blog post
(http://blog.sigfpe.com/2008/12/mother-of-all-monads.html). Edward
Kmett has also explored these ideas here:
http://www.mail-archive.com/haskell-cafe@haskell.org/msg57738.html

Preliminaries
===

Q: What is the "mother of all X", where X is some type class?
A: It is a data type D such that:

1. There exist total functions:

> lift :: X d => d a -> D a
> lower :: X d => D a -> d a

2. And you can write a valid instance:

> instance X D

With *no superclass constraints*.

3. (We may also add the constraint that D is somehow the "smallest
such" data type, but I don't know in exactly what sense I mean this).

So the "mother of all X" is a data type that somehow encodes all of
the functions that the X type class gives you.

An example is in order!


Example 1: Yoneda is the mother of all Functors
===

The code in this example and the next one is shamelessly stolen from
the category-extras package (thanks Edward!). Here is the data type:

> -- flip fmap :: forall a. f a -> (forall b. (a -> b) -> f b)
> newtype Yoneda f a = Yoneda { runYoneda :: forall b. (a -> b) -> f b }

And the injections. As it turns out, we don't need the Functor
constraint on the lowerYoneda call:

> liftYoneda :: Functor f => f a -> Yoneda f a
> liftYoneda f = Yoneda (flip fmap f)
>
> lowerYoneda :: Yoneda f a -> f a
> lowerYoneda f = runYoneda f id

Finally, we can write the Functor instance. Notice that we don't need
to make use of the Functor instance for f: all of the methods of
Functor f have been somehow encoded into the Yoneda data type!

> instance Functor (Yoneda f) where
>    fmap f m = Yoneda (\k -> runYoneda m (k . f))

Note that we can also write an instance (Y f => Y (Yoneda f)) for any
Functor subclass Y. But (Yoneda f) is not the mother of all Y, because
we will need the Y f constraint to do so. Here is an example:

> instance Applicative f => Applicative (Yoneda f) where
>     pure = liftYoneda . pure
>     mf <*> mx = liftYoneda (lowerYoneda mf <*> lowerYoneda mx)

Why is (Yoneda f) interesting? Because if I take some expression whose
type is quantified over any superclass of Functor, and we want to run
it with Functor instantiated to some F, if we instead run it with
Functor instantiated to (Yoneda f) and then use lowerYoneda, we will
automatically get guaranteed fmap fusion.


Example 2: Codensity is the mother of all Monads
===

Data type:

> -- (>>=)  :: forall a. m a -> (forall b. (a -> m b) -> m b)
> newtype Codensity m a = Codensity { runCodensity :: forall b. (a -> m b) -> m b }

Isomorphism. We need Monad constraints on both ends now:

> liftCodensity :: Monad m => m a -> Codensity m a
> liftCodensity m = Codensity ((>>=) m)
>
> lowerCodensity :: Monad m => Codensity m a -> m a
> lowerCodensity m = runCodensity m return

Instances:

> instance Functor (Codensity f) where
>     fmap f m = Codensity (\k -> runCodensity m (k . f))
>
> instance Applicative (Codensity f) where
>     pure x = Codensity (\k -> k x)
>     mf <*> mx = Codensity (\k -> runCodensity mf (\f -> runCodensity mx (\x -> k (f x))))
>
> instance Monad (Codensity f) where
>     return = pure
>     m >>= k = Codensity (\c -> runCodensity m (\a -> runCodensity (k a) c))

Again, using (Codensity m) where you used m before can yield a
performance improvement, notably in the case of free monads. See
http://haskell.org/haskellwiki/Performance/Monads or
http://wwwtcs.inf.tu-dresden.de/~voigt/mpc08.pdf.


Example 3: Wotsit is the mother of all Categories
===

I don't actually know what the right name for this data type is, I
just invented it and it seems to work:

> -- (>>>) :: forall a b. t a b -> (forall c. t b c -> t a c)
> newtype Wotsit t a b = Wotsit { runWotsit :: forall c. t b c -> t a c }

Isomorphism:

> liftWotsit :: Category t => t a b -> Wotsit t a b
> liftWotsit t = Wotsit ((>>>) t)
>
> lowerWotsit :: Category t => Wotsit t a b -> t a b
> lowerWotsit t = runWotsit t id

And finally the instance:

> instance Category (Wotsit t) where
>     id = Wotsit id
>     t1 . t2 = Wotsit (runWotsit t2 . runWotsit t1)

This is *strongly* reminiscent of normalisation-by-evaluation for
monoids (reassociation realised by assocativity of function
application), which is not surprising because Category is just a
monoid. There is probably some connection between NBE and Yoneda (e.g.
"Normalization and the Yoneda embedding", but I can't get access to
this paper electronically).


Conclusion
===

So I have a lot of questions about this stuff:

1. Is there a way to mechanically derive the "mother of all X" from
the signature of X? Are these all instances of a single categorical
framework?
2. Is there a mother of all idioms? By analogy with the previous three
examples, I tried this:

> -- (<**>) :: forall a. i a -> (forall b. i (a -> b) -> i b)
> newtype Thingy i a = Thingy { runThingy :: forall b. i (a -> b) -> i b }

But I can't see how to write either pure or <*> with that data type.
This version seems to work slightly better:

> newtype Thingy i a = Thingy { runThingy :: forall b. Yoneda i (a -> b) -> i b }

Because you can write pure (pure x = Thingy (\k -> lowerYoneda (fmap
($ x) k))). But <*> still eludes me!

3. Since (Codensity m) enforces >>= associativity, perhaps it can be
used to define correct-by-construction monads in the style of
operational or MonadPrompt?

Any insight offered would be much appreciated :-)

Cheers,
Max