How to define "type disjunction" (union types)?

Question

One way that has been suggested to deal with double definitions of overloaded methods is to replace overloading with pattern matching:

object Bar {
   def foo(xs: Any*) = xs foreach { 
      case _:String => println("str")
      case _:Int => println("int")
      case _ => throw new UglyRuntimeException()
   }
}

This approach requires that we surrender static type checking on the arguments to foo. It would be much nicer to be able to write

object Bar {
   def foo(xs: (String or Int)*) = xs foreach {
      case _: String => println("str")
      case _: Int => println("int")
   }
}

I can get close with Either, but it gets ugly fast with more than two types:

type or[L,R] = Either[L,R]

implicit def l2Or[L,R](l: L): L or R = Left(l)
implicit def r2Or[L,R](r: R): L or R = Right(r)

object Bar {
   def foo(xs: (String or Int)*) = xs foreach {
      case Left(l) => println("str")
      case Right(r) => println("int")
   }
}

It looks like a general (elegant, efficient) solution would require defining Either3, Either4, .... Does anyone know of an alternate solution to achieve the same end? To my knowledge, Scala does not have built-in "type disjunction". Also, are the implicit conversions defined above lurking in the standard library somewhere so that I can just import them?

Poussin

stackoverflow.com/questions/62173145 stackoverflow.com/questions/73916845 – Inclement

Answer 1

Well, in the specific case of Any*, this trick below won't work, as it will not accept mixed types. However, since mixed types wouldn't work with overloading either, this may be what you want.

First, declare a class with the types you wish to accept as below:

class StringOrInt[T]
object StringOrInt {
  implicit object IntWitness extends StringOrInt[Int]
  implicit object StringWitness extends StringOrInt[String]
}

Next, declare foo like this:

object Bar {
  def foo[T: StringOrInt](x: T) = x match {
    case _: String => println("str")
    case _: Int => println("int")
  }
}

And that's it. You can call foo(5) or foo("abc"), and it will work, but try foo(true) and it will fail. This could be side-stepped by the client code by creating a StringOrInt[Boolean], unless, as noted by Randall below, you make StringOrInt a sealed class.

It works because T: StringOrInt means there's an implicit parameter of type StringOrInt[T], and because Scala looks inside companion objects of a type to see if there are implicits there to make code asking for that type work.

Boast

If class StringOrInt[T] is made sealed, the "leak" you referred to ("Of course, this could be side-stepped by the client code by creating a StringOrInt[Boolean]") is plugged, at least if StringOrInt resides in a file of its own. Then the witness objects must be defined in the same souce as StringOrInt. – Eyla

I tried generalizing this solution somewhat (posted as an answer below). The main drawback compared to the Either approach seems to be that we lose a lot of compiler support for checking the match. – Poussin

nice trick! However, even with the sealed class, you can still circumvent it in client code either by defining an implicit val b = new StringOrInt[Boolean] in scope with foo, or by calling explicitly foo(2.9)(new StringOrInt[Double]). I think you need to make the class abstract as well. – Barbi

Yes; it would probably be better to use trait StringOrInt ... – Anklebone

Seems like this is a typeclass, so while you can create a context where it works, StringOrInt is not a type per se, and you cannot create List[StringOrInt]... correct me if I'm wrong. – Olivier

@VladPatryshev You are correct, though this hardly qualifies as a type class. Rather, the type class pattern in Scala uses the same mechanism as this, but this solves a completely different problem. – Boast

