Is there a type-class that checks for existence of at least one implicit of a type?

Question

I have a trait Foo[T, U] and a type-level algorithm that given an L <: HList and a target type U, tells me whether there exists T in L such that there is an implicit Foo[T, U] in scope. This is implemented using the following type class:

trait Search[L <: HList, U]

object Search {
  def apply[L <: HList, U](implicit s: Search[L, U]): U = null

  ...
}

and we have the following:

object Test {
  type L = Int :: String :: HNil

  implicit val foo: Foo[String, Boolean] = null

  Search[L, Boolean] //compiles

  Search[L, Double] //does not compile
}

What I would like is for the search to not take place at all if there is no Foo[T, U] for any T at all in scope, as then we already know that the algorithm will not complete. In other words, I want a type-class trait Exists[F[_]] for which instances exist if and only if there is at least one implicit F in scope, so the function Search.apply instead has signature:

def apply[L <: HList, U](implicit ev: Exists[Foo[_, U]], s: Search[L, U]): U = null

In this case the compiler will only try to resolve s if there is any implicit Foo in scope.

Is such a type-class possible to define? Does one already exist?

Banas

Answer 1

Try

import scala.language.experimental.macros
import scala.reflect.macros.{blackbox, contexts}

trait Exists[A]

object Exists {
  implicit def materialize[A]: Exists[A] = macro impl[A]

  def impl[A: c.WeakTypeTag](c: blackbox.Context): c.Tree = {
    import c.universe._
    val context = c.asInstanceOf[contexts.Context]
    val global: context.universe.type = context.universe
    val analyzer: global.analyzer.type = global.analyzer
    val callsiteContext = context.callsiteTyper.context

    val tpA = weakTypeOf[A]

    val searchResult = analyzer.inferImplicit(
      tree = EmptyTree.asInstanceOf[global.Tree],
      pt = tpA.asInstanceOf[global.Type],
      reportAmbiguous = false,
      isView = false,
      context = callsiteContext,
      saveAmbiguousDivergent = true,
      pos = c.enclosingPosition.asInstanceOf[global.Position]
    )

    val isAmbiguous = callsiteContext.reporter.firstError match {
      case Some(analyzer.AmbiguousImplicitTypeError(_,_)) => true
      case _ => false
    }

    if (searchResult.isSuccess || searchResult.isAmbiguousFailure || isAmbiguous) 
      q"new Exists[$tpA] {}"
    else c.abort(c.enclosingPosition, s"no implicit $tpA")    
  }
}

Test

// no implicit Int
// implicitly[Exists[Int]] // doesn't compile

implicit val i: Int = 1 
implicitly[Exists[Int]] // compiles

implicit val i: Int = 1 
implicit val i1: Int = 2 
implicitly[Exists[Int]] // compiles

I guess original Search was

trait Foo[U, V]

trait Search[L <: HList, V]

trait LowPrioritySearch {
  implicit def tail[H, T <: HList, V](implicit search: Search[T, V]): Search[H :: T, V] = null
}

object Search extends LowPrioritySearch {
  def apply[L <: HList, U](implicit s: Search[L, U]): U = null.asInstanceOf[U]

  implicit def head[U, T <: HList, V](implicit foo: Foo[U, V]): Search[U :: T, V] = null
}

Now with Exists

def apply[L <: HList, U](implicit ev: Exists[Foo[_, U]], s: Search[L, U]): U = null.asInstanceOf[U]

works as well

Search[L, Boolean] //compiles
// Search[L, Double] //does not compile

Tested in 2.13.0

libraryDependencies ++= Seq(
  scalaOrganization.value % "scala-reflect" % scalaVersion.value,
  scalaOrganization.value % "scala-compiler" % scalaVersion.value
)

---

Exists is still working in 2.13.10.

In Scala 3 there is API for that

import scala.quoted.{Type, Quotes, Expr, quotes}

trait Exists[A]

object Exists {
  inline given [A]: Exists[A] = ${impl[A]}

  def impl[A: Type](using Quotes): Expr[Exists[A]] = {
    import quotes.reflect.*

    Implicits.search(TypeRepr.of[A]) match {
      case _: (ImplicitSearchSuccess | AmbiguousImplicits) => '{new Exists[A]{}}
      case _ => report.errorAndAbort(s"no implicit ${Type.show[A]}")
    }
  }
}

// no implicit Int
// summon[Exists[Int]] // doesn't compile

given Int = 1
summon[Exists[Int]] // compiles

given Int = 1
given i: Int = 2
summon[Exists[Int]] // compiles

Scala 3.2.0.

Gravid

That works, but at this point I don't recommend doing this with Scala 2 macros, even less casting to Scala 2 compiler internals as you've done here. The non-macro Search you've shown is the way to go unless compile times are completely unacceptable. – Brad

Thanks Dmytro, I expected that this could only be done using macros. I also agree with @MilesSabin 's point that this probably won't offer significant compile-time improvements over my Search algorithm, but nonetheless thought that this was an interesting problem... is such a thing possible in scala 3 without macros? – Banas

It can be done with a specialised inline and an implicit match in Scala 3.There are some examples or related things in the shapeless's shapeless-3 branch. – Brad

@MilesSabin Could you explain how to achieve that? For me inline def summon[T] <: T = given match { case t: T => t } given as Int = 1 given ambig as Int = 2 summon[Int] produces error ambiguous implicit arguments. I looked at shapeless-3 branch. What code from there should be used? – Gravid

@DmytroMitin yes that will lead to ambiguity. I meant that the Search type class could be implemented in terms of specializing inline and implicit matches. – Brad

It might be possible to use the fact that Scala 3 differentiates between ambiguous implicits and just no implicits found, although it also provides its own typeclasses. – Tori

Answer 2

In Scala 3, scala.util.Not (soon to be NotGiven?), which exists if no implicits of the given type are found, can be used for this:

implicit val b: Byte = 1
  
summon[Not[Not[Byte]]] //compiles

implicit val i: Int = 0
implicit val i2: Int = 2

summon[Not[Not[Int]]] //compiles

summon[Not[Not[String]]] //doesn't compile - Not[String] not found

See it in Scastie.

Your Exists typeclass can now look like this (the syntax for givens may change soon, but you get the idea):

@annotation.implicitNotFound("No implicit of type ${T} was found")
trait Exists[T]
object Exists {
  given [T](using Not[Not[T]]) as Exists[T]
}

See it in Scastie.

Tori