類型構造器的Scala類型推斷

我有一個關於Scala類型構造器上的類型推理的問題。我跑斯卡拉2.9.1 ...類型構造器的Scala類型推斷

假設我定義的樹：根據我的樹定義

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

這個問題是，我必須提供類型參數，只要我在stantiate 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)

在我原來的問題沒有工作，因爲這對聲明只是語法糖對於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提到順便這個解決方案，但這種行爲似乎與我想要的方式。請讓我知道你在想什麼！

來源

2011-12-03 shj

關於您的修改代碼：它更類似於@David的解決方案。類型不是完全推斷的，你必須將表達式顯式地鍵入爲BinaryTree [Int]。我認爲這很合理。協變解決方案避免了這種情況，但它帶有一個價格：協方差大多是一件好事，它限制了班級可以做什麼。特別是，它只適用於類型C是協變量。 –

從推斷C[X] = (X,X)開始有個問題。假設你通過(String, String)地方編譯器期望C[String]，必須推斷C，C[X]可能是(X, X)，(X, String)，(String, X)甚至與X幻影(String, String)。

聲明別名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]

與協方差得到的東西，你從葉刪除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)))))

A面的話，將它沒有更多意義了

case object Empty extends Tree[Nothing, Nothing]

而不是Leaf。與Leaf，有二叉樹的形狀，你不能得到。

更新關於你的評論：

先不要打擾太多與幻影型，我不應該提到它。如果您定義類型T[X]而X在T的定義中沒有出現，則稱爲幻像類型。可以編寫聰明的代碼以確保在編譯時證明某些屬性，但這不是重點。事實上，當scala編譯器被賦予某些類型T和X，並且必須推斷C，使得C [X]是（超類型的）T--在我的例子中，那就是T =（字符串，字符串）和X =字符串 - 只有當T（或超類型）是隻有一個類型參數的類型的參數化時，它才能工作。更一般地說，與類型參數C一樣多的類型參數。由於C有一個而Tuple2有兩個（你定義了一個別名Pair不算），所以它不能工作。

我試圖指出的是，沒有這樣的規則，編譯器會有很多選擇C。如果我知道(String, Int)是C[String]，並且我必須猜出C是什麼，那麼我會認爲C[X]是(X, Int)。當你寫如果通過（字符串，INT），不會推斷（任何，任何），它沒有任何意義，因爲它試圖推斷一個類型的構造函數。答案必須是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，因此需要推斷它。

來源

2011-12-03 19:46:36

第一段我有點困惑。 X是幻影是什麼意思？如果我通過（字符串，字符串）編譯器期望C [字符串]，它不會推斷它（String，String）？如果我傳遞（String，Int），它不會推斷（Any，Any）嗎？ – shj

另外，如果我使用List而不是我的類型別名Pair，我會得到類似的錯誤。既然列表是同質的，它不應該能夠推斷出類型？非常感謝你的幫助！ – shj

更新回覆您的評論。 –

發生在我身上的唯一變化是反而註釋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-03 19:00:52 david

類型構造器的Scala類型推斷

回答

相關問題