[Haskell-cafe] Type classes

[Tom Ellis]

On Tue, May 28, 2013 at 05:21:58PM +0200, Johannes Gerer wrote:
> That makes sense. But why does
> 
> instance Monad m => ArrowApply (Kleisli m)
> 
> show that a Monad can do anything an ArrowApply can (and the two are
> thus equivalent)?

I've tried to chase around the equivalence between these two before, and
I didn't find the algebra simple.  I'll give an outline.

In non-Haskell notation

1) instance Monad m => ArrowApply (Kleisli m)

means that if "m" is a Monad then "_ -> m _" is an ArrowApply.

2) instance ArrowApply a => Monad (a anyType)

means that if "_ ~> _" is an ArrowApply then "a ~> _" is a Monad.

One direction seems easy: for a Monad m, 1) gives that "_ -> m _" is an
ArrowApply.  By 2), "() -> m _" is a Monad.  It is equivalent
to the Monad m we started with.

Given an ArrowApply "_ ~> _", 2) shows that "() ~> _" is a Monad.  Thus by
1) "_ -> (() ~> _)" is an ArrowApply.  I believe this should be the same
type as "_ ~> _" but I don't see how to demonstrate the isomorphsim here.

Tom