P.s. if you want to support subtypes simply change StringOrInt[T] to StringOrInt[-T] (see #24388201) – Menace

@Matt That's a completely different issue. List("foo","bar").map(x => Bar.foo(x)) does compile. The problem with the first is that it will try to resolve the implicit before finding out the types of the function, and there's no implicit for the existential type T. – Boast

@DanielC.Sobral is it possible to use this technique for return types? re: https://mcmap.net/q/95567/-is-there-a-oneof-class-for-grouping-classes-with-no-common-ancestor/33689 – Rickety

Answer 2

Miles Sabin describes a very nice way to get union type in his recent blog post Unboxed union types in Scala via the Curry-Howard isomorphism:

He first defines negation of types as

type ¬[A] = A => Nothing

using De Morgan's law this allows him to define union types

type ∨[T, U] = ¬[¬[T] with ¬[U]]

With the following auxiliary constructs

type ¬¬[A] = ¬[¬[A]]
type |∨|[T, U] = { type λ[X] = ¬¬[X] <:< (T ∨ U) }

you can write union types as follows:

def size[T : (Int |∨| String)#λ](t : T) = t match {
    case i : Int => i
    case s : String => s.length
}

Blois

Thanks for passing that along. Absolutely brilliant! – Poussin

Still trying to figure out how to make this work in a vararg context, where individual arguments may be of different "concrete" types. – Olivier

Here is my extended implementation of Miles' idea: github.com/GenslerAppsPod/scalavro/blob/master/util/src/main/… -- with examples: github.com/GenslerAppsPod/scalavro/blob/master/util/src/test/… – Gahan

The above comment should be an answer on its own. It is just an implementation of Miles's idea, but wrapped up nicely in a package on Maven Central, and without all those unicode symbols that might (?) pose a problem for something in a build process somewhere. – Sestos

@JimPivarski is there such a library out there that you know of? – Menace

Follow the link in Connor Doyle's comment. It leads to a package that he wrote, which is on Maven Central. (At least, that's what I remember when I followed up on this last year.) – Sestos

That funny character is boolean negation. – Blois

Initially, the idea looked far too convoluted to me. Reading almost every link mentioned in this thread, I was caught by the idea and by the beauty of its implementation :-) ... but I'm still feeling like this is something convoluted... now just because it's not yet available straight away from Scala. As Miles says: "Now we just need to pester Martin and Adriaan to make it directly accessible." – Revelation

archive.org link to Unboxed union types in Scala via the Curry-Howard isomorphism by Miles Sabin since his blog is currently being transitioned and the post is not available at its previous address. – Lempres

Does this allow to pass IntOrString to something that expects IntOrStringOrBoolean ? – Stiltner

I mean this : #45255770 – Stiltner

Answer 3

Dotty, a new experimental Scala compiler, supports union types (written A | B), so you can do exactly what you wanted:

def foo(xs: (String | Int)*) = xs foreach {
   case _: String => println("str")
   case _: Int => println("int")
}

Es

One of these days. – Sycamine

By the way, Dotty will be the new scala 3 (it was announced a few months ago). – Loquitur

and will be available somewhere in late 2020 – Harry

It is available. – Loquitur

Answer 4

Here is the Rex Kerr way to encode union types. Straight and simple!

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

scala> f(3)
res0: Int = 4

scala> f("hello")
res1: Int = 5

scala> f(9.2)
<console>:9: error: Cannot prove that Int with String <:< Double.
       f(9.2)
        ^

---

Source: Comment #27 under this excellent blog post by Miles Sabin which provides another way of encoding union types in Scala.

Subalternate

Unfortunately, this encoding can be defeated: scala> f(9.2: AnyVal) passes the typechecker. – Gennie

@Kipton: That's sad. Does Miles Sabin's encoding also suffer from this problem? – Subalternate

