Should Monad extend Defer?

[rossabaker]

The "unit-flatMap" idiom is used in various places for deferring the creation of a value where no Defer instance is available:

  def defer[A](fa: => F[A]): F[A] =
    flatMap(unit)(_ => fa)

This is not always the optimal defer implementation for a Monad, but it's always a possible one and can be overridden with optimal. It would also be binary compatible to extend Monad with Defer with this default implementation. Furthermore, with some rearrangements of instance inheritance, it seems source compatible with Cats-defined instances. Types outside Cats that define separate Monad and Defer instances today would become ambiguous without similar tricks, so it's not entirely source compatible through the ecosystem.

Before I go further: good idea or bad idea?

[rossabaker]

My gut tells me bad idea, and my default position is to be irritable about anything source breaking. But I've almost talked myself into this after a small spike.

[johnynek]

I think it is a bad idea because strict monads, such as cats.Id would just have to directly evaluate this totally destroying the intent of Defer.

Aside from intend, it would fail the current laws because the current law says defer shouldn't evaluate the arg if you just call it.

That said, maybe that's a bad law... idk.... but if that doesn't work, I don't see how fix would work, and fix and recursion is the real motivation of Defer. Having a working Defer is what allows us to implement ContT. Basically, when we are cargo culting from Haskell it is easy to not notice when laziness is required since Haskell is non-strict. Defer allows us to declare explicitly where we are leveraging laziness.

I think maybe StackSafeMonad could extend Defer in this way. That said, it's not that hard to add this implementation to the StackSafeMonad you are implementing.

[rossabaker]

You're right. I didn't have enough compiling to run more tests than MiMa, but it definitely breaks both the spirit and the letter of the law in several cases.

A place I've seen this come up repeatedly, and again today, is to avoid the eager instantiation of the fallback value on timeouts. When all people have is GenTemporal (and specifically don't want Sync), they resort to the unit.flatMap trick. Perhaps Defer could be introduced a bit earlier in the cats-effect hierarchy, but I'm convinced that Monad is too early. Thanks for validating my gut.

[satorg]

I like the idea to consider StackSafeMonad for adding Defer as a mixin. At first glance, it looks pretty natural – if we can defer evaluation, then we can afford stack safety in general – can't we?

Moreover, I would say that currently StackSafeMonad looks a bit awkward – it is nothing but a kind of "marker" trait, i.e. it does not add new functionality, but rather assumes changes in some behavior only.

[armanbilge]

I like the idea to consider StackSafeMonad for adding Defer as a mixin. At first glance, it looks pretty natural – if we can defer evaluation, then we can afford stack safety in general – can't we?

Yes indeed. This idea is discussed before in #3790 (comment).

---

Moreover, I would say that currently StackSafeMonad looks a bit awkward

Daniel explained recently on Discord:

ironically, when I introduced that trait, I intended it to be solely used as a mixin and never as a constraint 😛
I was just trying to solve the problem of everyone cargo-culting the same tailRecM implementation

[rossabaker]

Future has StackSafeMonad, but would fail the "defer does not evaluate" law.

Aside: the stack safety of the current instance depends on the stack safety of its ExecutionContext.

[satorg]

Future has StackSafeMonad, but would fail the "defer does not evaluate" law.

@rossabaker, actually, Future is an interface, so it can implemented in a way that Defer can be supported too, check this out:

Custom Future implementation (folded, because even a minimal implementation is fairly large):

final class LazyFuture[+T](get: () => Future[T]) extends Future[T] {
  private lazy val future = get()

  override def isCompleted: Boolean = future.isCompleted
  override def value: Option[Try[T]] = future.value

  override def onComplete[U](f: Try[T] => U)(implicit executor: ExecutionContext): Unit =
    future.onComplete(f)

  override def transform[S](f: Try[T] => Try[S])(implicit executor: ExecutionContext): Future[S] =
    future.transform(f)

  override def transformWith[S](f: Try[T] => Future[S])(implicit executor: ExecutionContext): Future[S] =
    future.transformWith(f)

  override def ready(atMost: Duration)(implicit permit: CanAwait): this.type = {
    future.ready(atMost)
    this
  }

  override def result(atMost: Duration)(implicit permit: CanAwait): T =
    future.result(atMost)
}

So yes, the main idea is to suspend one `Future` in another (custom) one.

Now, the implementation of Defer for Future comes out fairly simple:

