Add `((->) r')` as a base monad for `SelectT`.

[jumper149]

trafficstars

Identity is the obvious choice, but we can pass arguments below SelectT.

We should be able to even use arbitrary ReaderT stacks below SelectT.

---

I'm not sure if there is a good way to generalize these instances. I tried to use MonadBaseControlIdentity from https://hackage.haskell.org/package/monad-control-identity-0.2.0.0/docs/Control-Monad-Trans-Control-Identity.html#t:MonadBaseControlIdentity, but this leads to duplicate instances. And the only way to resolve these, was by adding newtype wrappers (atleast I think so).

type WithBaseMonadT :: (Type -> Type) -> (Type -> Type) -> Type -> Type
newtype WithBaseMonadT b m a = MkWithBaseMonadT {unWithBaseMonadT :: m a}
  deriving newtype (Functor, Applicative, Monad)

instance MonadBaseControlIdentity Identity m => MonadSelect r (WithBaseMonadT Identity (T.SelectT r m)) where
  select f = MkWithBaseMonadT $ T.SelectT $ \ k -> liftBaseWithIdentity $ \runInIdentity ->
    Identity $ f $ runIdentity . runInIdentity . k

instance MonadBaseControlIdentity ((->) r2) m => MonadSelect r (WithBaseMonadT ((->) r2) (T.SelectT r m)) where
  select f = MkWithBaseMonadT $ T.SelectT $ \ k -> liftBaseWithIdentity $ \ runInIdentity ->
    \ r2 -> f $ \ma -> runInIdentity (k ma) r2

[jumper149]

I just noticed, that the same sort of thing will work for AccumT probably.

Edit: I don't understand why the MonadAccum instance for AccumT also uses Identity as a base monad. I think it should be fine with any monad, right?

[emilypi]

Edit: I don't understand why the MonadAccum instance for AccumT also uses Identity as a base monad. I think it should be fine with any monad, right?

Not unless you want to overlap on the monoid instance. Every Monad may admit any number of accumulating monoids, so the general instance is not supplied. This is a case where we ask not "can we?" but "should we?".

[emilypi]

This case might actually be okay tho. @kozross thoughts?

[kozross]

I'd be OK with a -> r instance in principle.

[jumper149]

I initially dumped all my thoughts into this PR, but let's make sure we are talking about the same things.

---

Edit: I don't understand why the MonadAccum instance for AccumT also uses Identity as a base monad. I think it should be fine with any monad, right?

Not unless you want to overlap on the monoid instance. Every Monad may admit any number of accumulating monoids, so the general instance is not supplied. This is a case where we ask not "can we?" but "should we?".

This discussion should move to #141.

---

This case might actually be okay tho. @kozross thoughts?

Referring to:

instance MonadSelect r (SelectT r ((->) r')) where
  select f = SelectT $ \k r' -> f $ \a -> k a r'

---

I'd be OK with a -> r instance in principle.

Also referring to:

instance MonadSelect r (SelectT r ((->) r')) where
  select f = SelectT $ \k r' -> f $ \a -> k a r'

---

On another note, I'll fix the CI quickly. I was programming blind without compiling offline :safety_vest:

[Lysxia]

@kozross What is the origin of the MonadSelect class? It looks quite odd compared to other MonadX classes in mtl that all have an instance of the form Monad m => MonadX (XT m).

[jumper149]

@Lysxia I agree, it does look odd. I played around with it for a bit just now and tried to generalize that instance. This is the best I could come up with.

{-# OPTIONS_GHC -fno-warn-orphans #-}

module Control.Monad.Select.OrphanInstances where

import Control.Monad.Select
import Control.Monad.Turn
import qualified Control.Monad.Trans.Select as T

instance MonadTurn m => MonadSelect r (T.SelectT r m) where
  select f = T.SelectT $ \ k -> returnWith $ \turn -> f $ turn . k

turn is the inverse of return here.

---

Here is the other boilerplate code. It depends on monad-control-identity to match ReaderT-stacks of any depth.

If you were to use BaseMonadTurn instead MonadTurn you would miss out on stuff like SelectT r (ReaderT r' Identity)

{-# LANGUAGE UndecidableInstances #-}

module Control.Monad.Turn where

import Control.Monad.Trans.Control.Identity
import Data.Functor.Identity

class Monad m => BaseMonadTurn m where
  returnBaseWith :: ((forall x. m x -> x) -> a) -> m a

instance BaseMonadTurn Identity where
  returnBaseWith f = Identity $ f runIdentity

instance BaseMonadTurn ((->) r) where
  returnBaseWith f r = f ($ r)

class Monad m => MonadTurn m where
  returnWith :: ((forall x. m x -> x) -> a) -> m a

-- TODO: Remove `Monad m` constraint. Found a GHC bug. :/
instance (BaseMonadTurn b, MonadBaseControlIdentity b m, Monad m) => MonadTurn m where
  returnWith f =
    liftBaseWithIdentity $ \ runInBase ->
      returnBaseWith $ \ turn ->
        f $ turn . runInBase

instance (MonadTurn m, MonadTransControlIdentity t) => MonadTurn (t m) where
  returnWith f =
    liftWithIdentity $ \ runT ->
      returnWith $ \ turn ->
        f $ turn . runT

---

If you want to try it out:

• Instance
• Boilerplate

---

Overall I'm not sure if I would even call this a monad transformer, since it only works for a subclass of monads.

[Lysxia]

I think we agree that something odd is going on with that class, but "not a monad transformer" isn't quite the right way to put it.

Strictly speaking, a monad transformer is just something that implements MonadTrans (lawfully of course). SelectT fits the bill.

It's difficult to pinpoint the root of the issue because there is no established criterion for what makes a class suitable for inclusion in mtl. Nevertheless, I think the problem is more that MonadSelect doesn't capture the functionality of SelectT as "faithfully" as other mtl classes do for their respective transformers. Without side effects in the argument of the select method, it seems impossible to implement the examples from the very paper that introduced SelectT: Monad transformers for backtracking search.

It would be helpful to know of some uses for MonadSelect.

[jumper149]

Seems like you are right. SelectT is just like in the paper.

In the example they even use SelT Outcome [] Move, which would not work with MonadSelect as it is currently.

The select function from transformers is also constrained to Select (not SelectT!).

Maybe we need:

select :: ((a -> m r) -> m a) -> m a 

Or something similar. I guess I have to gain a better understanding of the paper.

[kozross]

MonadSelect was my attempt at generalizing the functionality of SelectT. I admit that I probably didn't understand it very well: transformers basically links two papers instead of writing documentation, neither of which is very practitioner-oriented.

I don't mind either getting rid of it, or reworking it to better suit its intended purpose, but it'd have to be by someone who understands it better than I do.

[Lysxia]

Practically, it may be wiser to just not touch MonadSelect, to avoid a breaking change, until either a concrete (even toy) use case or a more convincing replacement comes up.

At the moment, MonadSelect r is basically equivalent to MonadBase (Select r) (if Select wasn't defined with a transformer). This PR generalizes MonadSelect somewhat beyond MonadBase (Select r) but there isn't an obvious motivation for it.