Tipo-Inferenza Scala Tipo Costruttore

Question

Ho una domanda riguardante l'inferenza di tipo sui costruttori di tipi di Scala. Io corro Scala 2.9.1 ...

Supponiamo che io definito Albero:

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] 

e definito un BinaryTree basata sulla mia definizione Albero:

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

Ora posso definire un BinaryTree di interi quanto tali:

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

Il problema è che ho per fornire i parametri di tipo ogni volta che in stantiate Node.

Quindi, se fare questo:

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

ottengo l'errore:

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'è un modo per costringere il tipo ortografico in modo che io non devo fornire esplicitamente il tipi di Node?

Grazie!

---

revisione previa Commenti di didierd

Se ho la comprensione correttamente, la dichiarazione

type Pair[A] = (A, A) 

nella mia domanda iniziale non funziona in quanto questa dichiarazione Pair è solo zucchero sintattico per un costruttore di tipi Tuple2 (che richiede due parametri di tipo). Ciò causa il fallimento del tipo-inferneratore.

Se io dichiaro la mia classe di coppia (come didierd suggerisce nella sua risposta), io sono riuscita a ottenere l'Albero per funzionare correttamente.

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

Allora posso fare questo ...

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

So didierd menzionato questa soluzione di passaggio, ma questo sembra a comportarsi nel modo desiderato. Per favore fatemi sapere cosa ne pensate!

Answer 1

c'è un problema per cominciare con inferire C[X] = (X,X). Supponiamo che si passa (String, String) da qualche parte il compilatore si aspetta C[String] e deve dedurre C, C[X] potrebbe essere (X, X), (X, String), (String, X) o anche (String, String) con X fantasma.

Dopo aver dichiarato un alias Pair non aiuta.Credo che dovrai dichiarare case class Pair[A](_1: A, _2: A) - concesso, dedurre C[X] = Pair[String] e X il fantoccio sarebbe ancora possibile, ma fortunatamente, il compilatore non lo fa.

Tuttavia, quando si scrive Tree(1, Pair(Leaf(2), Leaf(3)), non si deduce lo C in Foglie. Non sono molto sicuro del perché. Ma comunque, non c'è modo di poterlo dedurre quando scrivi semplicemente val l = Leaf(2).

Penso che si possa arrivare a qualcosa, rendendo tutto covariante

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] 

con covarianza, si rimuove C da Leaf, quindi non deve essere dedotta

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

Un'osservazione lato, sarebbe non avere più senso di avere

case object Empty extends Tree[Nothing, Nothing] 

piuttosto che Leaf. Con Leaf, ci sono forme dell'albero binario che non puoi ottenere.

---

Aggiornamento quanto riguarda i vostri commenti:

Prima non si preoccupano troppo con il tipo di fantasma, non avrei parlato. Se si definisce un tipo T[X] e X non viene visualizzato diversamente nella definizione di T, viene chiamato un tipo di fantasma. Il codice intelligente può essere scritto con questo per garantire che alcune proprietà siano provate in fase di compilazione, ma questo non è il punto qui.

Di fatto, quando al compilatore di scala vengono dati alcuni tipi T e X, e si deve inferire C, tale che C [X] è (un supertipo di) T - nel mio esempio, che era T = (String, String) e X = String - funzionerà solo se T (o un supertipo) è una parametrizzazione di un tipo con esattamente un parametro di tipo. Più in generale, come molti parametri di tipo del parametro di tipo C. Dato che C ha uno e Tuple2 ne ha due (il tuo aver definito un alias Coppia non conta), non può funzionare.

Quello che ho cercato di indicare era che, senza una tale regola, il compilatore avrebbe molte scelte per C. Se so che (String, Int) è un C[String], e che devo indovinare cosa è C, allora penso che C[X] sia (X, Int). Quando si scrive se passato (String, Int), non lo sarebbe se inferire (Qualsiasi, Qualsiasi), non ha senso, dato che sta cercando di dedurre un costruttore di tipi. La risposta deve essere C[X] = something with X (eccetto per la possibilità che X sia fantasma). Completamente diverso sarebbe avere Pair[X] = (String, Int) e dover dedurre X. Quindi, in effetti, dedurrebbe X = Any. Quindi dato C [String] = (String, String), C [X] = (X, String) è tanto una soluzione quanto C [X] = (X, X).

Sul tuo secondo commento per quanto riguarda List, è lo stesso problema che esiste anche con Pair una volta che avete definito case class Pair (terzo comma, nella risposta precedente), vale a dire che non dedurre cosa C è quando si scrive Leaf(2), dove C non appare. È qui che entra in gioco la covarianza, che rinuncia al parametro C di Leaf, e quindi alla necessità di dedurlo.

Answer 2

L'unica variazione che si è verificato a me è stato quello di annotare l'argomento Pair invece. Altre persone sono sicuro che avranno altre idee.

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