Adding a proper ListT to transformers and this package

[sofia-m-a]

I think we should add a type equivalent to the following to transformers (and mtl):

newtype ChoiceT m a = ChoiceT { runChoiceT :: m (Maybe (ChoiceT m a)) }

This is a monad transformer, while it's well-known that the existing ListT is not.

And perhaps we should add the relevant MonadChoice class here (subject to design discussion)

Ideally this would happen in cooperation between the two libraries, hence why I'm opening it here. We would at least need all the instances to lift MonadX through ChoiceT

Bikeshedding name suggestions: ChoiceT, StreamT, NonDetT, ...

[turion]

It should be called ListT, since the name is already well-established in other libraries that implement it, such as pipes and list-t.

[kozross]

I would be happy to add this, but it raises an interesting problem. ListT generally has two meanings:

• 'I am a monadic stream'; and
• 'I am non-determinism of some flavour'.

With regard to the first of these, I actually don't know what kind of laws it could have; with regard to the second, this is basically MonadLogic from logict. If we want it to mean the former, we have to come up with some semantics; if it's the latter, it amounts to 'ownership' of logict by us.

Furthermore, mtl doesn't generally contain concrete transformers: merely the 'effect type classes' with instances for such. If anything, we'd need ListT to be added or fixed in transformers first.

FWIW, my take is that the second interpretation is the more correct one. While I do think MonadLogic absolutely has a place here, LogicT must land in transformers first for this to be reasonable IMHO.

@emilypi - thoughts?

[AshleyYakeley]

1. It would be somewhat odd for transformers to add the new transformer with the same name as the old ListT that was removed.
2. I think the definition is wrong, it should be: newtype ChoiceT m a = ChoiceT { runChoiceT :: m (Maybe (a, ChoiceT m a)) }

[AshleyYakeley]

3. Not sure if this is useful, but I think it can be decomposed:

   newtype StreamT m a = StreamT (m (a, StreamT m a))
   type ChoiceT m = StreamT (MaybeT m)

[noughtmare]

It might be good to consider prior art:

• Monadic stream functions from dunai

  data MSF m a b = MSF { unMSF :: a -> m (b, MSF m a b) }

  This is an arrow, but the monadic form would be the StreamT that @AshleyYakeley suggests.

• Monadic streams used by vector for stream fusion

  data Step s a where
  Yield :: a -> s -> Step s a
  Skip  :: s -> Step s a
  Done  :: Step s a
  
  data Stream m a = forall s. Stream (s -> m (Step s a)) s

  This is a corecursive form that presumably fuses better.

[AshleyYakeley]

For what it's worth, MSF can be decomposed (though you'd need a wrapper to make it an Arrow):

newtype StreamT m a = StreamT (m (a, StreamT m a))
type MSF m a = StreamT (ReaderT a m)

[Kleidukos]

If you want to ping Ross on the transformers ticket tracker: https://hub.darcs.net/ross/transformers/issue/88

[turion]

3. Not sure if this is useful, but I think it can be decomposed:

newtype StreamT m a = StreamT (m (a, StreamT m a))
type ChoiceT m = StreamT (MaybeT m)

The issue is that there is no Monad m => Monad (StreamT m), at least not in such a way that it gives rise to the Monad m => Monad (ChoiceT m) you'd expect.

[AshleyYakeley]

Hmm, you're right that StreamT would not be a monad transformer. However, I think you could do MonadPlus m => Monad (StreamT m). And you already have Monad m => MonadPlus (MaybeT m), so that gives you Monad m => Monad (ChoiceT m).

[turion]

I'd be surprised if that can be done in a way such that it gives you the instance you expect. At some point, you need to "concatenate" the lists, and I don't see how that would work out.

I think you could do MonadPlus m => Monad (StreamT m)

How so?

[AshleyYakeley]

Maybe this? This is just a guess and I haven't really analyzed it properly.

newtype StreamT m a = MkStreamT {runStreamT :: m (a, StreamT m a)}

