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?

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.

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
}

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

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.

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".

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.

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)

              ^

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 => _)
} 

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).

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}.

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.

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

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.

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.

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

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.