Instances of transformers not needing the Monad constraint?

[turion]

Is there for example an instance:

instance Selective f => Selective (ReaderT r f a)

[snowleopard]

@turion Interesting question! Here is an instrance for ReaderT:

instance Selective f => Selective (ReaderT env f) where
    select (ReaderT x) (ReaderT f) = ReaderT $ \env -> select (x env) (f env)

I guess this should trivially satisfy the laws since accessing the environment env is not an observable effect.

I wonder if we can prove that the behaviour we get must coincide with that of the existing instance with the Monad constraint. If yes, then we should export the above instance, since it's more general.

[turion]

Assuming that select = selectM for f, we have:

ReaderT $ \env -> select (x env) (f env)
= ReaderT $ \env -> selectM (x env) (f env)
= ReaderT $ \env -> x env >>= \e -> case e of
    Left  a -> ($a) <$> f env
    Right b -> pure b
= ReaderT $ \env -> do
    e <- x env
    case e of
      Left  a -> ($a) <$> f env
      Right b -> pure b

On the other hand, consider >>= for ReaderT (https://hackage.haskell.org/package/transformers-0.5.2.0/docs/src/Control.Monad.Trans.Reader.html#line-148), which is:

ReaderT m >>= k = ReaderT $ \env -> do
  e <- m env
  runReaderT (k e) env

Then selectM for ReaderT r f expands as follows:

selectM (ReaderT x) (ReaderT f)
-- definition of selectM
= (ReaderT x) >>= \e -> case e of
    Left  a -> ($a) <$> (ReaderT f)
    Right b -> pure b
-- definition of >>=
= ReaderT $ \env -> do
    e <- x env
    runReaderT (case e of
      Left  a -> ($a) <$> (ReaderT f)
      Right b -> pure b
    ) env
-- evaluate runReaderT in both branches
= ReaderT $ \env -> do
    e <- x env
    case e of
      Left  a -> runReaderT (($a) <$> (ReaderT f)) env
      Right b -> runReaderT (pure b) env

Then by looking up the definitions of fmap and pure for ReaderT one arrives at the other implementation.

I'm pretty sure you can prove something like that for other transformers as well.

[turion]

Here is an interesting observation related to this:

The signature for the Applicative instance of ExceptT is (https://hackage.haskell.org/package/transformers-0.5.6.2/docs/Control-Monad-Trans-Except.html#t:ExceptT):

(Functor m, Monad m) => Applicative (ExceptT e m)

One would think that (Applicative m) => Applicative (ExceptT e m) should be sufficient. But it isn't. When ap-ing ExceptT f <*> ExceptT a, one needs to inspect in which branch of m (Either e a) f is! So one needs exactly Selective to make ExceptT an Applicative!

To me this sounds like there should be yet another Either-related transformer newtype EitherT m e a = EitherT { runEitherT :: m (Either e a) } which has the following instance:

instance Selective m => Applicative (EitherT m e) where
...

This is not the same as ComposeEither, because that executes all effects. This new variant here does not execute the effect of a in f <*> a when f throws an error.

Semantically this is the same as the transformers implementation: https://hackage.haskell.org/package/transformers-0.5.6.2/docs/src/Control.Monad.Trans.Except.html#line-186

I stumbled upon this because I wanted to implement instance Selective m => Selective (ExceptT e m). But this is not possible because Applicative (ExceptT e m) needs Monad m, because when transformers was written they didn't know about Selective. But for this new EitherT we can implement such an instance.

[snowleopard]

@turion Your proof sketch looks convincing. I've added more general instances for IdentityT and ReaderT in #38.

Here is an interesting observation related to this [...]

Oh, wow, that's so cool! It's a shame we can't have a meaningful instance Selective m => Selective (ExceptT e m) because the applicative instance currently requires a monad. I don't mind adding a new module Control.Selective.EitherT which declares all the instances as you described. Would you like to do it? Happy to review!

[turion]

Here is an interesting observation related to this [...]

Oh, wow, that's so cool! It's a shame we can't have a meaningful instance Selective m => Selective (ExceptT e m) because the applicative instance currently requires a monad. I don't mind adding a new module Control.Selective.EitherT which declares all the instances as you described. Would you like to do it? Happy to review!

Yes, I'll give it a try.

[turion]

StateT can't work fundamentally, thus RWST neither. It remains to be seen whether ContT works, but I'm pessimistic ;)

[turion]

It remains to be seen whether ContT works, but I'm pessimistic ;)

ContT has no contraints at all, so there is nothing to do there.

The only transformers for which it works then are WriterT, ExceptT and MaybeT.

AccumT doesn't work for the same reason as StateT: If you have something of type s -> m x, you can't make an m (s -> x) from it for a general selective m. (Otherwise Selective was the same as Monad I think.) But you need it to pass the previously computed state to the later continuation. Maybe something can be done with Control.Selective.Multi and an extra constraint on the state type, but then the instances don't form a hierarchy anymore, since the Monad (StateT s m) instance doesn't need that extra constraint on the state type.

[snowleopard]

@turion I agree with your analysis: state-passing seems monadic in nature.

I wonder if switching from s -> f (a, s) to f (s -> (a, s)) gives you anything useful. Probably not?

[turion]

I wonder if switching from s -> f (a, s) to f (s -> (a, s)) gives you anything useful. Probably not?

This is a transformer as far as I know, but it's strictly less expressive than StateT. For example, I believe that you can't even write the following program:

main = flip evalStateT 23 $ do
  n <- get
  lift $ print n