join :: MonadPlus m => StreamT m (StreamT m a) -> StreamT m a
join (MkStreamT ssa) = MkStreamT $ do
    (MkStreamT sa,ssa') <- ssa
    (a,sa') <- sa
    return (a, mplus sa' $ join ssa')

instance MonadPlus m => Monad (StreamT m) where
    return a = MkStreamT $ return (a, mzero)
    p >>= q = join $ fmap q p

instance MonadPlus m => MonadPlus (StreamT m) where
    mzero = MkStreamT mzero
    mplus (MkStreamT pa) qa = MkStreamT $ do
        mpa <- mplus (fmap Just pa) $ return Nothing
        case mpa of
            Just (a,pa') -> return (a,mplus pa' qa)
            Nothing -> runStreamT qa

[turion]

I don't think join does what you want it to do. Looking at https://hackage.haskell.org/package/transformers-0.6.0.4/docs/src/Control.Monad.Trans.Maybe.html#line-197, I understand the behaviour of mplus in the case of MaybeT to be "if the first value succeeds, only take the first value, otherwise try the second. So if your sa' has a value, ssa' will be dropped completely.

[AshleyYakeley]

I don't think so. mplus sa' $ join ssa' uses the instance for MonadPlus (StreamT m) I also provided, which concatenates the two lists.

[AshleyYakeley]

So I believe it works.

The problem is that type ChoiceT m = StreamT (MaybeT m) means you obviously can't have MonadTrans ChoiceT without a newtype wrapper, which may not be worth it.

[AshleyYakeley]

On the plus side, StreamT Maybe is equivalent to lists, StreamT Identity is equivalent to infinite streams (not a monad of course), and StreamT [] is equivalent to trees, if for some reason you want this kind of polymorphism.

[turion]

So I believe it works.

I agree as well now :) thanks for your explanation!

The problem is that type ChoiceT m = StreamT (MaybeT m) means you obviously can't have MonadTrans ChoiceT without a newtype wrapper, which may not be worth it.

Yes, since MonadTrans t has Monad m => Monad (t m) as a prerequisite nowadays. It is still an applicative transformer, but there is no commonly used type class for that.

I think a newtype wrapper would be good, because you could then write:

newtype ChoiceT t m a = ChoiceT { unChoiceT :: StreamT (t m) a }

instance (Monad m => MonadPlus (t m)) => MonadTrans (ChoiceT t)

instance MonadPlus (t m) => Monad (ChoiceT t m)

That way you get all the instances you want without having to specialise to MaybeT. (Didn't test this though.)

Maybe we can turn this conversation closer to mtl again :sweat_smile: Do you think that StreamT works well with all the mtl classes? I.e. MonadState m => MonadState (StreamT m)? Again we have the issue that this would require Monad (StreamT m), so maybe we really need the ChoiceT t m a construction.

Also, is adding a further dependency to mtl ok?

[AshleyYakeley]

Note that you do have Monad m => MonadPlus (MaybeT m), so you can actually derive Monad m => Monad (ChoiceT m) and therefore MonadTrans ChoiceT (using a simple newtype wrapper).

[turion]

Yes, and the motivation behind the ChoiceT t m a construction is to allow this step for all transformers that have such an instance. So one doesn't have to make a newtype for each of them. Ok, the only other example I know is ExceptT e. I don't know whether that is sufficient repetition to eliminate it.

[AshleyYakeley]

OK, that makes sense.

I have no idea whether this StreamT thing is actually a good idea. The main problem is StreamT isn't a monad transformer, so it just might not fit in well with the rest of mtl. There might be more justification if there were a use-case for some other transformer besides MaybeT. ExceptT e will give you a list with an e on the end, not sure if that's useful...

[turion]

ExceptT e will give you a list with an e on the end, not sure if that's useful...

Yes I think it is. It's like a "return code" for the stream execution. Most streaming libraries have something like this, because drum roll it makes the stream also a monad in e!

[AshleyYakeley]

So in that case, one possibility is this:

newtype ChoiceT e m a = ChoiceT { runChoiceT :: m (Either e (a, ChoiceT e m a)) }
type ListT = ChoiceT ()

[AshleyYakeley]

This ChoiceT when considered as a monad in e is very similar to StepT in my monadology package. The only use I have for it is coroutines, though.

[turion]

So in that case, one possibility is this:

Yes, although I really like your more general StreamT. Since it wouldn't reside in this library here anyways, how about putting that in a separate library and creating this ChoiceT e m a newtype there? Then ChoiceT could be part of mtl.