There is a slightly simpler version of Miles' code; since he's actually using the reverse implication of the contravariant parameter of the function, not a strict "not", you can use trait Contra[-A] {} in place of all the functions to nothing. So you get stuff like type Union[A,B] = { type Check[Z] = Contra[Contra[Z]] <:< Contra[Contra[A] with Contra[B]] } used like def f[T: Union[Int, String]#Check](t: T) = t match { case i: Int => i; case s: String => s.length } (without fancy unicode). – Secondary

This might solve the inheritance problem of union types ? #45255770 – Stiltner

Hmm, I tried it, I cannot create return types with this encodings, so its does not seem to be possible to implement subtyping #45255770 – Stiltner

Answer 5

It's possible to generalize Daniel's solution as follows:

sealed trait Or[A, B]

object Or {
   implicit def a2Or[A,B](a: A) = new Or[A, B] {}
   implicit def b2Or[A,B](b: B) = new Or[A, B] {}
}

object Bar {
   def foo[T <% String Or Int](x: T) = x match {
     case _: String => println("str")
     case _: Int => println("int")
   }
}

The main drawbacks of this approach are

• As Daniel pointed out, it does not handle collections/varargs with mixed types
• The compiler does not issue a warning if the match is not exhaustive
• The compiler does not issue an error if the match includes an impossible case
• Like the Either approach, further generalization would require defining analogous Or3, Or4, etc. traits. Of course, defining such traits would be much simpler than defining the corresponding Either classes.

Update:

Mitch Blevins demonstrates a very similar approach and shows how to generalize it to more than two types, dubbing it the "stuttering or".

Poussin

Answer 6

I have sort of stumbled on a relatively clean implementation of n-ary union types by combining the notion of type lists with a simplification of Miles Sabin's work in this area, which someone mentions in another answer.

Given type ¬[-A] which is contravariant on A, by definition given A <: B we can write ¬[B] <: ¬[A], inverting the ordering of types.

Given types A, B, and X, we want to express X <: A || X <: B. Applying contravariance, we get ¬[A] <: ¬[X] || ¬[B] <: ¬[X]. This can in turn be expressed as ¬[A] with ¬[B] <: ¬[X] in which one of A or B must be a supertype of X or X itself (think about function arguments).

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]"
  }

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

I did spend some time trying to combine this idea with an upper bound on member types as seen in the TLists of harrah/up, however the implementation of Map with type bounds has thus far proved challenging.

Equilateral

This is brilliant, thank you! I tried the earlier approaches but kept having issues using this with generic types as part of the union. This was the only implementation that I could get working with generic types. – Haematopoiesis

Sadly, but probably to be expected, when I try to use a Scala method that takes in a union type from Java code, it does not work. Error:(40, 29) java: method setValue in class Config cannot be applied to given types; required: X,scala.Predef.$less$colon$less<UnionTypes.package.$u00AC<java.lang.Object>,UnionTypes.package.$u00AC<X>> found: java.lang.String reason: cannot infer type-variable(s) X (actual and formal argument lists differ in length) – Haematopoiesis

Still not quite clear on some of the details in this implementation. For example, the original article defined negation as "type ¬[A] = A => Nothing" but in this version if just has "sealed trait ¬[-A]" and the trait isn't extended anywhere. How does this work? – Haematopoiesis

@Samer Adra It would work either way, the article uses Function1 as an existing contravariant type. You don't need an implementation, all you need is evidence of conformance (<:<). – Equilateral

Any idea how to have a constructor that accepts a union type? – Haematopoiesis

Is it possible to make this work with subtyping ? My experiments suggest no, but I might be wrong : #45255770 – Stiltner

Answer 7

A type class solution is probably the nicest way to go here, using implicits. This is similar to the monoid approach mentioned in the Odersky/Spoon/Venners book:

abstract class NameOf[T] {
  def get : String
}

implicit object NameOfStr extends NameOf[String] {
  def get = "str"
}

implicit object NameOfInt extends NameOf[Int] {
 def get = "int"
}

def printNameOf[T](t:T)(implicit name : NameOf[T]) = println(name.get)

---

If you then run this in the REPL:

scala> printNameOf(1)
int

scala> printNameOf("sss")
str

scala> printNameOf(2.0f)
<console>:10: error: could not find implicit value for parameter nameOf: NameOf[
Float]
       printNameOf(2.0f)

              ^

Jeffers

I could be wrong, but I don't think this is what the OP was looking for. OP was asking about a data type which could represent a disjoint union of types, and then do case analysis on it at runtime to see what the actual type turned out to be. Type classes won't solve this problem, as they're a purely compile-time construct. – Ragan

