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.