Why does 'for' from Data.Traversable accept monadic actions?

Question

I was working on the following small fragment of code:

import           Control.Monad
import           Data.Aeson
import qualified Data.HashMap.Strict as HashMap
import           Data.Map (Map)
import qualified Data.Map as Map
import           GHC.Generics

-- definitions of Whitelisted, WhitelistComment and their FromJSON instances
-- omitted for brevity

data Whitelist = Whitelist
  { whitelist :: Map Whitelisted WhitelistComment
  } deriving (Eq, Ord, Show)

instance FromJSON Whitelist where
  parseJSON (Object v) =
    fmap (Whitelist . Map.fromList) . forM (HashMap.toList v) $ \(a, b) -> do
      a' <- parseJSON (String a)
      b' <- parseJSON b
      return (a', b')
  parseJSON _ = mzero

when I realised that I can rewrite the do block in applicative style:

instance FromJSON Whitelist where
  parseJSON (Object v) =
    fmap (Whitelist . Map.fromList) . forM (HashMap.toList v) $ \(a, b) ->
      (,) <$> parseJSON (String a) <*> parseJSON b
  parseJSON _ = mzero

and with that I could also replace forM with for. Before making the change above I switched to for first:

instance FromJSON Whitelist where
  parseJSON (Object v) =
    fmap (Whitelist . Map.fromList) . for (HashMap.toList v) $ \(a, b) -> do
      a' <- parseJSON (String a)
      b' <- parseJSON b
      return (a', b')
  parseJSON _ = mzero

and to my surprise this still compiled. Given the definition of for:

for :: (Traversable t, Applicative f) => t a -> (a -> f b) -> f (t b)

I thought the Applicative constraint would prevent me from using do notation / return in the action passed to for.

I'm clearly missing something fundamental here, either in terms of what for signature really implies, or how the code I posted is interpreted by the compiler, and would appreciate any help understanding what's going on.

Answer 1

This is just the usual caller-vs-implementer duality going on, where one side gets flexibility and the other restriction.

for provides you with this interface:

for :: (Traversable t, Applicative f) => t a -> (a -> f b) -> f (t b)

You as the caller get the flexibility to choose any type f to instantiate it, so you can use it as if it were:

for :: Traversable t => t a -> (a -> Parser b) -> Parser (t b)

Clearly once you've done that, there's no reason you couldn't use any Parser-specific functionality in the function you pass to for, including Monad stuff.

The implementer of for on the other hand gets restricted by the polymorphism in the interface of for. They have to work with any choice of f, so they can only use the Applicative interface in the code they write to implement for. But that only restricts the code of for itself, not the function passed into it.

If the author of for wanted to restrict what the caller could do in that function, they could have used RankNTypes to instead provide this interface:

for :: forall t f. (Traversable t, Applicative f) => t a -> (forall g. Applicative g => a -> g b) -> f (t b)

Now the provided lambda itself must be polymorphic in g (subject to an Applicative constraint). The caller of for still gets the flexibility to choose f, with the implementer being restricted in using only Applicative features. But the caller of for is the implementer of the function argument, so now that that function is polymorphic itself the caller of for is restricted to using only Applicative features there and the implementer of for gets the freedom to use it with any type they like (including possibly using monad features to combine it with other internal values). With this specific type signature the implementer of for will have to choose to instantiate g with the same type the caller of for selected for f, in order to come up with the final f (t b) return value. But the caller of for would still be restricted by the type system to providing a function that works for any Applicative g.

The point is, if you get to choose what type to instantiate a polymorphic signature with then you are not the one restricted by that interface. You can choose a type and then use whatever other features of that type you like, provided you still do provide the bits of information the interface requires of you. i.e. You can use non-Traversable functionality to create your t a and non-Applicative functionality to create your a -> f b, all that's required is that you do provide those inputs. And indeed you almost have to make use of functionality specific to a and b. The implementer of the polymorphic signature doesn't get that freedom, they are restricted by the polymorphism to only doing things that would work for any possible choice.

As an aside, similarly to how rank 2 types add "another level" of this duality with the roles reversed (and rank N types allow arbitrarily many levels), a similar duality is also seen (flipped around again) in the constraints themselves. Consider again the signature:

for :: (Traversable t, Applicative f) => t a -> (a -> f b) -> f (t b)

The caller of for is restricted by the Traversable and Applicative constraints when choosing the types t and f. The implementer gets the freedom to use any functions implied by those constraints, without worrying about how to prove the constraints are satisfied.

Answer 2

The first short answer is that Parser has an Applicative instance. The snippet

do
  a' <- parseJSON a
  b' <- parseJSON b
  return (a', b')

has the type Parser (Whitelisted, WhitelistComment) which unifies with f b in the type signature

for :: (Traversable t, Applicative f) => t a -> (a -> f b) -> f (t b)

Since there's an Applicative Parser instance, it also satisfies that constraint. (I think I got the types for a' and b' right)

---

The second short answer is that a Monad is strictly more powerful than an Applicative, anywhere you need an Applicative you can use a Monad instead. Ever since the Monad-Applicative proposal was implemented, every Monad is also Applicative. The Monad class now looks like

class Applicative m => Monad m where 
    ...

A Monad is strictly more powerful than an Applicative, anywhere you need an Applicative you can use a Monad instead with the following substitutions:

• ap instead of <*>
• return instead of pure
• liftM instead of fmap

If you're writing some new type, SomeMonad, and have provided an instance for the Monad class you can use it to provide the instances for Applicative and Functor too.

import Control.Monad

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

instance Functor SomeMonad where
    fmap = liftM