Resolving implicit instances of type-classes for union types

Question
1

I have what feels like a simple example I tested for trying to be able to generate a type-class for a union type:

final case class Options[T](options: List[T]) {
  def |[T2](that: Options[T2]): Options[T | T2] = Options(this.options ::: that.options)
}
object Options {

  def apply[A](implicit ev: Options[A]): Options[A] = ev

  inline given union[A, B](using a: Options[A], b: Options[B]): Options[A | B] = a | b

}

I tried a bunch of stuff with NotGiven, as well as trying to using macros to assert that A < B lexicographically, and that A and B are disjoint (using macros), and was having no success.

It seems to me that whenever you’d want the compiler to try calling union[A, B], it actually tries calling it with union[A | B, A | B].

Its quite likely Im just being a dummy here, and theres actually an obvious way to do this, and I just dont know what it is. If thats the case, please tell me what Im doing wrong. If Im not missing something totally obvious here, it feels like this is a bit of a compiler issue. I feel like getting an implicit instance of F[A | B] given an F[A] and F[B] should be a super simple thing to do, and that is just not my experience today.

Any help or comments are super welcome, thanks!

1 Like
2

It seems this doesnt work with intersection types either.

  final case class Validate[A](validate: A => Boolean)
  object Validate {

    def apply[A](implicit ev: Validate[A]): Validate[A] = ev

    given intersection[A, B](using a: Validate[A], b: Validate[B]): Validate[A & B] =
      Validate[A & B] { i => a.validate(i) && b.validate(i) }

  }

  trait TraitA {
    val a: Int
  }
  trait TraitB {
    val b: Int
  }

  final case class AAndB(a: Int, b: Int) extends TraitA with TraitB

  implicit val validateA: Validate[TraitA] = Validate { _.a > 0 }
  implicit val validateB: Validate[TraitB] = Validate { _.b < 0 }

  println(Validate[TraitA & TraitB].validate(AAndB(0, 0)))
3

Here is a full example of the Options type, that should allow for both A | B and A & B to work:

  final case class Options[T](
      options: List[T],
      cast: Any => Option[T],
  ) {

    def |[T2](that: Options[T2]): Options[T | T2] =
      Options(
        this.options ::: that.options,
        any => this.cast(any).orElse(that.cast(any)),
      )

    def &[T2](that: Options[T2]): Options[T & T2] = {
      val cast: Any => Option[T & T2] =
        any => Option.when(this.cast(any).nonEmpty && that.cast(any).nonEmpty)(any.asInstanceOf[T & T2])
      Options(
        (this.options ::: that.options).flatMap(cast),
        cast,
      )
    }

  }
  object Options {

    def apply[A](implicit ev: Options[A]): Options[A] = ev

    def make[A](as: A*)(implicit ct: ClassTag[A]): Options[A] = Options(as.toList, ct.unapply)

    inline given union[A, B](using a: Options[A], b: Options[B]): Options[A | B] = a | b
    inline given inter[A, B](using a: Options[A], b: Options[B]): Options[A & B] = a & b

  }

  trait TraitA { val a: Int }
  object TraitA {
    def apply(_a: Int): TraitA =
      new TraitA {
        override val a: Int = _a
        override def toString: String = s"TraitA($a)"
      }
  }

  trait TraitB { val b: Int }
  object TraitB {
    def apply(_b: Int): TraitB =
      new TraitB {
        override val b: Int = _b
        override def toString: String = s"TraitB($b)"
      }
  }

  final case class AAndB(a: Int, b: Int) extends TraitA with TraitB

  implicit val traitAOptions: Options[TraitA] = Options.make(TraitA(1), AAndB(1, 1))
  implicit val traitBOptions: Options[TraitB] = Options.make(TraitB(2), AAndB(2, 2))

  println("    union: " + Options[TraitA | TraitB](using Options.union[TraitA, TraitB]).options.mkString(", "))
  println("intersect: " + Options[TraitA & TraitB](using Options.inter[TraitA, TraitB]).options.mkString(", "))

  // TODO (KR) : work without explicit instance
  // println("    union: " + Options[TraitA | TraitB].options.mkString(", "))
  // println("intersect: " + Options[TraitA & TraitB].options.mkString(", "))

[info]     union: TraitA(1), AAndB(1,1), TraitB(2), AAndB(2,2)
[info] intersect: AAndB(1,1), AAndB(2,2)
4

There were some discussions on the scala discord server relating to this:

TLDR, its a tricky problem to solve for disambiguating A | B and B | A. This gets even trickier when you have to worry about

  • A | B | C | D
  • A | B | (C & D)
  • (A & B) | C | D
  • A | (B & C) | D
  • (A & B) | (C & D).

Would it be possible to have the compiler be able to generate a Union instance like this?

actual repr:

  trait Union[AB] {
    type A
    type B
  }

