Proposal: move tailRecM to FlatMap and remove FlatMapRec

[johnynek]

See this PR: #1216

Note the discussion about adding two different implementations of many of the methods, one using tailRecM the other not.

It seems that all the monads in cats can support tailRecM. In fact, it seems that if look at two classes of Monads we have "strict" (Option, Xor, Either, List, Vector, ...) and "lazy" (Free, Eval, State, ....)

In the case of the lazy monads, they are generally implemented in a stack safe way. In the case of strict monads, we can always implement tailRecM. What is an example of a monad we want to support that is not strict, yet not stack safe? I don't know of one.

Meanwhile, since authors can't depend on tailRecM, they use recursive flatMaps, and ask for Monad, when in reality they need something stronger: a Monad that supports recursive flatMaps or small enough inputs that you don't blow the stack.

To me, I'd rather tax implementers a bit more, or force some Monads into FreeT or such to get tailRecM than to deal with stack overflows due to the monad you are using (say for Xor) not supporting recursive flatMap.

[ceedubs]

Resolved in #1280 (@johnynek feel free to reopen if there was a reason for this still being open).

[adelbertc]

So after some thought and hearing about @tpolecat and @raulraja 's experience of migrating to Cats 0.7.x, I'm becoming open to the idea of just having tailRecM on FlatMap without the marker trait we currently have. My initial counter-example of tagless final algebras being not stack safe has since been disproven and I fail to find a data type for which tailRecM cannot be implemented in a lawful way.

My concern is primarily that of principle - Monad is a generally well understood, clean, abstraction and adding tailRecM to it muddies it a bit. But then again, monadic stack safety is quite important especially in a runtime like the JVM. Is there perhaps a way to mark a specific law as "optional"?

Tagging people who expressed an opinion on this before: @tpolecat @non @tixxit @travisbrown @mpilquist @ceedubs @zainab-ali @johnynek

I would also appreciate any feedback from @paf31 :-)

[paf31]

Is there a safe implementation for the list monad?

[johnynek]

There is a safe implementation for everything in cats including List and
Vector (both of which use a mutable builder internally).
On Sat, Sep 3, 2016 at 10:20 Phil Freeman [email protected] wrote:

Is there a safe implementation for the list monad?

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
#1278 (comment),
or mute the thread
https://github.com/notifications/unsubscribe-auth/AAEJdhyqTqOAk6ZiodPp_X6mjnbktvadks5qmdaMgaJpZM4JghMz
.

[adelbertc]

@paf31 We can make it safe, heap permitting, since Scala allows mutability:

cats/core/src/main/scala/cats/instances/list.scala

Line 29 in 706effc

def tailRecM[A, B](a: A)(f: A => List[Either[A, B]]): List[B] = {

- looks like we allocate a mutable buffer and append to it, converting it into an (immutable) list once we're done.

There was also a related question to that here: #1329

[djspiewak]

I'm assuming this is the issue @johnynek was referencing…

This is a lawful monad which does not have a stack-safe tailRecM implementation. It could be reimplemented to support tailRecM, but that would require altering its algebra to use (A => Eval[R]) => Eval[R] as the core function. This isn't an implementation detail: it would need to be propagated through the public API.

A more practical example is fs2.Task, which cannot have a safe tailRecM if users construct a long bind chain using asyncUnshifted.

These use-cases show up in general if you try to define a function [F[_]] scalaz.Monad[F] => cats.Monad[F], which is not possible without blowing the stack.

[djspiewak]

Copying over some context from Gitter…

@johnynek countered with the Continuation implementation in #1400, which is stack safe but only in a right-associative context. His Continuation implementation is really just Free[Cont[R, ?], A], which is a perfectly valid implementation, but hints at where the demons are hiding. Conceptual sketch:

// given a conventional Cont implementation and:
type JCont[R, A] = Free[Cont[R, ?], A]

val evil: Cont[R, JCont[R, A]] = ???
val lifted: JCont[R, JCont[R, A]] = JCont.liftM(evil)
val oops = lifted.join

Even assuming a join implemented by composing map and tailRecM, performing this construction will add a stack frame every time. Do this an arbitrary number of times, and you have constructed a counter-example to the stack safety of tailRecM.

Another way of looking at this is in the context of fs2.Task. If you want to define a function A => Task[A], there are three ways to go about it (if you ignore laziness):

object Task {
  def now(a: A): Task[A] = ???
  def async(a: (A => Unit) => Unit)(implicit S: Strategy): Task[A] = ???
  def asyncUnshift(a: (A => Unit) => Unit): Task[A] = ???
}

The first and second functions here will be stack-safe, and if Task only had these two, it would be able to implement a valid tailRecM. The only reason the second one works though is because it is literally trampolining through Strategy, which bounces the stack by thread-shifting. That's not what you want every time, and clearly it's perfectly valid not to use that function. If you use asyncUnshift, there's no bouncing of the call stack, which means that you can construct arbitrarily long bind chains which are entirely within the suspension and grow the stack on each iteration.

Note that the tailRecMStackSafety test will not catch any of this, because it only uses F.pure. The pure constructor delegates to now in Task, or simply pure in @johnynek's Continuation (which is obviously not Cont's pure, but Free's).

[johnynek]

It's true that without stack safe functions, which we could add, I see no way to make Cont totally stack safe. @mpilquist did some benchmarks on a function with stack safe andThen and it wasn't totally terrible. I mean, if you have to deal with (A => R) => R you have to use the call stack.

Here is a link to recent discussion: https://gitter.im/typelevel/cats?at=58d83c68b402a53211b5931a

Since this is the only real case we know of, I think we should attack this more directly than giving up tailRecM on all cats.Monads, since so many implementations are non-obvious, yet without them people have empirically just written unsafe code using recursive flatMap. In my view, that is much worse, since unlike tailRecM which is safe for every monad instance in cats, recursive flatMap is unsafe for almost all instances (except Free, FreeT, Eval). Indeed, even getting out or a Free (since there is no free-lunch), requires tailRecM.

[djspiewak]

As I mentioned on Gitter, what this comes down to for me is whether or not we're ok with tailRecM lying. Or equivalently, is the contract of tailRecM "always uses O(1) stack", or is it "tries very hard to use O(1) stack, but might use proportional stack under some rare circumstances." If it's the latter, then we're good all around. If it's the former though, then we're dead by definition.

If we take the strict view on tailRecM, then cats.Monad is strictly more restrictive than the mathematical definition of monad. Which is to say, there are monads which have no (truthful) cats.Monad. If we take the lenient view, then tailRecM can still be used by those that are trying to get stack safety, so long as they understand that certain monads will not be able to give it to them.

I want to be very clear that this isn't a matter of insufficient creativity in Task. There is no way to have a stack-safe tailRecM for all Task values, just like there is no way to have a stack-safe tailRecM for all Cont values. The fact is that cats.Monad only characterizes a subset of monads. Even if there's a way to encode the concepts of Task in some other form which can produce a stack-safe tailRecM (which I greatly doubt), it doesn't change the fact that Task in its original form is a monad but not a cats.Monad.

So I think the only general solution to this is to just accept that tailRecM does not guarantee sub-proportional stack usage.