Union types and generalisations

Dotty
1

Hi dotty folks, not sure if this is the best place to post this question. I’ve already tried gitter and users.scala-lang.org does not have a dotty dedicated section.

Out of curiosity, I’ve been looking at union types, trying to get a feel for whether their current implementation would allow for a partial recovery extension method on Either, which would essentially look like this :

case class Error1()
case class Error2()

val a : Either[Error1 | Error2, Int]  = ???
val b = either.recoverOn[Error1](e1 => 0) // b inferred to Either[Error2, Int]

I’ve been bashing my head against the wall for hours on a few evenings, using my Scala2 knowledge of implicits resolution, Aux patterns, partially applied functions, etc, but keep falling short. I’ve also tried reducing the problem to obtain the following, still without success :

case class A()
case class B() 

val ab : A | B = A() 
// turning a union into an either as an extension method 
val res1 : Either[A, B] = ab.split[A] 
val res2 : Either[B, A] = ab.split[B]

without success.

So my question is : should this be possible ?

EDIT, closest I got to is this https://scastie.scala-lang.org/SKpvIekJSXyM3hLRkoWcwQ

1 Like
2

I got this far with old school syntax. I leave the translation to whatever is hip and happening in dotty at the moment as an exercise for the reader.

class RecoverOn[C, A, B](e: Either[A, B]) {                    
  def apply[X](f: C => B)(implicit ev: A <:< (X | C), ct: ClassTag[C]): Either[X, B] = e match { 
    case Left(c: C) => Right(f(c))
    case q: Either[X, B] => q } 
}

implicit class EitherSyntax[A, B](e: Either[A, B]) {
  def recoverOn[C] = new RecoverOn[C, A, B](e)
}

scala> val e: Either[Error1 | Error2, Int] = Left(Error1())
val e: Either[Error1 | Error2, Int] = Left(Error1())

scala> e.recoverOn[Error1](e => 42)
val res0: Either[Object & Product & Serializable, Int] = Right(42)

Haven’t managed to split the union type into sane parts though.

3

val res0: Either[Object & Product & Serializable, Int] = Right(42)

That’s exactly what gets me stuck. Thanks for sharing your implementation !

4

I suspect this is just a matter of type inference being too eager to throw away some information.

scala> class Split[A, B] { type C }
// defined class Split

scala> implicit def split0[A, B, C0](implicit ev: A =:= (B | C0)): Split[A, B]{type C = C0} = new Split[A,B]{ type C = C0}
def split0[A, B, C0](implicit ev: A =:= (B | C0)): Split[A, B]{C = C0}

scala> the[Split[Error1 | Error2, Error1]]
val res24: Split[Error1 | Error2, Error1]{C = Error2} = anon$1@4336b8c4

As you can see he manages to do the split here. But when I use my Split typeclass in recoverOn it doesn’t work anymore:

implicit class EitherSyntax[A, R](e: Either[A, R]) {
  def recoverOn[B](f: B => R)(implicit s: Split[A, B], ct: ClassTag[B]): Either[s.C, R] = e match { 
    case Left(b: B) => Right(f(b))
    case q: Either[s.C, R] => q 
  } 
}

scala> val x: Either[Error2, Int] = e.recoverOn[Error1](e => 42)
1 |val x: Either[Error2, Int] = e.recoverOn[Error1](e => 42)
  |                             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  |                    Found:    Either[Object & Product & Serializable, Int]
  |                    Required: Either[Error2, Int]
5

I suspect this is just a matter of type inference being to eager to throw away some information.

Indeed. Do you think I should file a bug ?

6

This comes down to being able to eliminate types from a union type, which I don’t think is directly possible. The same problem exists in Scala 2 for intersection types (A with B). I’ve had the need before to be able to eliminate types from an intersection type (in Scala 2) and solved it with a typeclass plus a fundep materialization macro. Here’s something similar in Scala 3 (lots of nice warnings, mainly because I had to do some backflips to construct the final union type as there doesn’t seem to be a way to construct types directly in the Scala 3 macro API yet):


trait Eliminate[A, B] {
  type Out
}

object Eliminate {

  import scala.quoted.{_, given}

