Unable to use monadic bind on an argument that is a monad

Question

The context is an exercise from the fp-course available on github; in StateT.hs:

data OptionalT f a =
  OptionalT {
    runOptionalT ::
      f (Optional a)
  } --local version the course declares of Haskell's Maybe

-- My interpretation of this line is that if f is a monad, then (OptionalT f) is an Applicative
instance Monad f => Applicative (OptionalT f) where
  pure a = OptionalT $ return $ Full a
  (<*>) (OptionalT fOpG) (OptionalT fOpA) = do
                        opG <- fOpG --so this is the specific thing throwing an error at me. They say they expect OptionalT f (Optional (a -> b))
                                    --but i'm providing them with a f (Optional (a -> b))
                        opA <- fOpA
                        ...

The error thrown at me is that Haskell couldn't match type 'f' with type 'OptionalT f' in the statement opG <- fOpG and i'm not sure why this doesn't typecheck. My understanding is that OptionalT contains a f (Optional a) where f is a monad, so i expect:

fOpG :: f (Optional a -> b) so using a monadic bind here should be valid? I've tried rewriting the expression using (>>=) notation instead of do notation and I run into the same error.

EDIT: I've managed to figure out how to fix the code above and the reason it breaks as follows, if i translate the do block to a chain of (>>=), and list a few important type signatures of variables:

fOpG >>= (\opG -> fopA >>= (\opA -> ...))
(>>=) :: Monad f => f a -> (a -> f b) -> f b
fOpG :: f (Optional a)

The issue is that the type signature of (>>=) expects a monad of type b as the final return result. So in my outermost use of it, with fOpG on the left, it expects the function on its right to produce a value of type f (Optional b), but my entire do block was wrongly returning something of type OptionalT f (Optional b). The fix was to do the re-wrapping outside, as suggested in the comments by Luqui. For reference, the wrong and fixed solutions were:

--Broken solution due to wrong location of OptionalT wrapper
instance Monad f => Applicative (OptionalT f) where
  pure a = OptionalT $ return $ Full a
  (<*>) (OptionalT fOpG) (OptionalT fOpA) = do
                                              opG <- fOpG 
                                              opA <- fOpA
                                              case opG of Empty  -> OptionalT $ return Empty
                                                          Full g -> OptionalT $ onFull (\t -> return (Full (g t))) opA


-- Fixed solution with wrapper outside
instance Monad f => Applicative (OptionalT f) where
  pure a = OptionalT $ return $ Full a
  (<*>) (OptionalT fOpG) (OptionalT fOpA) = OptionalT $ do
                                              opG <- fOpG 
                                              opA <- fOpA
                                              case opG of Empty  -> return Empty
                                                          Full g -> onFull (\t -> return (Full (g t))) opA

However I still don't understand why Haskell allows the following to go through:

(<*>) fOpG fOpA = do
                opG <- fOpG 
                opA <- fOpA
                OptionalT (return Empty) --just a dummy line to `enter code here`let me see if it typechecks

It is not clear to me why doing (opG <- fOpG) is valid. fOpG :: Optional T f (a -> b) is only an instance of functor at this point, and not yet an instance of applicative or monad, so I don't understand why I am able to use a monadic bind on it. Could someone provide some insight on what is actually happening here?

(I am under the impression that do notation is just syntactic sugar for chaining the (>>=) operator, i'm not sure if there are other subtleties or if in specific contexts this is not the case.)

Answer 1

Once you finished the exercise you can derive via MaybeT f (using Maybe in place of Option)

{-# Language DerivingVia              #-}
{-# Language StandaloneKindSignatures #-}

import Control.Applicative (Alternative)
import Control.Monad (MonadPlus)
import Control.Monad.Fix (MonadFix)
import Control.Monad.Reader (MonadReader)
import Control.Monad.State (MonadState)
import Control.Monad.Trans.Maybe
import Control.Monad.Zip (MonadZip)
import Data.Kind (Type)

type    OptionalT :: (Type -> Type) -> (Type -> Type)
newtype OptionalT f a = OptionalT { runOptionalT :: f (Maybe a) }
 deriving (Functor, Foldable, Applicative, Alternative, Monad, MonadPlus, MonadFail, MonadFix, MonadZip, MonadReader r, MonadState s)
 via MaybeT f

Answer 2

The edit above answers the initial problem, and Carl provided the remaining explanation in a comment: even though the instance of monad was incomplete and undefined, it had already been declared hence Haskell allowing the use of bind to go through.

Just putting an answer here so I can close the problem rather then leaving it open.

EDIT: For completeness, just thought to add a final edit that the solution above is still bugged, it compiles but is not a proper implementation of the applicative instance for Optional.

  (<*>) (OptionalT fOpG) (OptionalT fOpA) = OptionalT $ do
                                              opG <- fOpG 
                                              opA <- fOpA
                                              case opG of Empty  -> return Empty
                                                          Full g -> onFull (\t -> return (Full (g t))) opA

The problem here is that i sequentially pull opG and opA out, before checking first if opG is Empty. This results in problem with lists. Instead, opA should only be pulled after the checks on opG.

  (<*>) (OptionalT fOpG) (OptionalT fOpA) = OptionalT $ 
                                              fOpG >>= (\opG -> case opG of Empty  -> return Empty
                                                                            Full g -> fOpA >>= (\opA -> onFull (\t -> return (Full (g t))) opA))