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

Question

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

假设我定义了树:

 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 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 在他的回答中建议的那样)，我就成功地让树正常工作。

// 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)) 时，它不会推断出 Leaves 中的 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，有一些你无法得到的二叉树的形状。

<小时/>

关于您的评论的更新:

首先不要太在意幻像类型，我不应该提到它。如果定义类型 T[X] 并且 X 没有出现在 T 的定义中，则称为幻像类型。可以用它编写聪明的代码，以确保某些属性在编译时得到证明，但这不是这里的重点。

事实上，当 scala 编译器被赋予一些类型 T 和 X 时，并且必须推断 C，这样 C[X] 是 T(的父类(super class)型) - 在我的示例中，即 T = (String , String) 且 X = String - 仅当 T (或父类(super class)型)是仅具有一个类型参数的类型的参数化时，它才有效。更一般地说，类型参数的数量与类型参数 C 的数量一样多。由于 C 有一个而 Tuple2 有两个(您定义的别名对不算)，因此它无法工作。

我试图指出的是，如果没有这样的规则，编译器将为C提供多种选择。如果我知道 (String, Int) 是 C[String]，并且我必须猜测 C 是什么，那么我会认为 C[X]是(X, Int)。当您编写 if pass (String, Int), won't if infer (Any, Any) 时，它没有意义，因为它试图推断类型构造函数。答案一定是C[X] =带有X的东西(除了X可能是幻影的可能性)。完全不同的是拥有 Pair[X] = (String, Int) 并必须推断 X。那么确实，它会推断出X = Any。因此，给定 C[String] = (String, String)，C[X] = (X, String) 与 C[X] = (X,X) 一样是一个解决方案。

关于您关于List的第二条评论，一旦您定义了case class Pair(第三个)，Pair也存在同样的问题上面答案中的段落)，即当您编写 Leaf(2) 时，它不会推断出 C 是什么，其中 C 不出现。这就是协方差发挥作用的地方，省去了 Leaf 中的参数 C，因此不需要推断它。