Composing Applicatives

Question

I'm reading through Chapter 25 (Composing Types) of the haskellbook, and wish to understand applicative composition more completely

The author provides a type to embody type composition:

newtype Compose f g a =
  Compose { getCompose :: f (g a) }
  deriving (Eq, Show)

and supplies the functor instance for this type:

instance (Functor f, Functor g) =>
  Functor (Compose f g) where
    fmap f (Compose fga) =
      Compose $ (fmap . fmap) f fga

But the Applicative instance is left as an exercise to the reader:

instance (Applicative f, Applicative g) =>
  Applicative (Compose f g) where
    -- pure :: a -> Compose f g a
    pure = Compose . pure . pure
    -- (<*>) :: Compose f g (a -> b)
    --       -> Compose f g a
    --       -> Compose f g b
    Compose fgf <*> Compose fgx = undefined

I can cheat and look the answer up online... The source for Data.Functor.Compose provides the applicative instance definition:

Compose f <*> Compose x = Compose ((<*>) <$> f <*> x)

but I'm having trouble understanding what's going on here. According to type signatures, both f and x are wrapped up in two layers of applicative structure. The road block I seem to be hitting though is understanding what's going on with this bit: (<*>) <$> f. I will probably have follow up questions, but they probably depend on how that expression is evaluated. Is it saying "fmap <*> over f" or "apply <$> to f"?

Please help to arrive at an intuitive understanding of what's happening here.

Thanks! :)

Answer 1

Consider the expression a <$> b <*> c. It means take the function a, and map it over the functor b, which will yield a new functor, and then map that new functor over the functor c.

First, imagine that a is (\x y -> x + y), b is Just 3, and c is Just 5. a <$> b then evaluates to Just (\y -> 3 + y), and a <$> b <*> c then evaluates to Just 8.

(If what's before here doesn't make sense, then you should try to understand single layers of applicatives further before you try to understand multiple layers of them.)

Similarly, in your case, a is (<*>), b is f, and c is x. If you were to choose suitable values for f and x, you'd see that they can be easily evaluated as well (though be sure to keep your layers distinct; the (<*>) in your case belongs to the inner Applicative, whereas the <$> and <*> belong to the outer one).

Answer 2

Rather than <*>, you can define liftA2.

import Control.Applicative (Applicative (..))

newtype Compose f g a = Compose
  { getCompose :: f (g a) }
  deriving Functor

instance (Applicative f, Applicative g) => Applicative (Compose f g) where
  pure a = Compose (pure (pure a))
  -- liftA2 :: (a -> b -> c) -> Compose f g a -> Compose f g b -> Compose f g c
  liftA2 f (Compose fga) (Compose fgb) = Compose _1

We have fga :: f (g a) and fgb :: f (g b) and we need _1 :: f (g c). Since f is applicative, we can combine those two values using liftA2:

  liftA2 f (Compose fga) (Compose fgb) = Compose (liftA2 _2 fga fgb)

Now we need

_2 :: g a -> g b -> g c

Since g is also applicative, we can use its liftA2 as well:

  liftA2 f (Compose fga) (Compose fgb) = Compose (liftA2 (liftA2 f) fga fgb)

This pattern of lifting liftA2 applications is useful for other things too. Generally speaking,

liftA2 . liftA2 :: (Applicative f, Applicative g) => (a -> b -> c) -> f (g a) -> f (g b) -> f (g c)

liftA2 . liftA2 . liftA2
  :: (Applicative f, Applicative g, Applicative h)
  => (a -> b -> c) -> f (g (h a)) -> f (g (h b)) -> f (g (h c))