Scala Type-Inference cho Type Constructor

Question

Tôi có một câu hỏi liên quan đến loại-inferencing trên Scala's type-constructors. Tôi đang chạy Scala 2.9.1 ...

Giả sử tôi định nghĩa Tree:

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] 

Và định nghĩa một BinaryTree dựa trên định nghĩa Cây của tôi:

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

bây giờ tôi có thể định nghĩa một BinaryTree số nguyên như vậy:

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

Vấn đề với điều này là tôi phải cung cấp thông số loại bất cứ khi nào tôi vào stantiate Node.

Vì vậy, nếu làm được điều này:

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

tôi nhận được lỗi:

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

Có cách nào tôi có thể ép buộc kiểu trình kiểm tra vì vậy mà tôi không cần phải cung cấp một cách rõ ràng các loại Node?

Cảm ơn!

---

Revised Sau didierd Bình luận của

Nếu tôi hiểu một cách chính xác, báo cáo kết quả

type Pair[A] = (A, A) 

trong câu hỏi ban đầu của tôi không hoạt động kể từ khi tuyên bố Cặp này chỉ là cú pháp đường đối với một hàm tạo kiểu Tuple2 (yêu cầu hai kiểu tham số). Điều này làm cho trình sắp xếp không thành công.

Nếu tôi khai báo lớp Cặp của riêng mình (như didierd gợi ý trong câu trả lời của mình), tôi thành công trong việc đưa Cây hoạt động chính xác.

// Assume same Tree/Leaf/Node definition given above 
case class MyPair[A](_1: A, _2: A) 
type BinaryTree[A] = Tree[MyPair, A] 

Sau đó, tôi có thể làm điều này ...

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

Tôi biết didierd đề cập giải pháp này trong đi qua, nhưng điều này dường như cư xử theo cách tôi muốn. Xin vui lòng cho tôi biết những gì bạn nghĩ!

Answer 1

Có sự cố khi bắt đầu bằng cách suy ra C[X] = (X,X). Giả sử bạn vượt qua (String, String) đâu đó trình biên dịch hy vọng C[String] và phải suy C, C[X] có thể (X, X), (X, String), (String, X) hoặc thậm chí (String, String) với X phantom.

Sau khi khai báo bí danh Pair sẽ không hữu ích.Tôi tin rằng bạn sẽ phải tuyên bố case class Pair[A](_1: A, _2: A) - được cấp, phỏng đoán C[X] = Pair[String] và X phantom vẫn có thể thực hiện được, nhưng may thay, trình biên dịch không thực hiện điều đó.

Tuy nhiên, khi bạn viết Tree(1, Pair(Leaf(2), Leaf(3)), nó sẽ không suy ra số C trong Lá. Tôi không chắc lắm tại sao. Nhưng dù sao, không có cách nào nó có thể suy ra nó khi bạn chỉ cần viết val l = Leaf(2).

Tôi nghĩ rằng bạn có thể nhận được một cái gì đó bằng cách làm tất cả mọi thứ hiệp biến

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] 

với hiệp phương sai, bạn loại bỏ C từ lá, vì vậy nó không cần phải được suy ra

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

Một bên nhận xét, sẽ nó không có ý nghĩa hơn để có

case object Empty extends Tree[Nothing, Nothing] 

hơn Leaf. Với Leaf, có hình dạng của cây nhị phân mà bạn không thể nhận được.

---

Cập nhật về ý kiến ​​của bạn:

Đầu tiên đừng bận tâm quá nhiều với các loại ma, tôi không nên đề cập đến nó. Nếu bạn định nghĩa một loại T[X] và X không xuất hiện theo cách khác trong định nghĩa T, nó được gọi là kiểu ma. Mã thông minh có thể được viết với điều đó để đảm bảo rằng một số thuộc tính được chứng minh tại thời gian biên dịch, nhưng đây không phải là điểm ở đây. Trên thực tế, khi trình biên dịch scala được đưa ra một số kiểu T và X, và phải suy luận C, sao cho C [X] là (một siêu kiểu) T - trong ví dụ của tôi, đó là T = (T =(). String, String) và X = String - nó sẽ chỉ hoạt động nếu T (hoặc supertype) là một parametrization của một kiểu với chính xác một tham số kiểu. Nói chung, nhiều tham số kiểu như tham số kiểu C có. Khi C có một và Tuple2 có hai (bạn đã xác định một cặp bí danh không tính), nó không thể hoạt động.

Điều tôi cố gắng chỉ ra là, nếu không có quy tắc như vậy, trình biên dịch sẽ có nhiều sự lựa chọn cho C. Nếu tôi biết (String, Int) là C[String] và tôi phải đoán xem C là gì, thì tôi nghĩ rằng C[X] là (X, Int). Khi bạn viết nếu được thông qua (Chuỗi, Int), sẽ không nếu suy luận (Bất kỳ, Bất kỳ), sẽ không có ý nghĩa, vì nó đang cố gắng suy ra một hàm tạo kiểu. Câu trả lời phải là C[X] = something with X (ngoại trừ khả năng X là phantom). Hoàn toàn khác biệt sẽ có Pair[X] = (String, Int) và phải suy ra X. Sau đó, thực sự, nó sẽ suy ra X = Any. Vì vậy, cho C [String] = (String, String), C [X] = (X, String) là một giải pháp như C [X] = (X, X).

On bình luận thứ hai của bạn về List, nó là vấn đề tương tự mà cũng tồn tại với Pair một khi bạn đã xác định case class Pair (đoạn thứ ba trong câu trả lời ở trên), mà cụ thể là nó sẽ không suy C là gì khi bạn viết Leaf(2), nơi C không xuất hiện. Đây là nơi hiệp phương sai bắt đầu, phân phối với tham số C trong Leaf, và do đó cần phải suy ra nó.

Answer 2

Biến thể duy nhất xảy ra với tôi là chú thích đối số Pair thay thế. Những người khác tôi chắc chắn sẽ có những ý tưởng khác.

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