views:

373

answers:

2

According to the Typeclassopedia (among other sources), Applicative logically belongs between Monad and Pointed (and thus Functor) in the type class hierarchy, so we would ideally have something like this if the Haskell prelude were written today:

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

class Functor f => Pointed f where
    pure :: a -> f a

class Pointed f => Applicative f where
    (<*>) :: f (a -> b) -> f a -> f b

class Applicative m => Monad m where
    -- either the traditional bind operation
    (>>=) :: (m a) -> (a -> m b) -> m b
    -- or the join operation, which together with fmap is enough
    join :: m (m a) -> m a
    -- or both with mutual default definitions
    f >>= x = join ((fmap f) x)
    join x = x >>= id
    -- with return replaced by the inherited pure
    -- ignoring fail for the purposes of discussion

(Where those default definitions were re-typed by me from the explanation at Wikipedia, errors being my own, but if there are errors it is at least in principle possible.)

As the libraries are currently defined, we have:

liftA :: (Applicative f) => (a -> b) -> f a -> f b
liftM ::       (Monad m) => (a -> b) -> m a -> m b

and:

(<*>) :: (Applicative f) => f (a -> b) -> f a -> f b
ap    ::       (Monad m) => m (a -> b) -> m a -> m b

Note the similarity between these types within each pair.

My question is: are liftM (as distinct from liftA) and ap (as distinct from <*>), simply a result of the historical reality that Monad wasn't designed with Pointed and Applicative in mind? Or are they in some other behavioral way (potentially, for some legal Monad definitions) distinct from the versions that only require an Applicative context?

If they are distinct, could you provide a simple set of definitions (obeying the laws required of Monad, Applicative, Pointed, and Functor definitions described in the Typeclassopedia and elsewhere but not enforced by the type system) for which liftA and liftM behave differently?

Alternatively, if they are not distinct, could you prove their equivalence using those same laws as premises?

+8  A: 

For a given type, liftA, liftM, fmap, and . are all necessarily the same function. For any covariant functor, there exists one and only one implementation that satisfies the type. I.e. for a given type constructor, only one Functor instance exists. For a given type constructor f, fmap and fmap', both of type (a -> b) -> f a -> f b, satisfy the functor laws. By the functor laws, fmap id == id and fmap' id == id. Thus, fmap == fmap'.

Now for Applicative. It's possible for ap and <*> to be distinct for some functors simply because there could be more than one implementation that satisfies the types. For example, List has more than one possible Applicative instance. You could declare an applicative as follows:

instance Applicative [] where
  (f:fs) <*> (x:xs) = f x : fs <*> xs
  _      <*> _      = []
  pure              = repeat

The ap function would still be defined as liftM2 id, which is the Applicative instance that comes for free with every monad. But here you have an example of a type constructor having more than one applicative instance.

Apocalisp
OK, that's true, there is more than one Applicative instance and more than one Monad instance for some types. But, under the definitions above the pure/return implementation would have to be shared between the Applicative instance and the Monad instance. Does this mean that, to satisfy the laws, that <*> and ap would have to be the same? It looks like your example relies on making an Applicative instance for [] with pure = repeat, but still using the Prelude Monad instance for [] with return = ([])?
Doug McClean
You could definitely have two instances of Pointed [], one for pure x = [x] and another for pure = repeat.
Apocalisp
+4  A: 

They can differ, but they shouldn't.

They can differ because they can have different implementations: one is defined in an instance Applicative while the other is defined in an instance Monad. But if they indeed differ, then I'd say the programmer who wrote those instances wrote misleading code.

You are right: the functions exist as they do for historical reasons. People have strong ideas about how things should have been.

Martijn