Covarianza nella programmazione a livello di tipo

Question

Sto cercando di creare tipi Tuple equivalenti a quelli della libreria Scala, solo con un metodo: + che estende una tupla in una tupla aggiungendo il valore N + 1st - quindi che sarò in grado di costruire tuple in modo ricorsivo:

class Test { 
    abstract class Tuple { 
    //protected type Next[_] <: Tuple 
    //def :+[T](p: T): Next[T] 
    } 

    case class Tuple0() extends Tuple { 
    protected type Next[T] = Tuple1[T] 
    def :+[T](p: T): Next[T] = Tuple1(p) 
    } 

    case class Tuple1[+T1](p1: T1) extends Tuple { 
    protected type Next[T] = Tuple2[T1, T] 
    def :+[T](p: T): Next[T] = Tuple2(p1, p) 
    } 

    case class Tuple2[+T1, +T2](p1: T1, p2: T2) extends Tuple { 
    protected type Next[-T] = Nothing 
    def :+[T](p: T): Next[T] = throw new IndexOutOfBoundsException(); 
    } 
} 

Questo compila, ma non appena ho Rimuovere il commento la definizione di tuple # Avanti, ottengo:

Test.scala:13: error: covariant type T1 occurs in invariant position in type [T]Test.this.Tuple2[T1,T] of type Next 
    protected type Next[T] = Tuple2[T1, T] 
        ^
one error found 

Perché? Potete fornire una soluzione alternativa che mi consenta di creare tuple (di tipi di valori misti, sicuri per tipo) in modo ricorsivo?

Grazie.

Answer 1

si potrebbe fare quello che Mark Harrah fa in up:

sealed trait HList 

case class HCons[+H, +T <: HList](head: H, tail: T) extends HList 
{ 
    def :+:[T](v : T) = HCons(v, this) 
} 

case object HNil extends HList 
{ 
    def :+:[T](v : T) = HCons(v, this) 
} 

Cioè, non hanno un membro di tipo per il tipo successivo. Potrebbero esserci cose che non puoi fare come ... noterai che up's HList is not covariant for this reason.

Mi piacerebbe davvero che qualcuno indicasse un modo generale per rendere covariante il tipo di membro . Temo che la ragione per cui non sono è al di sopra la mia testa, anche se potrebbe avere qualcosa a che fare con questa frase da Martin Oderksy's paper:

membri di valore si comportano sempre covariantly; un membro del tipo diventa invariato come appena viene reso concreto. Ciò è dovuto al fatto che Scalina non ammette il late-binding per i membri di tipo.

Anche se qualcuno potrebbe spiegare quella frase mi sarei felice;)

---

Edit: Ecco un altro approccio che è più vicino a quello che originariamente chiesto. Su scrivendolo ho capito che non sono sicuro se questo farà veramente quello che vuoi ... magari potresti dare un esempio di come intendi usare queste tuple?

Dal momento che non siamo in grado di avere membri di tipo covarianti, possiamo mettere la "prossima tupla" logica in un tratto a parte:

trait Add { 
    type N[T] 
    type Add2[T] <: Add 

    def add[T](x: T): N[T] 
    def nextAdd[T](n: N[T]): Add2[T] 
} 

E poi convertire implicitamente ad esso:

class Tuple0Add extends Add { 
    type N[T1] = T1 
    type Add2[T1] = Tuple1Add[T1] 

    def add[T1](x: T1) = x 
    def nextAdd[T1](n: T1) = new Tuple1Add(n) 
} 
implicit def tuple0Add(t0: Unit) = new Tuple0Add 

class Tuple1Add[T1](t1: T1) extends Add { 
    type N[T2] = (T1, T2) 
    type Add2[T2] = Nothing 

    def add[T2](x: T2) = (t1, x) 
    def nextAdd[T2](n: (T1,T2)) = sys.error("Can't go this far") 
} 
implicit def tuple1Add[T1](t1: T1) = new Tuple1Add(t1) 

Questa è una tecnica generale che ho trovato utile: Scala non si lamenta se si converte implicitamente un tipo covariante in un tipo invariante .

Questo quindi permette di fare 2 cose di cui sopra che cosa si potrebbe fare con le tuple regolari:

1) costruire manualmente una tupla in passi, e conservare le informazioni sul tipo:

