Add `MonadYield`

[sjshuck]

class (Monad m) => MonadYield o m | m -> o where
    yield :: o -> m ()

pipes and conduit could have instances. It shouldn't be added here however until another more basic instance exists in transformers, which would be useful anyway since those two packages require mmorph and mono-traversable, respectively. Consider this issue also a discussion for the transformers instance.

@snoyberg has opined about the need for a more central streaming abstraction in this blog post. What are people's thoughts about a streaming type in the core libraries? In base?

cc @Gabriella439

[noughtmare]

Can you describe what it does? I'm guessing yield x behaves like tell [x] (it has an equivalent type signature), but how does it differ?

[mniip]

Is there a yield law? Is Either o an instance? Can I say yield _ = pure () making every monad an instance?

[mniip]

There's also MonadFree ((,) o), which likewise doesn't have a definite axiom but only a vague vibe that you shouldn't quotient it anyhow.

[sjshuck]

how does it differ?

tell merely accumulates, whereas yield (and lift and return) correspond to explicit variants in a free monad, like this, in that order actually. You can unwrap it and get access to the continuation, which makes it reentrant. The use case is various eliminators and combinators beyond runWriterT where you can pull yielded values from a computation whose base monad may be strict in >>= without running all of it.

law?

I have no intuition about such things but I doubt it, considering that pipes only talks about them in the context of combinators.

Is Either o an instance?

That's a good question. Probably MonadYield is MonadThrow without the constraints or the law and specialized to return (). So, not useful. You're not having any nice combinators that work forall o m. (MonadYield o m) either. All the streaming libraries have the streaming transformer as the outermost layer of the monad stack.

I'll leave the issue title as it is but just focus on the transformer for now.

Can I say yield _ = pure () making every monad an instance?

I suppose. Can't we also define trivial instances of MonadWriter for every monad?

MonadFree ((,) o)

That's more or less the encoding of streaming, except it transforms another Monad m, which is what we want from a streaming abstraction.

[mniip]

Probably MonadYield is MonadThrow without the constraints or the law.

I think an important property of MonadThrow is the fact that throwError :: e -> m Void rather than -> m ().

Can't we also define trivial instances of MonadWriter for every monad?

That's where the laws help. The fact that you can listen allows you to form a law between tell and listen that makes sure information is not dropped (for a very peculiar notion of "not dropped" though, consider WriterT w Proxy).

If you split off just the MonadTell part of the typeclass, you still have the option to say that tell x >> tell y = tell (x <> y), which is like a monoid homomorphism, implying that the monad must retain some quotient of the w monoid.

Indeed you can always quotient out everything, producing a trivial monoid (think instance Monoid ()), which is what happens with WriterT w Proxy.

But with MonadYield o you don't even have that (<>) @w to rely on. All you can say is that the monad retains some information about [o], which I don't think is usable whatsoever.

That's more or less the encoding of streaming

Well aware. I was pointing out specifically that while FreeT ((,) o) M is your typical stream monad, MonadFree ((,) o) m is supposed to be its "MTL abstraction", with lifting instances for adding more transformers on top and so on.

What's missing for useful "pipe this into that" combinators is the notion of an "un-wrap", which has the same relationship with wrap as catchError does with throwError. What would that look like? I'm not sure. An initial hunch is:

class MonadFree f m | m -> f where
  wrap :: f (m a) -> m a
  reinterpret :: (forall x. f x -> m x) -> m a -> m a
  -- reinterpret (wrap . fmap pure) = id
  -- ^ similar to `(`catchError` throwError) = id`

In the case of f ~ ((,) o) the type of reinterpret is equivalent to (o -> m ()) -> m a -> m a which should be understood as "call the given callback whenever the given action yields (and suppress the yields)"

[sjshuck]

FreeT ((,) o) m is your typical stream monad, MonadFree ((,) o) m is supposed to be its "MTL abstraction"

Ah, yep, thanks for clarifying.

Incidentally Gabriella has talked about FreeT at the end of her transformers talk. Perhaps expressing a desire to add it in.

[sjshuck]

and suppress the yields

What I want (ignore the name) is

for :: (MonadYield o m) => m a -> (o -> m b) -> m b

Would that be a kind of eliminator that lets you formulate laws?

[noughtmare]

Laws are pretty easy to develop. You just match up different operations with each other. So what happens if you apply for to yield?

for (yield x) k = ?

I think it should perhaps be for (yield x) k = k x.

Then we can consider a variation. What if there are more operations after the yield?

for (yield x >> k1) k2 = ?

If yields are really like throwing exceptions then we should just ignore k1: for (yield x >> k1) k2 = k2 x, but I'd be surprised if this is what streaming libraries really do. Perhaps it should be for (yield x >> k1) k2 = k2 x >> k1, but then the type signature of for does not work (it should be for :: (MonadYield o m) => m a -> (o -> m ()) -> m a.

[sjshuck]

Trying to think of an unwrap method.

step :: m a -> m (Either a (o, m a))

From that,

for s f = step s >>= either return (\(y, t) -> f y >> for t f)

which has a different final return type. Which is fine, I think.

[Gabriella439]

Yeah, the Pipes tutorial covers the three laws for how for and yield should interact:

for (yield x) f = f x

for m yield = m

for (for m f) g = for m (\x -> for (f x) g)

Notice that these are just the Monad laws except replacing return with yield and >>= with for. In fact, they are the Monad laws for "ListT done right"

[Gabriella439]

The equivalent MTL class would probably be something like this:

class MonadYield o m | m -> o where
    yield :: o -> m ()
    for :: m a -> (o -> m ()) -> m a

… which is almost the exact same thing as the MonadError class except that yield returns () and for keeps the return type the same (although I'm not sure I got the class signature correct). This isn't that surprising because the throwError and catchError also obey the same monad laws as yield and for:

throwError e `catchError` f = f x

m `catchError` throwError = m

(m `catchError` f) `catchError` g = m `catchError` (\x -> f x `catchError` g)

[mniip]

for :: m a -> (o -> m a) -> m a

Are you sure it's not m a -> (o -> m ()) -> m a? That's what I get from the connection via the free monad.

[Gabriella439]

Oops, yeah, I think you're right. I'll fix it

[noughtmare]

Then I think the for-yield law can be extended like this:

for (yield x >> k) f = f x >> for k f