Proposal: adding a Defer typeclass

[johnynek]

It is often useful to have a way to see if a type constructor supports laziness.

Consider:

trait Defer[F[_]] {
  def defer[A](f: => F[A]): F[A]
}

Note, that cats-effect has this method (called suspend) on Sync: https://github.com/typelevel/cats-effect/blob/master/core/shared/src/main/scala/cats/effect/Sync.scala#L37

In cats, the law would be:

defer(fa) <-> fa

along with the ad-hoc law that:

var evaluated = false
val deferFa = defer {
  evaluated = true
  fa
}

assert(!evaluated)
deferFa <-> fa

Some example instances:

class DeferFunction0 extends Defer[Function0] {
  def defer[A](fa: => Function0[A]): Function0[A] =
    () => fa()
}

class DeferFunction1[Z] extends Defer[Z => ?] {
  def defer[A](fa: => Function[Z, A]): Function[Z, A] =
    { z: Z => fa(z) }
}

class DeferEval extends Defer[Eval] {
  def defer[A](fa: => Eval[A]): Eval[A] =
    Eval.defer(fa)
}

class DeferFree[M[_]] extends Defer[Free[M, ?]] {
  def defer[A](fa: => Free[M, A]): Free[M, A] =
    Free.defer(fa)
}

and Kleisli, IndexedStateT, EitherT, OptionT, etc... I think all have them if the F[_] they are working with has them.

One use for these, for example, is working with map2Eval on Apply:
https://github.com/typelevel/cats/blob/master/core/src/main/scala/cats/Apply.scala#L194

If we have a Defer[F] then we could (arguably) implement:

  def map2Eval[A, B, Z](fa: F[A], fb: Eval[F[B]])(f: (A, B) => Z): Eval[F[Z]] =
    Eval.later(map2(fa, defer(fb.value))(f))

If we added this typeclass, cats.effect.Sync could extend Defer with suspend == defer.

[johnynek]

To be clear: the point here is not to capture effects, but to write certain recursive algorithms.

For instance:

val foo: Parser[Int] = {
  def toIntBase10(ints: List[Int]): Int =
    ints.foldLeft(0) { (acc, digit) => acc*10 + digit }
  
   def repeat[A](p: Parser[A]): Parser[List[A]] =
     Parser.tailRecM(Nil: List[A]) { soFar =>
       p.map { a => Left(a :: soFar) }
         .orElse(Parser.pure(Right(soFar.reverse)))
     }

  repeat(Parser.digit).map(toIntBase10(_))
    .orElse(Parser.string("(") *> Parser.defer(foo) <* Parser.string(")"))
}

[non]

Abstracting over whether or not a monad supports this kind of deferment/suspension is useful. 👍