Why is it permissible to use `ap` on a function that takes two monad values as opposed to a function wrapped in the monad?

Question

Here's the haskell code:

zipWith compare `ap` tail

where

zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
compare :: a -> a -> Ordering 
ap :: Monad m => m (a -> b) -> m a -> m b

So from what I understand ap in this case will need a function wrapped inside the list monad, that is it needs m (a -> b), which is supposedly fulfilled by zipWith compare but I don't see how, because zipWith compare will take on type [a] -> [a] -> [Ordering] which is not quite correct. Is there something happening behind the scenes of the list monad that causes the necessary type conversion?

The code works and is not my own work, I'm just trying to understand how it's permissible.

Answer 1

The trick here is that a -> is a Monad!

In fact, we can list out the instances of Monad in a plain ghci session:

ghci> :i Monad
type Monad :: (* -> *) -> Constraint
class Applicative m => Monad m where
  (>>=) :: m a -> (a -> m b) -> m b
  (>>) :: m a -> m b -> m b
  return :: a -> m a
  {-# MINIMAL (>>=) #-}
    -- Defined in ‘GHC.Base’
instance Monoid a => Monad ((,) a) -- Defined in ‘GHC.Base’
instance (Monoid a, Monoid b) => Monad ((,,) a b)
  -- Defined in ‘GHC.Base’
instance (Monoid a, Monoid b, Monoid c) => Monad ((,,,) a b c)
  -- Defined in ‘GHC.Base’
instance Monad ((->) r) -- Defined in ‘GHC.Base’ <- This is the one!
instance Monad IO -- Defined in ‘GHC.Base’
instance Monad Maybe -- Defined in ‘GHC.Base’
instance Monad Solo -- Defined in ‘GHC.Base’
instance Monad [] -- Defined in ‘GHC.Base’
instance Monad (Either e) -- Defined in ‘Data.Either’

Therefore, zipWith compare :: m ([a] -> Ordering) and tail :: m [a] where m is ((->) [a]), or ([a] ->).

The trick here is that the function arrow, ->, is indeed a type constructor that builds new types. Once getting around this, you can take a look at the actual implementation of its Monad instance (and it's nothing out of expectation there).

In fact, for ap (I haven't double-checked but I'm pretty confident), it looks like this:

ap :: (r -> (a -> b)) -- this is m (a -> b)
   -> (r -> a)        -- this is m a
   -> (r -> b)        -- this is m b
ap rab ra
  = \r ->             -- the result must be a function starting from r
      (rab r)         -- gives (a -> b)
      (ra r)          -- gives a, thus the body of the lambda gives b

This is also the S-combinator in SKI.

Answer 2

but I don't see how, because zipWith compare will take on type [a] -> [a] -> [Ordering] which is not quite correct.

No, the type has the correct form. It is not obvious at first, but the type indeed matches m (t -> u) so one can use ap here.

To understand why, we need to recall that A -> B is syntactic sugar for (->) A B. This is the type constructor (->) applied to A, then applied again to B. We can also write that as ((->) A) B.

So, let's match the types:

  [a] -> [a] -> [Ordering]
= (->) [a] ([a] -> [Ordering])
= ((->) [a]) ([a] -> [Ordering])
  ---------m  --t    ---------u

So we can take m = (->) [a], t = [a], and u = [Ordering] to satisfy the requirements for passing that to ap.

ap :: Monad m => m (t -> u) -> m t -> m u

Finally, note that m = (->) [a] is indeed a monad. It's essentially the same monad as the Reader [a] monad, only without the newtype wrapper.