scala typeclass implicit union-types given

givens / implicits for Scala 3 Union Types

I have some typeclass, e.g.:

trait ExampleTypeClass[A]
  // imagine one or more methods here

object ExampleTypeClass:
  given ExampleTypeClass[Int] = new ExampleTypeClass{/* ... */}
  given ExampleTypeClass[Boolean] = new ExampleTypeClass{/* ... */}

Furthermore, if I have instances of that typeclass for types A and B, I would know how to implement an instance for A | B (I am aware that A | B is equivalent as in =:= to B | A, but for my case, the order is irrelevant).

The most obvious way to implement something like that would be:

  given unionExampleTypeClass[A, B](
    using a: ExampleTypeClass[A],
    b: ExampleTypeClass[B]
  ): ExampleTypeClass[A | B] = 
    new ExampleTypeClass[A | B]{
      // imagine some logic that depends on a and b here
      // (which does not depend on the order of a and b)
    }

When implemented like that, I can call this explicitly - the following compiles fine:

val intOrBoolTC1: ExampleTypeClass[Int | Boolean] = 
  unionExampleTypeClass[Int, Boolean]

val intOrBoolTC2: ExampleTypeClass[Int | Boolean] = 
  unionExampleTypeClass[Boolean, Int]

However, implicit resolution fails:

val intOrBoolTC3 = summon[ExampleTypeClass[Int | Boolean]]
// results in:
//[error] Ambiguous given instances: both given instance given_ExampleTypeClass_Int in object ExampleTypeClass and given instance given_ExampleTypeClass_Boolean in object ExampleTypeClass match type ExampleTypeClass[A] of parameter x of method summon in object Predef
// [error] val intOrBoolTC3 = summon[ExampleTypeClass[Int | Boolean]]
// [error]                                                           ^

Is there a way to make the combined implementation for A | B available in implicit scope so that summoning such instances would work?

I also tried some variants with inline and summonInline, but those did not solve the main problem which (as far as I understand) seems to be that both unionExampleTypeClass[Int, Boolean] and unionExampleTypeClass[Boolean, Int] return the desired type, leading to ambiguity.

I found a kind of related question Implicit conversion between a Union Type and Either in Scala 3, but besides confirming my suspicion what the root problem might be, I did not find an answer there.

Solution

In order to resolve ambiguity you can prioritize instances of type class:

trait LowPriorityExampleTypeClass:
  given ExampleTypeClass[Int] = null

object ExampleTypeClass extends LowPriorityExampleTypeClass:
  given ExampleTypeClass[Boolean] = null

trait LowPriorityExampleTypeClass:
  given ExampleTypeClass[Boolean] = null

object ExampleTypeClass extends LowPriorityExampleTypeClass:
  given ExampleTypeClass[Int] = null

You can try to use type class similar to shapeless.Lub ("least upper bound") in Scala 2 https://github.com/milessabin/shapeless/blob/main/core/shared/src/main/scala/shapeless/typeoperators.scala#L186-L202 Covariance between 3 types in Scala

trait Lub[-A, -B, Out]:
  def left(a: A): Out
  def right(b: B): Out
object Lub:
  given [T]: Lub[T, T, T] with
    def left(a: T): T = a
    def right(b: T): T = b

given unionExampleTypeClass[A, B, Out](using
  ExampleTypeClass[A],
  ExampleTypeClass[B],
  Lub[A, B, Out],
): ExampleTypeClass[Out] = null

But then not only summon[ExampleTypeClass[Int | Boolean]] will compile, also for example summon[ExampleTypeClass[Any]] will:

https://scastie.scala-lang.org/DmytroMitin/680pTCXQQkqRxaXa2V6ldQ/5

If you want to forbid ExampleTypeClass[Any] etc. you can add constraints NotGiven[Out =:= Any], NotGiven[Out =:= AnyVal], NotGiven[Out =:= AnyRef]:

given unionExampleTypeClass[A, B, Out](using
  ExampleTypeClass[A],
  ExampleTypeClass[B],
  Lub[A, B, Out],
  NotGiven[Out =:= Any],
  NotGiven[Out =:= AnyVal],
  NotGiven[Out =:= AnyRef],
): ExampleTypeClass[Out] = null