  inline given derive[A, B] <: Eliminate[A, B] = ${ deriveImpl('[A], '[B]) }
  def deriveImpl[A, B](A: Type[A], B: Type[B])(given ctx: QuoteContext): Expr[Eliminate[A, B]] = {
    import ctx.tasty.{_, given}
    def expandOrs(typ: ctx.tasty.Type): List[ctx.tasty.Type] = typ match {
      case OrType(t1, t2) => expandOrs(t1) ++ expandOrs(t2)
      case typ => List(typ)
    }

    def orAll(typs: List[ctx.tasty.Type]): ctx.tasty.Type = {
      type X1
      type X2 
      typs match {
        case last :: Nil => last
        case first :: rest =>
          first.seal match {
            case first: scala.quoted.Type[X1] => orAll(rest).seal match {
              case rest: scala.quoted.Type[X2] => or[X1, X2](given first, rest, ctx).unseal.tpe
            }
          }
      }
    }

    val as = expandOrs(A.unseal.tpe)
    val b = B.unseal.tpe
    val withoutB = as.filterNot {
      typ => typ =:= b
    }
    val resultOrType = orAll(withoutB).seal
    '{ null: Eliminate[$A, $B] { type Out = $resultOrType }}
  }
  
  def or[X1, X2](given x1: Type[X1], x2: Type[X2], ctx: QuoteContext): Type[X1 | X2] = '[$x1 | $x2]

}

You can see it work like so:

scala> summon[(String | Int | Boolean) Eliminate Int]
val res0:
  Eliminate[String | Int | Boolean, Int]{
    Out = String | Boolean
  } = null

(notice the Out type has the resulting union type).

Hopefully someone who knows dotty a little more deeply can point out the proper way to do these things (like constructing a union type from two quoted types or tasty types) :smile:

3 Likes
7

The problem is that fundamentally, eliminating a type X from a union of types is an ill-defined problem in Dotty’s type system. This is because any type T can be upcasted to T | X. So any solution you find that can take a S | X and transform it into an S won’t be able to be applied reliably, because type inference can always pick S = the original type as a valid solution, and Dotty will not perform backtracking if that solution ends up not working.

So unless @smarter manages to make type inference magically do the right thing for the use cases you care about, a macro indeed seems to be the only reliable way to make this work.

@jeremyrsmith I think it’s worth opening an issue on the Dotty repo, as they’re currently trying to finalize the design of macros.

8

I’m sure that this is something that just hasn’t been implemented yet (by which I mean constructors/combinators for building union and intersection types among others). I doubt it’s something that’s just been overlooked. It might even exist already and I just don’t know how to do it :smile:

9

It occurs to me that the use cases of both eliminating a type from a union, and eliminating a type from an intersection, could be solved by introducing a “not” mechanism for types. Imagine for example there was a syntax ~X which had the meaning of “The union of all types besides X”. Then you could express the OP’s use case kinda like this:

trait Either[+A, +B] {
  def recoverOn[E, BB >: B](fn: E => B): Either[A & ~E, BB] = ???
}

where A & ~E eliminates E from the union type A (if it is present).

Similarly, the use case for removing a type from an intersection (I won’t go into the reasons but I’ll clarify that in the use case I had, the intersection type is a phantom type), given an intersection type X like A & B & C, you could use a type bound XX >: X <: ~B for example to infer the type which is the narrowest supertype of X which is disjoint with B (i.e. A & C).

I guess it’s a little late to propose something like that for dotty, but it would be pretty powerful!

2 Likes
10

That is correct! It is funny that you should mention it, because I have been experimenting with negative types in my own type system experiments, and they are very useful.

By the way, phantom type intersections are a very useful concept (*), and eliminating types from them is often desired.

(*) As examples I could cite Squid (where it’s used for context types), Scala Effekt, and ZIO.

1 Like
11

Wait a minute, I was under the impression that complement types WERE supported in Dottie.

12

Where did you get that impression?

13

There is a kind of complement implicits type in Dotty (scala.implicits.Not), but I find it mostly unusable:

Changes in Implicit Resolution

The treatment of ambiguity errors has changed. If an ambiguity is encountered in some recursive step of an implicit search, the ambiguity is propagated to the caller. Example: Say you have the following definitions:

class A
class B extends C
class C
implicit def a1: A
implicit def a2: A
implicit def b(implicit a: A): B
implicit def c: C

and the query implicitly[C] .

This query would now be classified as ambiguous. This makes sense, after all there are two possible solutions, b(a1) and b(a2) , neither of which is better than the other and both of which are better than the third solution, c . By contrast, Scala 2 would have rejected the search for A as ambiguous, and subsequently have classified the query b(implicitly[A]) as a normal fail, which means that the alternative c would be chosen as solution!

