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]

そして、私の 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か?

ありがとう！


ディディアードのコメント後に改訂

私が正しく理解していれば、ステートメント

 type Pair[A] = (A, A)

私の最初の質問では、この Pair 宣言は Tuple2 型コンストラクター (2 つの型パラメーターを必要とする) の単なる構文糖衣であるため、機能しません。これにより、型推論が失敗します。

独自の Pair クラスを宣言すると (ディディアードの回答で示唆されているように)、ツリーを正しく機能させることに成功します。

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

ディディアードがこの解決策について言及したことは知っていますが、これは私が望むように動作するようです。あなたの考えを教えてください！

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ファントムは引き続き可能ですが、幸いなことに、コンパイラはそれを行いません。

それでも、あなたが書いたとき、それはin LeavesTree(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)))))

余談ですが、持っているほうが意味がありませんか

case object Empty extends Tree[Nothing, Nothing]

ではなくLeaf。ではLeaf、得られない二分木の形があります。

コメントに関する更新:

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

実際のところ、scala コンパイラーがいくつかの型 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と考えるでしょう。if passed (String, Int), would't if infer (Any, Any)と書くと、型コンストラクターを推論しようとしているので意味がありません。答えは(X がファントムである可能性を除いて) でなければなりません。を持っていることと、 を推論しなければならないことは、完全に異なります。それから確かに、それは推測するでしょう. したがって、C[String] = (String, String) を考えると、C[X] = (X, String) は C[X] = (X,X) と同じくらい多くのソリューションです。C[X](X, Int)C[X] = something with XPair[X] = (String, Int)XX = Any

に関する2番目のコメントでは、定義した後（上記の回答の3番目の段落）にも存在する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 に答える