8

我有一个关于 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]

并根据我的树定义定义了一个 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？

谢谢！


在迪迪埃德的评论之后修订

如果我理解正确，声明

 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 顺便提到了这个解决方案，但这似乎是我想要的方式。请让我知道你在想什么！

4

2 回答 2

6

从推断开始就有问题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 有两个（您定义的别名 Pair 不算数），因此它无法工作。

我试图指出的是，如果没有这样的规则，编译器对于C. 如果我知道(String, Int)是 a C[String]，并且我必须猜测是什么C，那么我会认为C[X]是(X, Int)。当您编写if passed (String, Int), won't if infer (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也存在同样的问题，即它不会推断您写的时候是什么，而不会出现在哪里。这就是协方差发挥作用的地方，省去了 Leaf 中的参数 C，因此需要推断它。Paircase class PairCLeaf(2)C

于 2011-12-03T19:46:36.727 回答
3

我想到的唯一变化是对Pair论点进行注释。其他人我肯定会有其他想法。

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)    
}
于 2011-12-03T19:00:52.810 回答