object FutureDefer extends Defer[Future] {
  override def defer[A](fa: => Future[A]): Future[A] =
    new LazyFuture[A](() => fa)
}

An example of demo code:

implicit val executor: ExecutionContext = ExecutionContext.parasitic

var evaluated1 = false
var evaluated2 = false
val deferred = FutureDefer.defer {
  evaluated1 = true
  Future {
    evaluated2 = true
    12345
  }
}

println("allow some time, just in case...")
Thread.sleep(1000)

println(s"evaluated1=$evaluated1; evaluated2=$evaluated2")

println("now await the future...")
val result = Await.result(deferred, Duration.Inf)
println(s"evaluated1=$evaluated1; evaluated2=$evaluated2")
println(s"result=$result")

And here is the output:

allow some time, just in case...
evaluated1=false; evaluated2=false
now await the future...
evaluated1=true; evaluated2=true
result=12345

So it looks working even with the parasitic context.

---

That said, I am not sure if we can expect from Future to fully support the laws due it its lack of referential transparency. The following code code wouldn't work properly just because of that:

val original = Future {
  evaluated2 = true
  12345
}

val deferred = FutureDefer.defer {
  evaluated1 = true
  original
}

Apparently, the output is:

allow some time, just in case...
evaluated1=false; evaluated2=true
now await the future...
evaluated1=true; evaluated2=true
result=12345

But even in that case, evaluated1 is still properly deferred.

[satorg]

Actually, I'm inclining to think that StackSafeMonad could benefit from inheriting to Defer, check this out:

val M = Monad[Eval]

println("begin")
M.tailRecM(0) { a =>
  println(s"a=$a")
  Eval.always(Either.cond(a == 3, "done", a + 1))
}
println("end")

Even though we do not ask for the result Eval's value the very first call to f is made eagerly:

begin
a=0
end

I feel it might not be what users would expect in general.

But if StackSafeMonad was extending Defer, then it could defer the first call as well:

trait StackSafeMonad[F[_]] extends Monad[F] with Defer[F] {
  override def tailRecM[A, B](a: A)(f: A => F[Either[A, B]]): F[B] = {
    def loop(aa: A): F[B] =
      flatMap(f(aa)) {
        case Left(aaa) => loop(aaa)
        case Right(b) => pure(b)
      }

    defer(loop(a))
  }
}

[johnynek]

I'm wary of arguments about pure FP that leverage hidden side-effects to show their value. In the case of using defer(loop(a)) in the tailRecM example above, that is only an observable difference because the function f isn't pure. But when we start admitting impure functions into our code almost everything can fall apart and almost all the laws can be violated.

I know sometimes people do this, but generally, we shouldn't design for it.

That said, FlatMap.tailRecM and Defer.defer (similar to Monoid.combineAll) are making concessions to the fact that we are implementing this code on virtual machines where function evaluations consume a finite resource (stack space), and so by declaring the intent of the code directly we can get a more efficient encoding on those virtual machines. So the law in Defer about not evaluating the argument is really motivated by the desire for O(1) stack usage to do defer(foo(a)) independent of the stack usage of evaluating foo(a). In a recursive context especially this is important to convert what could be linear stack depth consumption to constant or logarithmic, which we can then actually run on our machines.

A secondary concern is the ability to short circuit a computation (e.g. foldRight) but that is only about improving the best or average case scenario, it doesn't change the worst case performance.

[rossabaker]

I agree with Oscar's sentiment here.

The motivating case here is the secondary concern: improving the average case of a timeout, when the fallback value requires an expensive stack trace and is rarely returned. We fake that today with the unit.flatMap, which risks the same miscalculation I opened the thread with. It works in practice, because the base monad of GenTemporal is usually IO, which has a lazy flatMap, even for pure IO. And if the idiom's assumption fails, it's just slow, not incorrect.

I still wonder whether GenTemporal's laws imply a lawful Defer. Nothing jumps out at me. And even then, it would be a Cats-Effect issue.

[armanbilge]

And if the idiom's assumption fails, it's just slow, not incorrect.

For some definition of correct :) constructing an exception is not pure, it is side-effectful. Depending on where and when you do it, you will capture a different stack trace. If we decide we don't care about stack traces, then it doesn't matter.

I wonder if what we need is a dedicated way to create Exceptions in the Cats(-Effect) hierarchy. That way we don't have to reach for Defer or Sync to suspend when what we specifically need is weaker.