Why is Deferred factory method has return value in the context of F

Question

I'm looking at cats.effect.concurrent.Deferred and noticed that all pure factory methods inside its companion object return the F[Deferred[F, A]], not just Deferred[F, A] like

def apply[F[_], A](implicit F: Concurrent[F]): F[Deferred[F, A]] =
  F.delay(unsafe[F, A])

but

  /**
    * Like `apply` but returns the newly allocated promise directly instead of wrapping it in `F.delay`.
    * This method is considered unsafe because it is not referentially transparent -- it allocates
    * mutable state.
    */
  def unsafe[F[_]: Concurrent, A]: Deferred[F, A]

Why?

The abstract class has two methods defined (docs omitted):

abstract class Deferred[F[_], A] {
  def get: F[A]
  def complete(a: A): F[Unit]
}

So even if we allocate Deferred directly it is not clear how the state of Deferred can be modified via its public method. All modification are suspended with F[_].

Travis Brown · Accepted Answer · 2019-02-25T13:29:12.873

The issue isn't whether or not mutation is suspended in F, it's whether Deferred.unsafe allows you to write code that isn't referentially transparent. Consider the following two programs:

import cats.effect.{ContextShift, IO}
import cats.effect.concurrent.Deferred
import cats.implicits._
import scala.concurrent.ExecutionContext

implicit val cs: ContextShift[IO] = IO.contextShift(ExecutionContext.global)

val x = Deferred.unsafe[IO, Int]

val p1 = x.complete(1) *> x.get
val p2 = Deferred.unsafe[IO, Int].complete(1) *> Deferred.unsafe[IO, Int].get

These two programs aren't equivalent: p1 will compute 1 and p2 will wait forever. The fact that we can construct an example like this shows that Deferred.unsafe isn't referentially transparent—we can't freely replace calls to it with references and end up with equivalent programs.

If we try to do the same thing with Deferred.apply, we'll find that we can't come up with pairs of non-equivalent programs by replacing references with values. We could try this:

val x = Deferred[IO, Int]

val p1 = x.flatMap(_.complete(1)) *> x.flatMap(_.get)
val p2 = Deferred[IO, Int].flatMap(_.complete(1)) *> Deferred[IO, Int].flatMap(_.get)

…but that gives us two programs that are equivalent (both hang). Even if we try something like this:

val x = Deferred[IO, Int]

val p3 = x.flatMap(x => x.complete(1) *> x.get)

…all referential transparency tells us is that we can rewrite that code to the following:

val p4 = Deferred[IO, Int].flatMap(x => x.complete(1) *> x.get)

…which is equivalent to p3, so we've failed to break referential transparency again.

The fact that we can't get a reference to the mutable Deferred[IO, Int] outside of the context of F when we use Deferred.apply is specifically what's protecting us here.

That way any method creating an instance encapsulating mutable state (even though the mutable state is accessed through methods where mutation is suspended in `F[_]`) cannot be considered referential transparent. Is that correct? — Some Name, Feb 25 '19 at 14:55

Why is Deferred factory method has return value in the context of F

1 Answers1