example repr:

  sealed trait SimpleType
  object SimpleType {

    final case class Basic(name: String) extends SimpleType {
      override def toString: String = name
    }

    final case class Or(left: SimpleType, right: SimpleType) extends SimpleType {
      override def toString: String = s"($left | $right)"
    }

    final case class And(left: SimpleType, right: SimpleType) extends SimpleType {
      override def toString: String = s"($left & $right)"
    }

  }

  final case class UnionInstance(ab: SimpleType, a: SimpleType, b: SimpleType)
  object UnionInstance {

    implicit val ord: Ordering[SimpleType.Basic | SimpleType.And] =
      Ordering
        .by[SimpleType.Basic | SimpleType.And, Int] {
          case SimpleType.Basic(_)  => 1
          case SimpleType.And(_, _) => 2
        }
        .orElseBy(_.toString)

    private def flattenOrs(t: SimpleType): List[SimpleType.Basic | SimpleType.And] =
      t match
        case SimpleType.Or(left, right) => flattenOrs(left) ::: flattenOrs(right)
        case t @ SimpleType.Basic(_)    => t :: Nil
        case t @ SimpleType.And(_, _)   => t :: Nil

    private def makeOrs(a: SimpleType, b: List[SimpleType]): SimpleType =
      b match
        case head :: tail => SimpleType.Or(a, makeOrs(head, tail))
        case Nil          => a

    def make(ab: SimpleType): Option[UnionInstance] =
      flattenOrs(ab).sorted match
        case a :: b :: c => UnionInstance(ab, a, makeOrs(b, c)).some
        case _           => None

  }

examples:

  given Conversion[String, SimpleType] = SimpleType.Basic(_)
  extension (self: SimpleType) {
    def ||(that: SimpleType): SimpleType = SimpleType.Or(self, that)
    def &&(that: SimpleType): SimpleType = SimpleType.And(self, that)
  }

  println(UnionInstance.make("A" || "B" || "C" || "D"))
  println(UnionInstance.make(("A" || "B") || ("C" || "D")))
  println(" ")
  println(UnionInstance.make(("A" || "B") || ("C" && "D")))
  println(UnionInstance.make("A" || "B" || ("C" && "D")))
  println(UnionInstance.make("A" || "B" || ("C" && "D")))
  println(UnionInstance.make(("A" || ("C" && "D")) || "B"))
  println(" ")
  println(UnionInstance.make("A"))
  println(UnionInstance.make("A" && ("B || C")))

[info] Some(UnionInstance( (((A | B) | C) | D) , A , (B | (C | D))) )
[info] Some(UnionInstance( ((A | B) | (C | D)),A,(B | (C | D))))
[info]  
[info] Some(UnionInstance(((A | B) | (C & D)),A,(B | (C & D))))
[info] Some(UnionInstance(((A | B) | (C & D)),A,(B | (C & D))))
[info] Some(UnionInstance(((A | B) | (C & D)),A,(B | (C & D))))
[info] Some(UnionInstance(((A | (C & D)) | B),A,(B | (C & D))))
[info]  
[info] None
[info] None
5

I don’t know about the rest, but this should be impossible (by design)
Both | and & are commutative operators

1 Like
6

Just to add to @Sporarum here are the docs saying intersections and unions are commutative.

1 Like
7

Ended up getting this to work:


import scala.quoted.*

trait UnionMirror[A] {
  type ElementTypes <: Tuple
}
object UnionMirror {

  final class Impl[A, T <: Tuple] extends UnionMirror[A] {
    override type ElementTypes = T
  }

  transparent inline given derived[A]: UnionMirror[A] = ${ derivedImpl[A] }

  private def derivedImpl[A](using quotes: Quotes, tpe: Type[A]): Expr[UnionMirror[A]] = {
    import quotes.reflect.*

    type Elems <: Tuple

    @scala.annotation.nowarn
    def expandTypes(repr: TypeRepr): List[TypeRepr] =
      repr.dealias match {
        case OrType(left, right) => expandTypes(left) ::: expandTypes(right)
        case _                   => repr :: Nil
      }

    val tupleAppend = TypeRepr.of[? *: ?].asInstanceOf[AppliedType].tycon

    val expanded: List[TypeRepr] = expandTypes(TypeRepr.of[A])

    if (expanded.size < 2)
      report.errorAndAbort(s"Type ${TypeRepr.of[A].show} is not a union type")

    given Type[Elems] =
      expanded
        .foldRight(TypeRepr.of[EmptyTuple]) { case (t, acc) =>
          AppliedType(
            tupleAppend,
            List(t, acc),
          )
        }
        .asType
        .asInstanceOf[Type[Elems]]

    Apply(
      TypeApply(
        Select.unique(
          New(
            Applied(
              TypeTree.of[UnionMirror.Impl],
              List(
                TypeTree.of[A],
                TypeTree.of[Elems],
              ),
            ),
          ),
          "<init>",
        ),
        List(
          TypeTree.of[A],
          TypeTree.of[Elems],
        ),
      ),
      Nil,
    ).asExprOf[UnionMirror[A]]
  }

}

  type UnionGeneric[A] = UnionMirror[A]

  trait DerivableUnion[T[_]] {

    protected inline def foldUnion[A, B](ta: T[A], tb: T[B]): T[A | B]

    final inline def deriveUnion[A](implicit ev: UnionGeneric[A]): T[A] = {
      summonFlatFieldInstances[ev.ElementTypes, T]
        .reduceLeft { (a, b) => foldUnion(a.asInstanceOf[T[Any]], b.asInstanceOf[T[Any]]) }
        .asInstanceOf[T[A]]
    }

  }
  object DerivableUnion {

    trait Auto[T[_]] extends DerivableUnion[T] {
      final inline implicit def deriveUnionAuto[A](implicit ev: UnionGeneric[A]): T[A] = deriveUnion[A]
    }

  }

(same concept also works for Intersection types)

1 Like