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

[mniip]

@noughtmare With free monads in general I think you have:

reinterpret h (k >>= f) = reinterpret h k >>= \x -> reinterpret h (f x)

Specializing to MonadYield:

for (k >>= f) h = for k h >>= \x -> for (f x) h

Setting k = yield x0 and f to be a constant function, we get your thing as corollary.

[sjshuck]

class (Monad m) => MonadYield o m | m -> o where
    yield :: o -> m ()
    step :: m a -> m (Either a (o, m a))

step (return x) = return (Left x)
step (yield y >> m) = return (Right (y, m))

These seem like laws for my yield/step idea of the typeclass.

BTW, why isn't the type

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

?

[mniip]

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

So this corresponds to a different way of un-wrap-ing a free monad: instead of iterT to fold all uses of f, you pattern match on FreeT directly to find the outermost use of f, if any.

This is a stronger interface, because pattern matching on FreeT can be used to implement iterT, and likewise, step can be used to implement for:

for :: m a -> (o -> m ()) -> m a
for m cb = step m >>= \case
  Left x -> pure x
  Right (o, m') -> cb o >> for m' cb

Is it strictly stronger? I cannot tell, but there's going to be difficulty implementing this interface if your pipe monad is CPS encoded, rather than being an ADT.

BTW, why isn't the type for :: (MonadYield o m) => m a -> (o -> m b) -> m a

Mathematically, the two types are equivalent, by parametricity this for is required to discard the b's. However from the PoV of designing the library to encourage people to write maintainable code, I think it's better if discarding data has to be explicitly initiated by the user.

[sjshuck]

step can be used to implement for

Agreed, see above. And it more directly expresses the required reentrancy property; for by itself doesn't do that. yield yields a value and step yields execution. It also expresses when execution yields: every value comes with a breakpoint and vice versa. This is important when a streaming type has different non-yielding constructors Pure and Effect but the consumer doesn't care and merely wants to fast-forward to the next value always.

A better name than step might be next.

difficulty implementing this interface if your pipe monad is CPS encoded

I am glad you brought this up because I'm at the point where I want to sketch out a concrete transformer, and I had in mind a CPS'd one. My understanding from conduit docs is it has better "fusion" (the non-CPS'd one SealedConduit has a more niche use case that may not be applicable to us). But if ~step~ next has a lot of friction with that encoding, we might end up with a Foldable situation where there are tons of methods with default implementations.

I think it's better if discarding data has to be explicitly initiated by the user.

While I disagree, I think reasoned arguments exist in both directions. I will say that the strong tendency in base is to implicitly discard: forever, (>>), mapM_, ... But at least forkIO is an exception.