data Eq a b = Eq (forall f. f a -> f b)

Eq is given kind

Eq :: forall a . a -> a -> *

and both Eq Integer Char and Eq [] Maybe are valid types.

Using kind polymorphism, it is possible to write sigfpe's From monoids to monads using a single type class.

To talk about monoids, you need a category (mor), multiplication (mul) and a unit.

class Monoid mor mul unit m where

one :: mor unit m

mult :: mor (mul m m) m

With mor being (->), mul being (,), unit being () this is a normal monoid (one :: () -> m and mult :: (m,m) -> m.). For example:

instance Monoid (->) (,) () Integer where

one () = 1

mult = uncurry (*)

Now, instead of functions, there will be natural transformations; instead of (,) there will be functor composition; instead of unit there will be identity functor.

data Nat f g = Nat (forall x. f x -> g x)

data Comp f g x = Comp (f (g x))

data Id x = Id x

Nat :: (* -> *) -> (* -> *) -> *

Comp :: (* -> *) -> (* -> *) -> * -> *

Id :: * -> *

And here is the list monad. Notice kinds are different than in the previous case, but it is still an instance of the same type class.

instance Monoid Nat Comp Id [] where

one = Nat $ \(Id x) -> [x] -- one :: Nat Id []

mult = Nat $ \(Comp x) -> concat x -- mult :: Nat (Comp [] []) []

So, monads are really monoids in category of endofunctors.

If you invert the arrows, you get a comonad. Here's the product comonad.

data CoNat f g = CoNat (forall x. g x -> f x)

data CoComp f g x = CoComp (g (f x))

CoNat :: (* -> *) -> (* -> *) -> *

CoComp :: (* -> *) -> (* -> *) -> * -> *

data Product w a = Product w a

instance Monoid CoNat CoComp Id (Product w) where

one = CoNat $ \(Product a b) -> Id b

mult = CoNat $ \(Product a b) -> CoComp $ Product a (Product a b)

Question: what are kinds of mor, mul, unit and m in the Monoid type class definition?

There's a small lie here: monads require also a liftM/fmap function. Not all Haskell types of * -> * are functors, and I used that as a poor replacement.

I didn't write monoid laws, which if translated happen to be monad laws. You're welcome to read sigfpe's original post. It's hard to write them generically since there's no access to fmap.

The code is available on hpaste and can be run in UHC.

## 4 comments:

This is pretty neat. I've been thinking of following up my article on monoids and monads with some examples of the consequences. I'll have to think about whether I'd be better off using UHC.

Unfortunately UHC is limited; as far as I know, it doesn't have interactive mode, and error messages are often cryptic. It's good for experimentation though. I'm trying to express other examples of monoids, but it's hard.

Shouldn't this generic instance also work?

instance Monoid Nat Comp Id m where

one = Nat $ \(Id x) -> return x

mult = Nat $ \(Comp x) -> join x

It works, but with Monad m constraint.

instance Monad m => Monoid Nat Comp Id m where

one = Nat $ \(Id x) -> return x

mult = Nat $ \(Comp x) -> join x

Same could be done with Monoid, but there's name clash. Renaming the generic Monoid to Mon, the following compiles.

instance Monoid m => Mon (->) (,) () m where

one () = mempty

mult = uncurry mappend

[The required functions are in Control.Monad and Data.Monoid respectively.]

Post a Comment