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 monads.