Scala Type-Inference For Type Constructor

Question

I have a question regarding type-inferencing on Scala's type-constructors. I'm running Scala 2.9.1...

Suppose I defined Tree:

 sealed trait Tree[C[_], A]
 case class Leaf[C[_], A](a: A) extends Tree[C, A]
 case class Node[C[_], A](a: A, c: C[Tree[C, A]]) extends Tree[C, A]

And defined a BinaryTree based upon my Tree definition:

 type Pair[A] = (A, A)
 type BinaryTree[A] = Tree[Pair, A]

I can now define a BinaryTree of integers as such:

 val tree: BinaryTree[Int] = Node[Pair, Int](1, (Leaf(2), Leaf(3)))

The problem with this is that I have to supply the type parameters whenever I instantiate Node.

So if do this:

 val tree: BinaryTree[Int] = Node(1, (Leaf(2), Leaf(3)))

I get the error:

error: no type parameters for method apply: (a: A, c: C[Tree[C,A]])Node[C,A] in 
object Node exist so that it can be applied to arguments (Int, (Leaf[Pair,Int], Leaf[Pair,Int]))
 --- because ---
 argument expression's type is not compatible with formal parameter type;
 found   : (Leaf[Pair,Int], Leaf[Pair,Int])
 required: ?C[Tree[?C,?A]]
   val tree: BinaryTree[Int] = Node(1, (Leaf(2), Leaf(3)))
                               ^

Is there any way I can coerce the type-checker so that I don't have to explicitly supply the types of Node?

Thanks!

---

Revised After didierd's Comments

If I'm understanding correctly, the statement

 type Pair[A] = (A, A)

in my original question doesn't work since this Pair declaration is just syntactic sugar for a Tuple2 type-constructor (which requires two type-parameters). This causes the type-inferencer to fail.

If I declare my own Pair class (as didierd suggests in his answer), I'm successful in getting the Tree to work correctly.

// Assume same Tree/Leaf/Node definition given above
case class MyPair[A](_1: A, _2: A)
type BinaryTree[A] = Tree[MyPair, A]

Then I can do this...

scala> val t: BinaryTree[Int] = Leaf(3)
t: BinaryTree[Int] = Leaf(3)

scala> val t2: BinaryTree[Int] = Node(1, MyPair(Leaf(2), Leaf(3)))
t2: BinaryTree[Int] = Node(1,MyPair(Leaf(2),Leaf(3)))

I know didierd mentioned this solution in passing, but this seems to behave the way I want. Please let me know what you think!

Answer 1

There is a problem to start with with inferring C[X] = (X,X). Suppose you pass (String, String) somewhere the compiler expects C[String] and must infer C, C[X] could be (X, X), (X, String), (String, X) or even (String, String) with X phantom.

Having declared an alias Pair does not help. I believe you will have to declare case class Pair[A](_1: A, _2: A) - granted, inferring C[X] = Pair[String] and X phantom would still be possible, but fortunately, the compiler does not do that.

Still, when you write Tree(1, Pair(Leaf(2), Leaf(3)), it will not infer the C in Leaves. I am not very sure why. But anyway, there is no way it could infer it when you simply write val l = Leaf(2).

I think you can get to something by making everything covariant

sealed trait Tree[+C[+X], +A]
case class Leaf[+A](a: A) extends Tree[Nothing, A]
case class Node[+C[+X], +A](a: A, c: C[Tree[C,A]]) extends Tree[C,A]

with covariance, you remove C from Leaf, so it need not be inferred

case class Pair[+A](left: A, right: A)

val tree = Node(1, Pair(Leaf(2), Node(3, Pair(Leaf(3), Leaf(4)))))
tree: Node[Pair,Int] = Node(1,Pair(Leaf(2),Node(3,Pair(Leaf(3),Leaf(4)))))

A side remark, would it not make more sense to have

case object Empty extends Tree[Nothing, Nothing]

rather than Leaf. With Leaf, there are shapes of binary tree that you cannot get.

---

Update regarding your comments:

First do not bother too much with the phantom type, I should not have mentioned it. If you define a type T[X] and X does not appear otherwise in the definition of T, it is called a phantom type. Clever code may be written with that to ensure that some properties are proved at compile time, but this is not the point here.

As a matter of fact, when the scala compiler is given some types T and X, and must infer C, such that C[X] is (a supertype of) T - in my example, that was T = (String, String) and X = String - it will work only if T (or a supertype) is an parametrization of a type with exactly one type parameter. More generally, as many type parameters as the type parameter C has. As C has one and Tuple2 has two (your having defined an alias Pair does not count), it cannot work.

What I tried to point was that, without such a rule, the compiler would have many choices for C. If I know (String, Int) is a C[String], and that I must guess what C is, then I would think C[X] is (X, Int). When you write if passed (String, Int), wouldn't if infer (Any, Any), it does not make sense, given that it is trying to infer a type constructor. The answer must be C[X] = something with X (except for the possibility that X is phantom). Completely different would be having Pair[X] = (String, Int) and having to infer X. Then indeed, it would infer X = Any. So given C[String] = (String, String), C[X] = (X, String) is as much a solution as C[X] = (X,X) is.

On your second comment regarding List, it is the same problem that also exists with Pair once you have defined case class Pair (third paragraph in the answer above), namely that it will not infer what C is when you write Leaf(2), where C does not appear. This is where covariance kicks in, dispensing with the parameter C in Leaf, and so the need to infer it.

Answer 2

The only variation that occurred to me was to annotate the Pair argument instead. Other people I'm sure will have other ideas.

object BinaryTreeTest {
  sealed trait Tree[C[_], A]
  case class Leaf[C[_], A](a: A) extends Tree[C, A]
  case class Node[C[_], A](a: A, c: C[Tree[C, A]]) extends Tree[C, A]

  type Pair[A] = (A, A)
  type BinaryTree[A] = Tree[Pair, A]

  val p: Pair[Tree[Pair, Int]] = (Leaf(2), Leaf(3))    
  val t: BinaryTree[Int] = Node(1, p)    
}