Is it better to define Functor in terms of Applicative in terms of Monad, or vice versa?

Question

This is a general question, not tied to any one piece of code.

Say you have a type T a that can be given an instance of Monad. Since every monad is an Applicative by assigning pure = return and (<*>) = ap, and then every applicative is a Functor via fmap f x = pure f <*> x, is it better to define your instance of Monad first, and then trivially give T instances of Applicative and Functor?

It feels a bit backward to me. If I were doing math instead of programming, I would think that I would first show that my object is a functor, and then continue adding restrictions until I have also shown it to be a monad. I know Haskell is merely inspired by Category Theory and obviously the techniques one would use when constructing a proof aren't the techniques one would use when writing a useful program, but I'd like to get an opinion from the Haskell community. Is it better to go from Monad down to Functor? or from Functor up to Monad?

Answer 1

I tend to write and see written the Functor instance first. Doubly so because if you use the LANGUAGE DeriveFunctor pragma then data Foo a = Foo a deriving ( Functor ) works most of the time.

The tricky bits are around agreement of instances when your Applicative can be more general than your Monad. For instance, here's an Err data type

data Err e a = Err [e] | Ok a deriving ( Functor )

instance Applicative (Err e) where
  pure = Ok
  Err es <*> Err es' = Err (es ++ es')
  Err es <*> _       = Err es
  _      <*> Err es  = Err es
  Ok  f  <*> Ok  x   = Ok (f x)

instance Monad (Err e) where
  return = pure
  Err es >>= _ = Err es
  Ok  a  >>= f = f a

Above I defined the instances in Functor-to-Monad order and, taken in isolation, each instance is correct. Unfortunately, the Applicative and Monad instances do not align: ap and (<*>) are observably different as are (>>) and (*>).

Err "hi" <*>  Err "bye" == Err "hibye"
Err "hi" `ap` Err "bye" == Err "hi"

For sensibility purposes, especially once the Applicative/Monad Proposal is in everyone's hands, these should align. If you defined instance Applicative (Err e) where { pure = return; (<*>) = ap } then they will align.

But then, finally, you may be capable of carefully teasing apart the differences in Applicative and Monad so that they behave differently in benign ways---such as having a lazier or more efficient Applicative instance. This actually occurs fairly frequently and I feel the jury is still a little bit out on what "benign" means and under what kinds of "observation" should your instances align. Perhaps some of the most gregarious use of this is in the Haxl project at Facebook where the Applicative instance is more parallelized than the Monad instance, and thus is far more efficient at the cost of some fairly severe "unobserved" side effects.

In any case, if they differ, document it.

Answer 2

I often choose a reverse approach as compared to the one in Abrahamson's answer. I manually define only the Monad instance and define the Applicative and Functor in terms of it with the help of already defined functions in the Control.Monad, which renders those instances the same for absolutely any monad, i.e.:

instance Applicative SomeMonad where
  pure = return
  (<*>) = ap

instance Functore SomeMonad where
  fmap = liftM

While this way the definition of Functor and Applicative is always "brain-free" and very easy to reason about, I must note that this is not the ultimate solution, since there are cases, when the instances can be implemented more efficiently or even provide new features. E.g., the Applicative instance of Concurrently executes things ... concurrently, while the Monad instance can only execute them sequentially due to the nature of monads.

Answer 3

Functor instances are typically very simple to define, I'd normally do those by hand.

For Applicative and Monad, it depends. pure and return are usually similarly easy, and it really doesn't matter in which class you put the expanded definition. For bind, it is sometimes benfitial to go the "category way", i.e. define a specialised join' :: (M (M x)) -> M x first and then a>>=b = join' $ fmap b a (which of course wouldn't work if you had defined fmap in terms of >>=). Then it's probably useful to just re-use (>>=) for the Applicative instance.

Other times, the Applicative instance can be written quite easily or is more efficient than the generic Monad-derived implementation. In that case, you should definitely define <*> separately.

Answer 4

The magic here, that the Haskell uses the Kleisli-tiplet notation of a monad, that is more convenient way, if somebody wants to use monads in imperative programming like tools.

I asked the same question, and the answer come after a while, if you see the definitions of the Functor, Applicative, Monad in haskell you miss one link, which is the original definition of the monad, which contains only the join operation, that can be found on the HaskellWiki.

With this point of view you will see how haskell monads are built up functor, applicative functors, monads and Kliesli triplet.

A rough explanation can be found here: https://github.com/andorp/pearls/blob/master/Monad.hs And other with the same ideas here: http://people.inf.elte.hu/pgj/haskell2/jegyzet/08/Monad.hs

Answer 5

I think you mis-understand how sub-classes work in Haskell. They aren't like OO sub-classes! Instead, a sub-class constraint, like

class Applicative m => Monad m

says "any type with a canonical Monad structure must also have a canonical Applicative structure". There are two basic reasons why you would place a constraint like that:

• The sub-class structure induces a super-class structure.
• The super-class structure is a natural subset of the sub-class structure.

For example, consider:

class Vector v where
    (.^) :: Double -> v -> v
    (+^) :: v -> v -> v
    negateV :: v -> v

class Metric a where
    distance :: a -> a -> Double

class (Vector v, Metric v) => Norm v where
    norm :: v -> Double

The first super-class constraint on Norm arises because the concept of a normed space is really weak unless you also assume a vector space structure; the second arises because (given a vector space) a Norm induces a Metric, which you can prove by observing that

instance Metric V where
    distance v0 v1 = norm (v0 .^ negateV v1)

is a valid Metric instance for any V with a valid Vector instance and a valid norm function. We say that the norm induces a metric. See http://en.wikipedia.org/wiki/Normed_vector_space#Topological_structure .

The Functor and Applicative super-classes on Monad are like Metric, not like Vector: the return and >>= functions from Monad induce Functor and Applicative structures:

• fmap: can be defined as fmap f a = a >>= return . f, which was liftM in the Haskell 98 standard library.
• pure: is the same operation as return; the two names is a legacy from when Applicative wasn't a super-class of Monad.
• <*>: can be defined as af <*> ax = af >>= \ f -> ax >>= \ x -> return (f x), which was liftM2 ($) in the Haskell 98 standard library.
• join: can be defined as join aa = aa >>= id.

So it's perfectly sensible, mathematically, to define the Functor and Applicative operations in terms of Monad.