类型构造函数的Scala类型推断

Question

我有一个关于Scala的类型构造函数的类型推理的问题.我正在运行Scala 2.9.1 ...

假设我定义了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]

并根据我的Tree定义定义了BinaryTree:

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

我现在可以定义一个BinaryTree整数:

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

这个问题是我必须在实例化时提供类型参数Node.

所以,如果这样做:

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

我收到错误:

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

有什么方法可以强制类型检查器,以便我不必明确提供类型Node？

谢谢!

---

修改后的didierd的评论

如果我理解正确,声明

 type Pair[A] = (A, A)

在我的原始问题中不起作用,因为这个Pair声明只是Tuple2类型构造函数的语法糖(需要两个类型参数).这会导致类型推断器失败.

如果我声明我自己的Pair类(正如didierd在他的回答中建议的那样),我成功地让Tree正常工作.

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

然后我可以这样做......

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

我知道didierd顺便提到了这个解决方案,但这似乎表达了我想要的方式.请让我知道你在想什么!

Answer 1

推断有一个问题C[X] = (X,X).假设你通过(String, String)某个编译器期望C[String],必须推断C,C[X]可能是(X, X),(X, String),(String, X)甚至(String, String)与X幻影.

宣布别名后Pair没有用.我相信你必须声明case class Pair[A](_1: A, _2: A)- 授予,推断C[X] = Pair[String]和X幻像仍然是可能的,但幸运的是,编译器不这样做.

但是,当你写作时Tree(1, Pair(Leaf(2), Leaf(3)),它不会推断出C叶子.我不太清楚为什么.但无论如何,当你简单地写作时,它无法推断它val l = Leaf(2).

我认为你可以通过使一切协变来达到目的

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]

使用协方差,从Leaf中删除C,因此无需推断

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

一个侧面的评论,是不是更有意义

case object Empty extends Tree[Nothing, Nothing]

而不是Leaf.有了Leaf,你可以得到二进制树的形状.

关于您的意见的更新:

首先不要用幻影类型打扰太多,我不应该提到它.如果您定义了一个类型T[X],X并且在T的定义中没有出现,则称为幻像类型.可以使用它编写聪明的代码,以确保在编译时证明某些属性,但这不是重点.

事实上,当scala编译器给出一些类型T和X,并且必须推断C,这样C [X]是(超类型)T - 在我的例子中,那就是T =(String,String)和X = String - 仅当T(或超类型)是具有一个类型参数的类型的参数化时,它才有效.更一般地,与类型参数C一样多的类型参数.由于C有一个,而Tuple2有两个(你已经定义了一个别名对不计),它无法工作.

我试图指出的是,如果没有这样的规则,编译器会有很多选择C.如果我知道(String, Int)是一个C[String],我必须猜测是什么C,那么我认为C[X]是(X, Int).当你写if if(String,Int)时,如果推断(Any,Any)则不会,它没有意义,因为它试图推断一个类型构造函数.答案必须是C[X] = something with X(除了X是幽灵的可能性).完全不同将有Pair[X] = (String, Int)和不得不推断X.确实,它会推断X = Any.因此,给定C [String] =(String,String),C [X] =(X,String)与C [X] =(X,X)一样是一个解决方案.

关于你的第二个评论List,Pair一旦你定义了case class Pair(上面的答案中的第三段),它也存在同样的问题,即它不会推断你什么C时候写Leaf(2),哪里C没有出现.这是协方差开始的地方,省去了Leaf中的参数C,因此需要推断它.