union types in scala with subtyping: A|B <: A|B|C

Question

I would like to have a A|B type to be the subtype of A|B|C. Is that possible to encode in Scala ? If yes, how ?

I was hoping that I can make implicitly[¬¬[IF] <:< T] compile below (original code here), but it does not. Is there a way to fix this code to allow subtyping ?

object NUnion{
  type ¬¬[A] = ¬[¬[A]]

  type ¬[A] = A => Nothing
  trait Disj[T] {
    type or[S] = Disj[T with ¬[S]]
    type apply = ¬[T]
  }

  // for convenience
  type disj[T] = { type or[S] = Disj[¬[T]]#or[S] }


  type T = disj[Int]#or[Float]#or[String]#apply
  type IF = disj[Int]#or[Float]#apply
  implicitly[¬¬[Int] <:< T] // works
  // implicitly[¬¬[Double] <:< T] // doesn't work
  // implicitly[¬¬[IF] <:< T] // doesn't work - but it should

}

I also tried this (from here):

object Kerr{
  def f[A](a: A)(implicit ev: (Int with String with Boolean) <:< A) = a match {
     case i: Int => i + 1
     case s: String => s.length
  }

  f(1) //works
  f("bla") // works
  def g[R]()(implicit ev: (Int with String with Boolean) <:< R):R = "go" // does not work

}

but here I cannot make a union type "first-class" they can only exist as argument types, not as return types.

Same problem with this approach :

object Map{
  object Union {
    import scala.language.higherKinds

    sealed trait ¬[-A]

    sealed trait TSet {
      type Compound[A]
      type Map[F[_]] <: TSet
    }

    sealed trait ∅ extends TSet {
      type Compound[A] = A
      type Map[F[_]] = ∅
    }

    // Note that this type is left-associative for the sake of concision.
    sealed trait ∨[T <: TSet, H] extends TSet {
      // Given a type of the form `∅ ∨ A ∨ B ∨ ...` and parameter `X`, we want to produce the type
      // `¬[A] with ¬[B] with ... <:< ¬[X]`.
      type Member[X] = T#Map[¬]#Compound[¬[H]] <:< ¬[X]

      // This could be generalized as a fold, but for concision we leave it as is.
      type Compound[A] = T#Compound[H with A]

      type Map[F[_]] = T#Map[F] ∨ F[H]
    }

    def foo[A : (∅ ∨ String ∨ Int ∨ List[Int])#Member](a: A): String = a match {
      case s: String => "String"
      case i: Int => "Int"
      case l: List[_] => "List[Int]"
    }


    def geza[A : (∅ ∨ String ∨ Int ∨ List[Int])#Member] : A = "45" // does not work 


    foo(geza)

    foo(42)
    foo("bar")
    foo(List(1, 2, 3))
//    foo(42d) // error
//    foo[Any](???) // error
  }

}

Baxy

related : contributors.scala-lang.org/t/dotty-style-union-types-in-scala/… – Baxy

Answer 1

The union type of Scala.js (source and tests) supports A | B subtype of A | B | C. It even supports permutations like A | B subtype of B | C | A.

Hilarius

Fantastic, I guess Scala cannot support this on the server side ? Or can I use them also on the server side ? Do they use something Scala.js specific ? It seems to me that this can work on the server side too, with a little bit of tinkering... right ? – Baxy

It could mostly run on the server-side, but you'd have to use an abstract type |[A, B] instead of a sealed trait, so that its erasure is Object and casts to it succeed. That has one downside, which is that there is no companion object where the implicits can go for them to be brought in the implicit scope automatically. This means that at places where you need the "subtyping relationship" to hold, you'll need an import. Whereas in the Scala.js you only need the import when you write down A | B. – Hilarius

Thanks, need to see how I can make this work and think about this erasure difference between Scala.js and Scala. – Baxy

I found a way to give an implicit scope to type | (without changing its erasure): gist.github.com/Jasper-M/96ca24e8d2aa6160159abe2c4f745206 – Spotted

Answer 2

Your first approach works OK for me. It also works with permutations of types.

type IFS = disj[Int]#or[Float]#or[String]#apply
type IF = disj[Int]#or[Float]#apply
type IS = disj[Int]#or[String]#apply
type IFD = disj[Int]#or[Float]#or[Double]#apply
type FI = disj[Float]#or[Int]#apply

scala> implicitly[IF <:< IFS]
res0: <:<[IF,IFS] = <function1>

scala> implicitly[IS <:< IFS]
res1: <:<[IS,IFS] = <function1>

scala> implicitly[FI <:< IFS]
res2: <:<[FI,IFS] = <function1>

scala> implicitly[IFD <:< IFS]
<console>:18: error: Cannot prove that IFD <:< IFS.
       implicitly[IFD <:< IFS]

Of course, you should not lift IF into a union type with ¬¬[IF], because it's already a union type. You need to do ¬¬[Int], only because Int is not a union type in this approach.

Gloucester

Interesting, thanks ! Can I use IF as a return type in a function ? – Baxy