型コンストラクタの型推論

Question

私はScalaの型コンストラクタの型推論に関する質問があります。

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

私は今BinaryTreeを定義することができます：私のツリーの定義に基づいてBinaryTreeを

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] 

と定義される：私はツリーを定義したと仮定し

Scalaの2.9.1を...実行していますよのような整数の：

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

私はタイプパラメータを入力する必要がありますstantiate Node。これを行う場合

だから：

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

私は明示的に供給する必要がないように、私は型チェッカを強制することができますどのような方法があります：

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

私はエラーを取得しますNodeの種類？

ありがとうございます！私が正しく理解していた場合didierdのコメント

後改訂

---

このペア宣言は単なる糖衣構文であることから、文の私の元の質問で

type Pair[A] = (A, A) 

は動作しません。 Tuple2型コンストラクタ（これには2つの型パラメータが必要です）。これにより、型推論が失敗します。

私が自分のペアクラスを宣言した場合（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)を推測すると問題があります。あなたはどこかにコンパイラがC[String]を期待してCを推測しなければならない、C[X]は(X, X)、(X, String)、(String, X)あるいは(String, String)Xファントムとなる可能性が(String, String)を渡したとします。

エイリアスを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] 

すべてのものを作ることによって何かを得ることができ、それは

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

側の発言を推論する必要はありませんので、あなたは、葉からCを削除すると思います持っているほうが意味がありません

case object Empty extends Tree[Nothing, Nothing] 

Leafではなく、 Leafでは、取得できないバイナリツリーの形があります。あなたのコメントについて

---

更新：

まずファントムタイプとあまり気にしない、私はそれを言及していないはずです。タイプT[X]とXを定義すると、Tの定義に他には現れませんが、それはファントムタイプと呼ばれます。コンパイル時にいくつかのプロパティが証明されることを保証するために、賢明なコードを書くことができますが、これはここでのポイントではありません。

実例として、スカラーコンパイラにいくつかの型TとXが与えられ、C [X]がTのスーパー型であるようにCを推論しなければならないとしたら、T =（ String、String）とX = String - T（またはスーパータイプ）が、型パラメータが1つの型のパラメータ化である場合にのみ機能します。より一般的には、型パラメータCと同じ数の型パラメータがあります。 Cには1つがあり、Tuple2には2つの名前が付いています（Pairはカウントされません）。

私が指摘しようとしたことは、このようなルールがなければ、コンパイラにはCの多くの選択肢があるということでした。私が(String, Int)がC[String]であり、私はCが何であるか推測しなければならないと知っていれば、C[X]は(X, Int)だと思います。 （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に関する2番目のコメントに

、それはどこ、あなたはそれはあなたがLeaf(2)を書くときCが何であるかを推測しないであろう、すなわちこと、（上記の回答では第三段落）case class Pairを定義した後もPairに存在する同じ問題ですCは表示されません。これは、共分散が始まるところで、LeafのパラメータCを無視して、それを推論する必要があります。

Answer 2

唯一の変形は、代わりに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)  
}