Scala 2’s somewhat puzzling behavior with respect to ambiguity has been exploited to implement the analogue of a “negated” search in implicit resolution, where a query Q1 fails if some other query Q2 succeeds and Q1 succeeds if Q2 fails. With the new cleaned up behavior these techniques no longer work. But there is now a new special type scala.implicits.Not which implements negation directly. For any query type Q : Not[Q] succeeds if and only if the implicit search for Q fails.

14

Well if you say so then obviously I’m mistaken, but I seem to recall having the conversation in a chat with lptk. Gitter maybe?

15

I’ve been banging my head on this for a while as well.

I was turned on to https://github.com/jatcwang/hotpotato which is still early, but allows exactly the original example to be done in scala 2 with shapeless.

I’m really hopping dotty allows for this somehow, as most of my enthusiasm for union types revolves around this use case.

1 Like
16

Well, I don’t remember having such a conversation… (Also I don’t normally visit gitter much.)

17

@jeremyrsmith

Similarly, the use case for removing a type from an intersection (I won’t go into the reasons but I’ll clarify that in the use case I had, the intersection type is a phantom type), given an intersection type X like A & B & C , you could use a type bound XX >: X <: ~B for example to infer the type which is the narrowest supertype of X which is disjoint with B (i.e. A & C ).

One needs to extract the types T out of X for which T is unequal to E and intersect them, but that would be very hard with without appropriate reflection utils.

@Baccata

I’ve an example which comes close to it but not sadly enough:

import scala.reflect.ClassTag


def left[A:ClassTag,B:ClassTag,C:ClassTag](either:Either[A | B, C],fun:A=>C):Either[B,C]={
    either match {
    case Left(a:A) => Right(fun(a))
    case Left(b:B) => Left(b)
    case Right(c:C) => Right(c)
    }
 }

def right[A:ClassTag,B:ClassTag,C:ClassTag](either:Either[A | B, C],fun:B=>C):Either[A,C]={
   either match {
     case Left(a:A) => Left(a)
    case Left(b:B) => Right(fun(b))
    case Right(c:C) => Right(c)
    }
 }



object Main{
    def main(args : Array[String]) : Unit = {
      val eitherLeft:Either[Int|Double,String]=Left(2)
      val eitherRight:Either[Int|Double,String]=Left(2.0)
      def funLeft(a:Int):String="projected A"
      def funRight(a:Double):String="projected B"
      println(left[Int,Double,String](eitherLeft,funLeft))
      println(right[Int,Double,String](eitherRight,funRight))
    }
}

eitherLeft projects values of the left union type parameter if present into C and eitherRight likewise for the right union type parameter.

It should be possible to formulate these two functions as extension functions though it didn’t worked for me in scastie.

An improvement would be to group both methods into one multi method, i.e. they share the same name. However, both methods overlap for A and B equal, we need to state that A and B are unequal or we need some kinda specialization machinery in order to provide a third method covering the case of type equality.
I’m still unsure if Type or ClassTag are enough to resolve concerns about overloading collisions.

18

Worth noting that ClassTag-based type matching is unsound. For instance, see 𝐖ell-𝚻yped 𝐑eflections.

1 Like
19

By the way, a sound substitute for classtag-based pattern matching is in the work, feedback welcome: Unsound use of ClassTag.unapply · Issue #7554 · lampepfl/dotty · GitHub Fix #7554: Add TypeTest for sound pattern type test by nicolasstucki · Pull Request #7555 · lampepfl/dotty · GitHub

2 Likes
20

I absolutely love the idea of having a complement type operator! It’s a really neat thing, that could give rise to a host of new possibilites! However I have a few issues with how it could be made sound. Specifically I found that it would allow you to prove that any type is =:= to Any.
Here’s the “proof” I came up with by following the invariants I believe are in place today. Please correct me if I’ve made a mistake somewhere along the line.

Given these axioms:

A & ~A =:= Any
A & A =:= A 
A & Any =:= A
A & (B & C) =:= (A & B) & C

We can prove that A =:= Any by doing the following rewrites:

A & (A & ~A) =:= A //by expanding Any to A & ~A
(A & A) & ~A =:= A //intersection is associative
A & ~A =:= A //intersection is idempotent
Any =:= A //QED.

Is there any way around this?