"Intersection types" in Scala

Question

I know that "union types" are not supported in Scala, but what about intersection types?

In short, I would like a function like this:

def intersect[A,B,C](a: A, b: B): C = ??? // a & b

Or a method :

class A {
    def intersect[B, C](b: B): C = ??? // this & b
}

A and B share a common superclass ensuring the validity of the intersect operation, and C would be a type at the intersection ofA or B.

In my use case, A or B represent either variables or constants (of the same type). I want to distinguish, class-wise, a constant from a variable with singleton domain. If I try to intersect a set with a value, I return the value (or return the empty set/throw an exception if the value is not in the set).

Here is an example of expected output:

trait IntExpression {
  // Correct signature to be determined
  def intersect [A <: IntExpression, B <: A & this.type] (that: A): B
}
case class IntVariable(domain: Seq[Int]) extends IntExpression
case class IntConstant(value: Int) extends IntExpression

val a = IntVariable(1,2,3)
val b = IntVariable(2,3,4)
val c = IntConstant(2)

And then:

a intersect b == b intersect a == IntVariable(2,3)
a intersect c == c intersect a == IntConstant(2)

May be you can write a macro that derives such set? As long as it has access to the class hierarchy, it should be possible. — Ashalynd, Oct 17 '13 at 14:12
I don't quite understand what output you expect. Could you maybe give an example for the possible input values and the expected output? — drexin, Oct 17 '13 at 14:18
I don't see the use-case for this. Why don't you just use sets? — drexin, Oct 17 '13 at 14:58
I want to implement a DSL for a constraint programming solver. I am referring to an existing external DSL which distinguishes variables from constants. There even exists a third type of expression which represents a sequence of expressions (and is hard to unify with the remaining of the type system :() This distinction is often useful because it can lead to interesting optimizations. They could also be triggered by checking the domain size, but I wanted to use pattern-matching and additional type safety to my system. — scand1sk, Oct 17 '13 at 15:03
If you want to specify that a type is a subtype of both `A` and `B` write `A with B`. — ziggystar, Oct 17 '13 at 15:37
There is actually a way to encode union types in Scala. See [this question](http://stackoverflow.com/questions/3508077/does-scala-have-type-disjunction-union-types). — michid, Oct 17 '13 at 18:37

score 2 · Answer 1 · edited May 23 '17 at 11:52

As ziggystar is correctly stated above: A & B is A with B in Scala.

Regarding the fact you want to create your adjoint types C in runtime, you must want to create this type in runtime, based on the types you got in A and B.

Solution for this, or at least a clue, you may find at How to mix-in a trait to instance?.

However, what you want at your use-case is a case of the http://en.wikipedia.org/wiki/Dependent_type. In spite of the fact that dependent types are not supported in Scala, you may always try Agda ;)

score 0 · Answer 2 · answered Oct 17 '13 at 15:42

0

I use ++ as implementation because it's there. And intersect on Set doesn't work because Set is invariant. If this doesn't make sense, ignore it.

def intersect[C, A <: C, B <: C](as: Seq[A], bs: Seq[B]): Seq[C] = as ++ bs

answered Oct 17 '13 at 15:42

ziggystar

28,410
9
72
124

This is wrong. `intersect(Seq(1,2,3), Seq(2,3,4)) == Seq(1,2,3,2,3,4)` The op is looking for a result of `Seq(2,3)` – Ian McLaird Oct 17 '13 at 17:50

"Intersection types" in Scala

2 Answers2