https://scastie.scala-lang.org/DmytroMitin/680pTCXQQkqRxaXa2V6ldQ/8

But still an instance of type class will be defined not only for Int | Boolean. For example if you introduce an abstract type T >: Int | Boolean, summon[ExampleTypeClass[T]] will compile too.

I also tried some variants with inline and summonInline, but those did not solve the main problem which (as far as I understand) seems to be that both unionExampleTypeClass[Int, Boolean] and unionExampleTypeClass[Boolean, Int] return the desired type, leading to ambiguity.

I guess the reason of ambiguity is different. If we don't prioritize the instances then both ExampleTypeClass[Int] and ExampleTypeClass[Boolean] are eligible candidates for a: ExampleTypeClass[A] in given unionExampleTypeClass[A, B]. If we prioritize the instances (like I did) then the higher-priority instance is eligible candidate both for a: ExampleTypeClass[A] and b: ExampleTypeClass[B] and given unionExampleTypeClass[A, B] produces an implicit of the type ExampleTypeClass[A | A] i.e. ExampleTypeClass[A] instead of ExampleTypeClass[A | B] with different A, B. It's difficult to express the logic "do not take the same implicit for the second time" without something like

given unionExampleTypeClass[A, B](using
  ExampleTypeClass[A],
  SecondBest[ExampleTypeClass[B]],
): ExampleTypeClass[A | B] = null

Finding the second matching implicit

(NotGiven[A =:= B] doesn't work because this constraint is checked after it's already inferred that A = B = higher-priority candidate i.e. when it's too late. We don't have A ≠ B on type-inference level like <:, we have it only on implicit-resolution level like =:=, <:<, NotGiven[... =:= ...], NotGiven[... <:< ...]. Actually, A ≠ B shouldn't be expressible because in DOT calculus every type is a segment [Lower, Upper] but A ≠ B is a union of two intervals rather than segments [Nothing, B), (B, Any].)

Try the macro

import scala.quoted.*

transparent inline given unionExampleTypeClass[X]: ExampleTypeClass[X] =
  ${unionExampleTypeClassImpl[X]}

def unionExampleTypeClassImpl[X: Type](using Quotes): Expr[ExampleTypeClass[X]] =
  import quotes.reflect.*
  TypeRepr.of[X] match
    case OrType(l, r) =>
      (l.asType, r.asType) match
        case ('[a], '[b]) =>
          (Expr.summon[ExampleTypeClass[a]], Expr.summon[ExampleTypeClass[b]]) match
            case (Some(aInst), Some(bInst)) =>
              '{
                val x = $aInst
                val y = $bInst
                new ExampleTypeClass[a | b] {}
              }.asExprOf[ExampleTypeClass[X]]

(I am aware that A | B is equivalent as in =:= to B | A, but for my case, the order is irrelevant).

both unionExampleTypeClass[Int, Boolean] and unionExampleTypeClass[Boolean, Int] return the desired type, leading to ambiguity.

Actually, the thing is not only in order. It's true that Either[A, B] =:= Either[Int, Boolean] means A =:= Int and B =:= Boolean. But A | B =:= Int | Boolean doesn't mean that A =:= Int and B =:= Boolean. It even doesn't follow that A =:= Int, B =:= Boolean or vice versa A =:= Boolean, B =:= Int. There is also an option: A =:= Int | Boolean and B =:= Nothing or vice versa A =:= Nothing and B =:= Int | Boolean. And moreover, A =:= Int | Boolean, B =:= T or vice versa A =:= T, B =:= Int | Boolean, where T is an arbitrary (maybe abstract) type such that T <: Int | Boolean.

When you consider A | B =:= Int | Boolean as a synonym for A =:= Int, B =:= Boolean this means that your logic is not ordinary logic with types (including union types A | B). Your logic is a macro logic where you consider A | B as an AST (actually, type tree). So it's not surprising that this logic can be expressed with a macro.