Refactoring Semigroup/Monoid (was: instance Applicative Data.Map)

[Tyson Whitehead]

On November 17, 2012 11:18:46 Edward Kmett wrote:
> Honestly, the main issue is that even if you have the ability to describe
> default definitions for how to implement superclasses, it isn't really all
> that useful. :(

I was wondering about the solution demonstrated in the following example of a 
re-implementation of the standard Functor, Applicative, Monad hierarchy

  class Functor f where
    functor_map :: (a -> b) -> f a -> f b

  class Applicative f where  -- add appropriate defaults for the first bunch
    applicative_map :: (a -> b) -> f a -> f b
    applicative_pure :: a -> f a
    applicative_apply :: f (a -> b) -> f a -> f b

  class Monad m where  -- add appropriate defaults for the first bunch
    monad_map :: (a -> b) -> m a -> m b
    monad_pure :: a -> m a
    monad_apply :: m (a -> b) -> m a -> m b
    monad_join :: m (m a) -> m a
    monad_bind :: m a -> (a -> m b) -> m b

with the following functions

  fmap :: Functor f => (a -> b) -> f a -> f b
  fmap = functor_map

  pure :: Applicative f => a -> f a
  pure = applicative_pure
  (<*>) :: Applicative f => f (a -> b) -> f a -> f b
  (<*>) = applicative_apply

  return :: Monad m => a -> m a
  return = monad_pure
  (>>=) :: Monad m => m a -> (a -> m b) -> m b
  (>>=) = monad_bind

and the following instances

  instance Monad m => Applicative m where
    applicative_map = monad_map
    applicative_pure = monad_pure
    applicative_apply = monad_apply

  instance Applicative f => Functor f where
    functor_map = applicative_map

With this, providing instance at all levels is as easy as

  instance Monad [] where
    monad_join xss = [x | xs <- xss, x <- xs]
    monad_bind xs f = [y | x <- xs, y <- f x]
    monad_apply fs xs = [f x | f <- fs, x <- xs]
    monad_map f xs = [f x | x <- xs]
    monad_pure x = [x]

GHC 7.0.4 accepts this with FlexibleInstances and UndecidableInstances, but it 
seems to still have some issues (features?) as it overrides signatures

  *Main> :t pure
  pure :: Monad f => a -> f a

unless you add other instances that are only at the lowel levels.  For 
example, adding Maybe at the Applicative level to the above [] instance

  instance Applicative Maybe where
    applicative_apply (Just f) (Just x) = Just (f x)
    applicative_apply _        _        = Nothing
    applicative_map f (Just x) = Just (f x)
    applicative_map _ _        = Nothing
    applicative_pure x = Just x

gives

  *Main> :t pure
  pure :: Monad f => a -> f a
  *Main> :t Main.fmap
  Main.fmap :: Applicative f => (a -> b) -> f a -> f b

Cheers!  -Tyson