Adding a proper ListT to transformers and this package

Question

Adding a proper ListT to transformers and this package

sofia-m-a opened this issue 4 years ago · 23 comments

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, ...

Answer 1 · 2021-07-16T17:15:54.000Z

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

Answer 2 · 2022-08-09T20:52:24.000Z

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?

Answer 3 · 2022-11-01T02:01:27.000Z

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

Answer 4 · 2022-11-01T02:06:05.000Z

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)

Answer 5 · 2022-11-01T08:45:54.000Z

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.

Answer 6 · 2022-11-01T08:56:31.000Z

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)

Answer 7 · 2022-11-01T10:43:09.000Z

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

Answer 8 · 2022-11-02T09:56:01.000Z

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.

Answer 9 · 2022-11-02T10:24:43.000Z

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).

Answer 10 · 2022-11-02T10:39:07.000Z

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?

Answer 11 · 2022-11-02T11:37:16.000Z

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

Answer 12 · 2022-11-02T13:58:24.000Z

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.

Answer 13 · 2022-11-02T19:12:40.000Z

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

Answer 14 · 2022-11-02T19:18:17.000Z

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.

Answer 15 · 2022-11-02T19:38:31.000Z

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.

Answer 16 · 2022-11-03T08:33:58.000Z

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 😅 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?

Answer 17 · 2022-11-03T08:44:15.000Z

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).

Answer 18 · 2022-11-03T08:49:48.000Z

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.

Answer 19 · 2022-11-03T08:56:06.000Z

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...

Answer 20 · 2022-11-03T09:10:48.000Z

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!

Answer 21 · 2022-11-03T09:16:42.000Z

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 ()

Answer 22 · 2022-11-03T09:21:20.000Z

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.

Answer 23 · 2022-11-03T09:26:14.000Z

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.