> val a =() add 1 add 2 
> a._1 
1 
> a._2 
2 

2) Costruire un tupla in modo dinamico e, purtroppo, perdere le informazioni sul tipo:

def addAll(a: Add, s: List[_]): Any = s match { 
    case Nil => a 
    case x::Nil => a add x 
    case x::xs => addAll(a.nextAdd(a add x), xs) 
} 

> addAll((), List(1, 2)) 
(1, 2) 

Quello che veramente sarebbe piaciuto fare sarebbe quello di avere scritto

trait Add { 
    type N[T] <% Add 

    def add[T](x: T): N[T] 
} 

Cioè, affinché dopo l'aggiunta di 1 elemento, il risultato può avere più cose aggiunte ad esso; altrimenti non potremmo costruire tuple dinamicamente. Sfortunatamente, Scala non accetta i limiti di vista sui membri del tipo. Fortunatamente, una vista associata a non è altro che un metodo che esegue la conversione; quindi tutto ciò che dobbiamo fare è specificare manualmente il metodo; quindi nextAdd.

Questo potrebbe non essere quello che stai cercando, ma forse ti darà alcune idee come avvicinarti al tuo obiettivo attuale.

Answer 2

Avete bisogno che le vostre tuple abbiano la stessa classe base? se non allora non ricorsione è richiesto e si potrebbe anche solo magnaccia tuple di Scala:

object PimpedTuples { 
    implicit def pimpAny[A](a: A) = new { 
     def :+[B](b: B): (A, B) = (a, b) 
    } 

    implicit def pimpTuple2[A, B](t: (A, B)) = new { 
     def :+[C](c: C): (A, B, C) = (t._1, t._2, c) 
    } 

    // etc 
} 

Answer 3

Il HList in shapeless è pienamente covariant e supporta la conversione di tipi tuple corrispondenti.

Il problema si doveva (variabili di tipo covariante che appare in posizione controvariante) è evitato, in generale, per "sfruttamento della prostituzione via varianza": gli elementi ADT di base HList sono definite in minima parte, in modo simile al modo in cui Owen ha fatto nella parte superiore del suo risposta, e le definizioni che necessitano di utilizzare le variabili di tipo in modo contravariante vengono aggiunte tramite una conversione implicita.

L'operazione tupling è fornita da un meccanismo ortogonale: il tipo tupla risultante viene calcolata a livello di tipo utilizzando una combinazione di definizioni implicite tipo classe (in effetti un functional dependency) e tipi Metodo dipendenti (usa -Ydependent-method-types o Scala 2.10- SNAPSHOT),

// Minimal base HList ADT elements 
sealed trait HList 

final case class HCons[+H, +T <: HList](head : H, tail : T) extends HList { 
    def ::[U](h : U) : U :: H :: T = HCons(h, this) 
} 

trait HNil extends HList { 
    def ::[H](h : H) = HCons(h, this) 
} 

case object HNil extends HNil 

type ::[+H, +T <: HList] = HCons[H, T] 

// Separate 'Ops` trait allows the HList type L to be used independently 
// of variance. 
final class HListOps[L <: HList](l : L) { 
    // More definitions elided ... 

    def tupled(implicit tupler : Tupler[L]) : tupler.Out = tupler(l) 
} 

// Implicitly pimp away the variance 
implicit def hlistOps[L <: HList](l : L) = new HListOps(l) 

// Type class representing a type-level function from the HList type to 
// the corresponding tuple type 
trait Tupler[L <: HList] { 
    type Out <: Product 
    def apply(l : L) : Out 
} 

// Type class instances for Tupler 
object Tupler { 
    implicit def hlistTupler1[A] = new Tupler[A :: HNil] { 
    type Out = Tuple1[A] 
    def apply(l : A :: HNil) = Tuple1(l.head) 
    } 

    implicit def hlistTupler2[A, B] = new Tupler[A :: B :: HNil] { 
    type Out = (A, B) 
    def apply(l : A :: B :: HNil) = (l.head, l.tail.head) 
    } 

    // Add more instances for higher arities here ... 
} 

val t1 = (1 :: HNil).tupled   // type inferred as Tuple1[Int] 
val t2 = (1 :: "foo" :: HNil).tupled // type inferred as (Int, String)