The real question being asked was how to expose different behaviour for different types, but without overloading. Without knowledge of type classes (and perhaps some exposure to C/C++), a union type appears to be the only solution. Scala's pre-existing Either type tends to reinforce this belief. Using type classes via Scala's implicits is a better solution to the underlying problem, but it's a relatively new concept and still not widely known, which is why the OP didn't even know to consider them as a possible alternative to a union type. – Jeffers

does this work with subtyping ? #45255770 – Stiltner

Answer 8

We’d like a type operator Or[U,V] that can be used to constrain a type parameters X in such a way that either X <: U or X <: V. Here's a definition that comes about as close as we can get:

trait Inv[-X]
type Or[U,T] = {
    type pf[X] = (Inv[U] with Inv[T]) <:< Inv[X]
}

Here is how it's used:

// use

class A; class B extends A; class C extends B

def foo[X : (B Or String)#pf] = {}

foo[B]      // OK
foo[C]      // OK
foo[String] // OK
foo[A]      // ERROR!
foo[Number] // ERROR!

This uses a few Scala type tricks. The main one is the use of generalized type constraints. Given types U and V, the Scala compiler provides a class called U <:< V (and an implicit object of that class) if and only if the Scala compiler can prove that U is a subtype of V. Here’s a simpler example using generalized type constraints that works for some cases:

def foo[X](implicit ev : (B with String) <:< X) = {}

This example works when X an instance of class B, a String, or has a type that is neither a supertype nor a subtype of B or String. In the first two cases, it’s true by the definition of the with keyword that (B with String) <: B and (B with String) <: String, so Scala will provide an implicit object that will be passed in as ev: the Scala compiler will correctly accept foo[B] and foo[String].

In the last case, I’m relying on the fact that if U with V <: X, then U <: X or V <: X. It seems intuitively true, and I’m simply assuming it. It’s clear from this assumption why this simple example fails when X is a supertype or subtype of either B or String: for example, in the example above, foo[A] is incorrectly accepted and foo[C] is incorrectly rejected. Again, what we want is some kind of type expression on the variables U, V, and X that is true exactly when X <: U or X <: V.

Scala’s notion of contravariance can help here. Remember the trait trait Inv[-X]? Because it is contravariant in its type parameter X, Inv[X] <: Inv[Y] if and only if Y <: X. That means that we can replace the example above with one that actually will work:

trait Inv[-X]
def foo[X](implicit ev : (Inv[B] with Inv[String]) <:< Inv[X]) = {}

That’s because the expression (Inv[U] with Inv[V]) <: Inv[X] is true, by the same assumption above, exactly when Inv[U] <: Inv[X] or Inv[V] <: Inv[X], and by the definition of contravariance, this is true exactly when X <: U or X <: V.

It’s possible to make things a little more reusable by declaring a parametrizable type BOrString[X] and using it as follows:

trait Inv[-X]
type BOrString[X] = (Inv[B] with Inv[String]) <:< Inv[X]
def foo[X](implicit ev : BOrString[X]) = {}

Scala will now attempt to construct the type BOrString[X] for every X that foo is called with, and the type will be constructed precisely when X is a subtype of either B or String. That works, and there is a shorthand notation. The syntax below is equivalent (except that ev must now be referenced in the method body as implicitly[BOrString[X]] rather than simply ev) and uses BOrString as a type context bound:

def foo[X : BOrString] = {}

What we’d really like is a flexible way to create a type context bound. A type context must be a parametrizable type, and we want a parametrizable way to create one. That sounds like we’re trying to curry functions on types just like we curry functions on values. In other words, we’d like something like the following:

type Or[U,T][X] = (Inv[U] with Inv[T]) <:< Inv[X]

That’s not directly possible in Scala, but there is a trick we can use to get pretty close. That brings us to the definition of Or above:

trait Inv[-X]
type Or[U,T] = {
    type pf[X] = (Inv[U] with Inv[T]) <:< Inv[X]
}

Here we use structural typing and Scala’s pound operator to create a structural type Or[U,T] that is guaranteed to have one internal type. This is a strange beast. To give some context, the function def bar[X <: { type Y = Int }](x : X) = {} must be called with subclasses of AnyRef that have a type Y defined in them:

bar(new AnyRef{ type Y = Int }) // works!

Using the pound operator allows us to refer to the inner type Or[B, String]#pf, and using infix notation for the type operator Or, we arrive at our original definition of foo:

def foo[X : (B Or String)#pf] = {}

We can use the fact that function types are contravariant in their first type parameter in order to avoid defining the trait Inv:

type Or[U,T] = {
    type pf[X] = ((U => _) with (T => _)) <:< (X => _)
} 

Leonie

Can this solve the A|B <: A|B|C problem ? #45255770 I cannot tell. – Stiltner

Answer 9

There is also this hack:

implicit val x: Int = 0
def foo(a: List[Int])(implicit ignore: Int) { }

implicit val y = ""
def foo(a: List[String])(implicit ignore: String) { }

foo(1::2::Nil)
foo("a"::"b"::Nil)

See Working around type erasure ambiguities (Scala).

Blois

See #3422836. There's actually an easier hack: just add (implicit e: DummyImplicit) to one of the type signatures. – Poussin

Answer 10

You might take a look at MetaScala, which has something called OneOf. I get the impression that this doesn't work well with match statements but that you can simulate matching using higher-order functions. Take a look at this snippet, for instance, but note that the "simulated matching" part is commented out, maybe because it doesn't quite work yet.

Now for some editorializing: I don't think there's anything egregious about defining Either3, Either4, etc. as you describe. This is essentially dual to the standard 22 tuple types built in to Scala. It'd certainly be nice if Scala had built-in disjunctive types, and perhaps some nice syntax for them like {x, y, z}.

Ragan

Answer 11

I am thinking that the first class disjoint type is a sealed supertype, with the alternate subtypes, and implicit conversions to/from the desired types of the disjunction to these alternative subtypes.

I assume this addresses comments 33 - 36 of Miles Sabin's solution, so the first class type that can be employed at the use site, but I didn't test it.

sealed trait IntOrString
case class IntOfIntOrString( v:Int ) extends IntOrString
case class StringOfIntOrString( v:String ) extends IntOrString
implicit def IntToIntOfIntOrString( v:Int ) = new IntOfIntOrString(v)
implicit def StringToStringOfIntOrString( v:String ) = new StringOfIntOrString(v)

object Int {
   def unapply( t : IntOrString ) : Option[Int] = t match {
      case v : IntOfIntOrString => Some( v.v )
      case _ => None
   }
}

object String {
   def unapply( t : IntOrString ) : Option[String] = t match {
      case v : StringOfIntOrString => Some( v.v )
      case _ => None
   }
}

def size( t : IntOrString ) = t match {
    case Int(i) => i
    case String(s) => s.length
}

scala> size("test")
res0: Int = 4
scala> size(2)
res1: Int = 2

One problem is Scala will not employ in case matching context, an implicit conversion from IntOfIntOrString to Int (and StringOfIntOrString to String), so must define extractors and use case Int(i) instead of case i : Int.

---

ADD: I responded to Miles Sabin at his blog as follows. Perhaps there are several improvements over Either:

1. It extends to more than 2 types, without any additional noise at the use or definition site.
2. Arguments are boxed implicitly, e.g. don't need size(Left(2)) or size(Right("test")).
3. The syntax of the pattern matching is implicitly unboxed.
4. The boxing and unboxing may be optimized away by the JVM hotspot.
5. The syntax could be the one adopted by a future first class union type, so migration could perhaps be seamless? Perhaps for the union type name, it would be better to use V instead of Or, e.g. IntVString, `Int |v| String`, `Int or String`, or my favorite `Int|String`?

---

UPDATE: Logical negation of the disjunction for the above pattern follows, and I added an alternative (and probably more useful) pattern at Miles Sabin's blog.

sealed trait `Int or String`
sealed trait `not an Int or String`
sealed trait `Int|String`[T,E]
case class `IntOf(Int|String)`( v:Int ) extends `Int|String`[Int,`Int or String`]
case class `StringOf(Int|String)`( v:String ) extends `Int|String`[String,`Int or String`]
case class `NotAn(Int|String)`[T]( v:T ) extends `Int|String`[T,`not an Int or String`]
implicit def `IntTo(IntOf(Int|String))`( v:Int ) = new `IntOf(Int|String)`(v)
implicit def `StringTo(StringOf(Int|String))`( v:String ) = new `StringOf(Int|String)`(v)
implicit def `AnyTo(NotAn(Int|String))`[T]( v:T ) = new `NotAn(Int|String)`[T](v)
def disjunction[T,E](x: `Int|String`[T,E])(implicit ev: E =:= `Int or String`) = x
def negationOfDisjunction[T,E](x: `Int|String`[T,E])(implicit ev: E =:= `not an Int or String`) = x

scala> disjunction(5)
res0: Int|String[Int,Int or String] = IntOf(Int|String)(5)

scala> disjunction("")
res1: Int|String[String,Int or String] = StringOf(Int|String)()

scala> disjunction(5.0)
error: could not find implicit value for parameter ev: =:=[not an Int or String,Int or String]
       disjunction(5.0)
                  ^

scala> negationOfDisjunction(5)
error: could not find implicit value for parameter ev: =:=[Int or String,not an Int or String]
       negationOfDisjunction(5)
                            ^

scala> negationOfDisjunction("")
error: could not find implicit value for parameter ev: =:=[Int or String,not an Int or String]
       negationOfDisjunction("")
                            ^
scala> negationOfDisjunction(5.0)
res5: Int|String[Double,not an Int or String] = NotAn(Int|String)(5.0)

---

ANOTHER UPDATE: Regarding comments 23 and 35 of Mile Sabin's solution, here is a way to declare a union type at the use site. Note it is unboxed after the first level, i.e. it has the advantage being extensible to any number of types in the disjunction, whereas Either needs nested boxing and the paradigm in my prior comment 41 was not extensible. In other words, a D[Int ∨ String] is assignable to (i.e. is a subtype of) a D[Int ∨ String ∨ Double].

type ¬[A] = (() => A) => A
type ∨[T, U] = ¬[T] with ¬[U]
class D[-A](v: A) {
  def get[T](f: (() => T)) = v match {
    case x : ¬[T] => x(f)
  }
}
def size(t: D[Int ∨ String]) = t match {
  case x: D[¬[Int]] => x.get( () => 0 )
  case x: D[¬[String]] => x.get( () => "" )
  case x: D[¬[Double]] => x.get( () => 0.0 )
}
implicit def neg[A](x: A) = new D[¬[A]]( (f: (() => A)) => x )

scala> size(5)
res0: Any = 5

scala> size("")
error: type mismatch;
 found   : java.lang.String("")
 required: D[?[Int,String]]
       size("")
            ^

scala> size("hi" : D[¬[String]])
res2: Any = hi

scala> size(5.0 : D[¬[Double]])
error: type mismatch;
 found   : D[(() => Double) => Double]
 required: D[?[Int,String]]
       size(5.0 : D[?[Double]])
                ^

Apparently the Scala compiler has three bugs.

1. It will not choose the correct implicit function for any type after the first type in the destination disjunction.
2. It doesn't exclude the D[¬[Double]] case from the match.

3.

scala> class D[-A](v: A) {
  def get[T](f: (() => T))(implicit e: A <:< ¬[T]) = v match {
    case x : ¬[T] => x(f)
  }
}
error: contravariant type A occurs in covariant position in
       type <:<[A,(() => T) => T] of value e
         def get[T](f: (() => T))(implicit e: A <:< ?[T]) = v match {
                                           ^

The get method isn't constrained properly on input type, because the compiler won't allow A in the covariant position. One might argue that is a bug because all we want is evidence, we don't ever access the evidence in the function. And I made the choice not to test for case _ in the get method, so I wouldn't have to unbox an Option in the match in size().

---

March 05, 2012: The prior update needs an improvement. Miles Sabin's solution worked correctly with subtyping.

type ¬[A] = A => Nothing
type ∨[T, U] = ¬[T] with ¬[U]
class Super
class Sub extends Super

scala> implicitly[(Super ∨ String) <:< ¬[Super]]
res0: <:<[?[Super,String],(Super) => Nothing] = 

scala> implicitly[(Super ∨ String) <:< ¬[Sub]]
res2: <:<[?[Super,String],(Sub) => Nothing] = 

scala> implicitly[(Super ∨ String) <:< ¬[Any]]
error: could not find implicit value for parameter
       e: <:<[?[Super,String],(Any) => Nothing]
       implicitly[(Super ? String) <:< ?[Any]]
                 ^

My prior update's proposal (for near first-class union type) broke subtyping.

 scala> implicitly[D[¬[Sub]] <:< D[(Super ∨ String)]]
error: could not find implicit value for parameter
       e: <:<[D[(() => Sub) => Sub],D[?[Super,String]]]
       implicitly[D[?[Sub]] <:< D[(Super ? String)]]
                 ^

The problem is that A in (() => A) => A appears in both the covariant (return type) and contravariant (function input, or in this case a return value of function which is a function input) positions, thus substitutions can only be invariant.

Note that A => Nothing is necessary only because we want A in the contravariant position, so that supertypes of A are not subtypes of D[¬[A]] nor D[¬[A] with ¬[U]] (see also). Since we only need double contravariance, we can achieve equivalent to Miles' solution even if we can discard the ¬ and ∨.

trait D[-A]

scala> implicitly[D[D[Super]] <:< D[D[Super] with D[String]]]
res0: <:<[D[D[Super]],D[D[Super] with D[String]]] = 

scala> implicitly[D[D[Sub]] <:< D[D[Super] with D[String]]]
res1: <:<[D[D[Sub]],D[D[Super] with D[String]]] = 

scala> implicitly[D[D[Any]] <:< D[D[Super] with D[String]]]
error: could not find implicit value for parameter
       e: <:<[D[D[Any]],D[D[Super] with D[String]]]
       implicitly[D[D[Any]] <:< D[D[Super] with D[String]]]
                 ^

So the complete fix is.

class D[-A] (v: A) {
  def get[T <: A] = v match {
    case x: T => x
  }
}

implicit def neg[A](x: A) = new D[D[A]]( new D[A](x) )

def size(t: D[D[Int] with D[String]]) = t match {
  case x: D[D[Int]] => x.get[D[Int]].get[Int]
  case x: D[D[String]] => x.get[D[String]].get[String]
  case x: D[D[Double]] => x.get[D[Double]].get[Double]
}

Note the prior 2 bugs in Scala remain, but the 3rd one is avoided as T is now constrained to be subtype of A.

We can confirm the subtyping works.

def size(t: D[D[Super] with D[String]]) = t match {
  case x: D[D[Super]] => x.get[D[Super]].get[Super]
  case x: D[D[String]] => x.get[D[String]].get[String]
}

scala> size( new Super )
res7: Any = Super@1272e52

scala> size( new Sub )
res8: Any = Sub@1d941d7

I have been thinking that first-class intersection types are very important, both for the reasons Ceylon has them, and because instead of subsuming to Any which means unboxing with a match on expected types can generate a runtime error, the unboxing of a (heterogeneous collection containing a) disjunction can be type checked (Scala has to fix the bugs I noted). Unions are more straightforward than the complexity of using the experimental HList of metascala for heterogeneous collections.

Rolf

The #3 item above is not a bug in the Scala compiler. Note I originally had not numbered it as a bug, then carelessly made an edit today and did so (forgetting my original reason for not stating it was a bug). I didn't edit the post again, because I am at the 7 edits limit. – Rolf

The #1 bug above can be avoided with a different formulation of the size function. – Rolf

The #2 item is not a bug. Scala can't fully express a union type. The linked document provides another version of the code, so that size no longer accepts D[Any] as input. – Rolf

I don't quite get this answer, is this also an answer to this question : #45255770 – Stiltner

Answer 12

There is another way which is slightly easier to understand if you do not grok Curry-Howard:

type v[A,B] = Either[Option[A], Option[B]]

private def L[A,B](a: A): v[A,B] = Left(Some(a))
private def R[A,B](b: B): v[A,B] = Right(Some(b))  
// TODO: for more use scala macro to generate this for up to 22 types?
implicit def a2[A,B](a: A): v[A,B] = L(a)
implicit def b2[A,B](b: B): v[A,B] = R(b)
implicit def a3[A,B,C](a: A): v[v[A,B],C] = L(a2(a))
implicit def b3[A,B,C](b: B): v[v[A,B],C] = L(b2(b))
implicit def a4[A,B,C,D](a: A): v[v[v[A,B],C],D] = L(a3(a))
implicit def b4[A,B,C,D](b: B): v[v[v[A,B],C],D] = L(b3(b))    
implicit def a5[A,B,C,D,E](a: A): v[v[v[v[A,B],C],D],E] = L(a4(a))
implicit def b5[A,B,C,D,E](b: B): v[v[v[v[A,B],C],D],E] = L(b4(b))

type JsonPrimtives = (String v Int v Double)
type ValidJsonPrimitive[A] = A => JsonPrimtives

def test[A : ValidJsonPrimitive](x: A): A = x 

test("hi")
test(9)
// test(true)   // does not compile

I use similar technique in dijon

Grazier

Can this work with subtyping ? My gut feeling : no, but I might be wrong. #45255770 – Stiltner

Answer 13

Well, that's all very clever, but I'm pretty sure you know already that the answers to your leading questions are various varieties of "No". Scala handles overloading differently and, it must be admitted, somewhat less elegantly than you describe. Some of that's due to Java interoperability, some of that is due to not wanting to hit edged cases of the type inferencing algorithm, and some of that's due to it simply not being Haskell.

Feliks

While I've been using Scala for a while, I'm neither as knowledgeable nor as smart as you seem to think. In this example, I can see how a library could provide the solution. It makes sense to then wonder whether such a library exists (or some alternative). – Poussin

Answer 14

Adding to the already great answers here. Here's a gist that builds on Miles Sabin union types (and Josh's ideas) but also makes them recursively defined, so you can have >2 types in the union (def foo[A : UNil Or Int Or String Or List[String])

https://gist.github.com/aishfenton/2bb3bfa12e0321acfc904a71dda9bfbb

NB: I should add that after playing around with the above for a project, I ended up going back to plain-old-sum-types (i.e. sealed trait with subclasses). Miles Sabin union types are great for restricting the type parameter, but if you need to return a union type then it doesn't offer much.

Often

Can this solve the A|C <: A|B|C subtyping problem ? #45255770 My gut feeling NO because then it would mean that A or C would need to be the subtype of (A or B) or C but that does not contain the type A or C so there is no hope in making A or C a subtype of A or B or C with this encoding at least... what do you think ? – Stiltner

Answer 15

In Scala 3, you can use Union types Start a Scala 3 project: https://dotty.epfl.ch/#getting-started

One way is

sbt new lampepfl/dotty.g8

Then you can change directory to project, and type sbt console to start a REPL.

ref: https://dotty.epfl.ch/docs/reference/new-types/union-types.html

scala> def foo(xs: (Int | String)*) = xs foreach {
     |   case _: String => println("str")
     |   case _: Int => println("int")
     | }
def foo(xs: (Int | String)*): Unit

scala> foo(2,"2","acc",-223)                                                    
int
str
str
int

Ethicize

Answer 16

From the docs, with the addition of sealed:

sealed class Expr
case class Var   (x: String)          extends Expr
case class Apply (f: Expr, e: Expr)   extends Expr
case class Lambda(x: String, e: Expr) extends Expr

Regarding the sealed part:

It is possible to define further case classes that extend type Expr in other parts of the program (...). This form of extensibility can be excluded by declaring the base class Expr sealed; in this case, all classes that directly extend Expr must be in the same source file as Expr.

Coxcombry