Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Can liftM differ from liftA?

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?

like image 870
Doug McClean Avatar asked Oct 28 '09 02:10

Doug McClean


2 Answers

liftA, liftM, fmap, and . should all be the same function, and they must be if they satisfy the functor law:

fmap id = id

However, this is not checked by Haskell.

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 and the laws. 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, both of which satisfy the laws. But if your monads and your applicative functors disagree, it's considered good form to have different types for them. For example, the Applicative instance above does not agree with the monad for [], so you should really say newtype ZipList a = ZipList [a] and then make the new instance for ZipList instead of [].

like image 59
13 revs Avatar answered Nov 15 '22 18:11

13 revs


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.

like image 29
Martijn Avatar answered Nov 15 '22 18:11

Martijn