Scala types: least upper bounds

Question

I am trying to parameterize some methods with very general type parameters.

As an example, in the REPL I first define:

trait Term
case class FunctionalTerm[+T <: Term](t: T) extends Term

Intuitively, the following method takes a Term and a FunctionalTerm, and returns something with type the least upper bound of the type of term passed and the argument type of the FunctionalTerm:

def ex1[T1 <: Term, T3 <: X, FunctionalTerm[T1] <: X, X <: R, R <: Term](t1: FunctionalTerm[T1], s: T3): R = sys.error("TODO")

So far so good in the REPL.

Then I define ex2 as a convenience function that performs the same operation as ex1, but with the input arguments swapped:

def ex2[T2 <: Term, T3 <: X, FunctionalTerm[T2] <: X, X <: R, R <: Term](s: T3, t2: FunctionalTerm[T2]): R = ex1(t2,s)

Attempting to define ex2 in the REPL gives the following error:

error: inferred type arguments [T2,T3,FunctionalTerm,T3,T3] do not conform to method ex1's type parameter bounds [T1 <: Term,T3 <: X,FunctionalTerm[T1] <: X,X <: R,R <: Term]
         ex1(t2,s)
         ^
error: type mismatch;
 found   : FunctionalTerm[T2]
 required: FunctionalTerm[T1]
         ex1(t2,s)
             ^
error: type mismatch;
 found   : T3(in method ex2)
 required: T3(in method ex1)
         ex1(t2,s)
                ^
error: type mismatch;
 found   : R(in method ex1)
 required: R(in method ex2)
         ex1(t2,s)
            ^

I have spent about two days trying to figure out a solution, and am now totally stuck. I cannot find anything more on Google.

Since the type argument list of ex2 is the same as that of ex1 but with T1 and T2 swapped, I don't understand is wrong, or how to fix it.

Any help would be hugely appreciated!

Update

Least upper bounds were a red herring. The example can be distilled further.

The following two functions can be defined in the REPL without error:

def ex1[T1 <: Term, FunctionalTerm[T1] <: Term](t1: FunctionalTerm[T1]): Term = sys.error("TODO: ex1")
def ex2[T2 <: Term, FunctionalTerm[T2] <: Term](t2: FunctionalTerm[T2]): Term = ex1(t2)

Introducing the extra parameter X seems to cause the problem. I can define the following in the REPL:

def ex3[T1 <: Term, FunctionalTerm[T1] <: X, X <: Term](t1: FunctionalTerm[T1]): Term = sys.error("TODO: ex3")

But attempting to subsequently define:

def ex4[T2 <: Term, FunctionalTerm[T2] <: X, X <: Term](t2: FunctionalTerm[T2]): Term = ex3(t2)

gives the error:

error: inferred type arguments [T2,FunctionalTerm,Nothing] do not conform to method ex3's type parameter bounds [T1 <: Term,FunctionalTerm[T1] <: X,X <: Term]
       def ex4[T2 <: Term, FunctionalTerm[T2] <: X, X <: Term](t2: FunctionalTerm[T2]): Term = ex3(t2)
                                                                                               ^
error: type mismatch;
 found   : FunctionalTerm[T2]
 required: FunctionalTerm[T1]
       def ex4[T2 <: Term, FunctionalTerm[T2] <: X, X <: Term](t2: FunctionalTerm[T2]): Term = ex3(t2)
                                                                                                   ^

So, I guess the question becomes: Why does the parameter X unused in the signature have this effect?

Answer 1

I'm not sure whether or not you're experiencing a bug, but I am pretty sure you're making your life a lot more difficult that it needs to be. You can rely on covariance and unification to do all the hard work for you,

scala> trait Term
defined trait Term

scala> case class FunctionalTerm[+T <: Term](t: T) extends Term
defined class FunctionalTerm

scala> def ex1[T <: Term](t1 : FunctionalTerm[T], s : T) : T = s
ex1: [T <: Term](t1: FunctionalTerm[T], s: T)T

scala> class A extends Term ; class B extends A ; class C extends A
defined class A
defined class B
defined class C
scala> ex1(new FunctionalTerm(new B), new C)
res0: A = C@4ceeb514

Note the inferred result type (which is equivalent to the R of your original more complex definition) ... it's A which is the LUB of B and C.

Now the flipped version is trivial and Just Works,

scala> def ex2[T <: Term](s : T, t1 : FunctionalTerm[T]) : T = s
ex2: [T <: Term](s: T, t1: FunctionalTerm[T])T

scala> ex2(new C, new FunctionalTerm(new B))
res1: A = C@522ddcec 

Answer 2

I'm going to simplify your example (I'm using 2.9.1):

scala> trait Term; case class FunctionalTerm[+T <: Term](t: T) extends Term;
defined trait Term
defined class FunctionalTerm

scala> def ex1[T1 <: Term, T3 <: X, FunctionalTerm[T1] <: X, X <: R, R <: Term](t1: FunctionalTerm[T1], s: T3): R = sys.error("TODO")
ex1: [T1 <: Term, T3 <: X, FunctionalTerm[T1] <: X, X <: R, R <: Term](t1: FunctionalTerm[T1], s: T3)R

Now declaring the second method:

scala> def ex2[T2 <: Term, T3 <: X, FunctionalTerm[T2] <: X, X <: R, R <: Term](s: T3, t2: FunctionalTerm[T2]): R = ex1(t2, s)
<console>:11: error: inferred type arguments [T2,T3,FunctionalTerm,T3,T3] do not conform to method ex1's type parameter bounds [T1 <: Term,T3 <: X,FunctionalTerm[T1] <: X,X <: R,R <: Term]
       def ex2[T2 <: Term, T3 <: X, FunctionalTerm[T2] <: X, X <: R, R <: Term](s: T3, t2: FunctionalTerm[T2]): R = ex1(t2, s)
                                                                                                                    ^

The suspicious thing (to me) is the inferred types [T2,T3,FunctionalTerm,T3,T3] - in particular FunctionalTerm. FunctionalTerm is a type constructor * -> *but the method expects a type * in this position.

I would say that this is (presumably) a bug and hence you should submit it to the scala-user mailing list (before raising a ticket) - Adriaan Moors and Miles Sabin are much more likely to have a detailed answer as to whether I'm right.