Use Monad to implement Applicative and Functor instances

Created: 2023-02-14 17:16

Since the hierarchy of Functors is defined as:

class Functor f where
  ...
 
class Functor f => Applicative f where
  ...
 
class Applicative f => Monad f where
  ...

The intuition I have (and others as well I guess) is that one can/should not use a function from a higher up in the hierarchy to implement instances lower in the hierarchy.

But this intuition is not correct, a more powerful construct can be used to implement a less powerful one, whereas that doesn’t work the other way around.

Take the Reader Monad as an example, we can implement all the instances by hand:

newtype Reader r a = Reader { runReader :: r -> a }
 
instance Functor (Reader r) where
  fmap :: (a -> b) -> Reader r a -> Reader r b
  fmap f (Reader g) = Reader $ f . g 
 
instance Applicative (Reader r) where
  pure :: a -> Reader r a
  pure x = Reader (\_ -> x)
 
  (<*>) :: Reader r (a -> b) -> Reader r a -> Reader r b
  f <*> x = Reader $
    \r -> let f' = (runReader f) r
              a' = (runReader x) r
           in f' a'
 
instance Monad (Reader r) where
  return = pure
  
  (>>=) :: Reader r a -> (a -> Reader r b) -> Reader r b
  x >>= f = Reader $ \r -> runReader (f (runReader x r)) r

Or we can rely on the Monad instance:

import Control.Monad
 
-- > liftM :: Monad m => (a -> b) -> m a -> m
-- > ap :: Monad m => m (a -> b) -> m a -> m b
 
newtype Reader r a = Reader { runReader :: r -> a }
 
instance Functor (Reader r) where
  fmap :: (a -> b) -> Reader r a -> Reader r b
  fmap = liftM
 
instance Applicative (Reader r) where
  pure :: a -> Reader r a
  pure x = Reader (\_ -> x)
 
  (<*>) :: Reader r (a -> b) -> Reader r a -> Reader r b
  (<*>) = ap
 
instance Monad (Reader r) where
  return = pure
  
  (>>=) :: Reader r a -> (a -> Reader r b) -> Reader r b
  x >>= f = Reader $ \r -> runReader (f (runReader x r)) r

It is important to note that if your type has a Monad instance, then whatever <*> does it must be equivalent to ap (ie. relaying on the Monad instance). It is not necessary to use ap, for example if there’s a more performant implementation, but the result should be the same.

This is more evident on the State Monad:

import Control.Monad
 
newtype State s a = State { runState :: s -> (a, s) }
 
instance Functor (State s) where
  fmap = liftM
 
instance Applicative (State s) where
  pure x  = State $ \s -> (x, s)
 
  f <*> x = ap
 
instance Monad (State s) where
  x >>= f = State $
    \s -> let (a, s') = runState x s
           in runState (f a) s'
 
get :: State s s
get = State $ \s -> (s, s)
 
put :: s -> State s ()
put s' = State $ \_ -> ((), s')

Here’s the implementation of ap:

ap :: (Monad m) => m (a -> b) -> m a -> m b
ap m1 m2 = do
  x1 <- m1
  x2 <- m2
  return $ x1 x2

So <*> would look like this:

f <*> x = do
  f' <- f
  x' <- x
  return $ f' x'

If we implement it by hand we have to produce the same result:

(<*>) :: State s (a -> b) -> State s a -> State s b
f <*> x = State $ 
\s -> let (f', s')  = runState f s
          (x', s'') = runState x s'
       in (f' x', s'')

Notice how we are keeping track of the changes in the state (s, s', s''), that is because each of the operations might change the state, so we cannot feed it an outdated version of it. That was not the case in the Reader since the context (r) never changes.

Here’s an example, we have a function that increments n values of a tree:

data Tree a = Leaf | Node a (Tree a) (Tree a)
 
incrementN :: Num a => Word -> Tree a -> Tree a
incrementN = \n t -> fst $ runState (go t) n
  where
    go :: Tree a -> State Word (Tree a)
    go Leaf = pure Leaf
    go t@(Node x l r) = do
        n <- get
        if n == 0 then
          pure t
        else do
          put (n - 1)
          Node (succ x) <$> go l <*> go r

In the last line, Node (succ x) <$> go l <*> go r, if <*> would not properly keep track of the state changes, the result would not be correct.