Covarianza en la programación de nivel de tipo

Question

Estoy intentando crear tipos Tuple equivalentes a los de la biblioteca Scala, solo con un método: + que amplía una Tuple en una Tuple añadiendo el N + 1er valor, por lo tanto que voy a ser capaz de construir tuplas de forma recursiva:

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

Esto compila, pero tan pronto como me descomentar la definición de tupla # a continuación, me sale:

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 

¿Por qué? ¿Puede proporcionar una solución alternativa que me permita construir Tuples (de tipos de valores mixtos y de tipo seguro) recursivamente?

Gracias.

Answer 1

Usted podría hacer lo que hace la marca Harrah en 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) 
} 

Es decir, no tienen un miembro de tipo para el siguiente tipo. Puede haber cosas que no puede hacer como esto ... notará que up's HList is not covariant for this reason.

Me encantaría que alguien pudiera señalar una forma general de hacer que los miembros del tipo sean covariantes. Me temo que la razón por la que no se está por encima de la cabeza, aunque podría tener algo que ver con esta frase de Martin Oderksy's paper:

miembros de valor siempre se comportan covariantly; un miembro de tipo se vuelve invariante como tan pronto como se concrete. Esto está relacionado con el hecho de que Scalina no admite la vinculación tardía para miembros de tipo.

Aunque si alguien podría explicar esa frase me estaría encantado;)

---

Editar: Aquí hay otro enfoque que está más cerca de lo que usted pidió originalmente. En escribiéndolo, me di cuenta de que no estoy seguro de si esto realmente hará lo que usted desea ... ¿Podría dar un ejemplo de cómo piensa utilizar estas tuplas?

Puesto que no podemos tener miembros de tipo covariantes, podemos poner el "siguiente tupla" lógica en un rasgo separado:

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

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

Y entonces implícitamente convertir a la misma:

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) 

Esta es una técnica general que he encontrado útil: Scala no se queja si convierte implícitamente un tipo de covariante a un tipo invariante.

Este continuación, le permite hacer 2 cosas por encima de lo que podría hacer con tuplas regulares:

1) Construir una tupla manualmente en pasos, y preservar la información del tipo:

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

2) Construir una tupla de forma dinámica y, por desgracia, perder la información del 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) 

Lo que realmente hubiera gustado hacer sería tener por escrito

trait Add { 
    type N[T] <% Add 

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

Es decir, garantizar que después de la adición de 1 elemento, el resultado puede entonces tener más cosas añadidas a la misma; de lo contrario, no podríamos construir tuplas dinámicamente. Desafortunadamente, Scala no acepta límites de vista en los miembros de tipo. Afortunadamente, un límite de vista de no es más que un método que realiza la conversión; entonces todo lo que tenemos que hacer es especificar manualmente el método; por lo tanto, nextAdd.

Esto puede no ser lo que está buscando, pero tal vez le dará algunas ideas cómo acercarse a su objetivo real.

Answer 2

¿Necesita que sus tuplas tengan la misma clase base? si no, entonces no se requiere la repetición y es posible que también acaba de proxeneta tuplas de 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

El HList en shapeless es totalmente covariante y soporta la conversión a los tipos de tuplas correspondientes.

El problema que tenía (variables de tipo covariantes que aparecen en una posición contravariante) se evita en general mediante "variación de succión": los elementos HList ADT básicos se definen mínimamente, de forma similar a como lo hizo Owen en la parte superior respuesta, y las definiciones que necesitan usar las variables de tipo de forma contravariante se agregan a través de una conversión implícita.

La operación tupling es proporcionado por un mecanismo ortogonal: el tipo tupla resultante se calcula en el nivel de tipo usando una combinación de las definiciones de clase tipo implícitos (en efecto, una functional dependency) y los tipos de método dependientes (a fin de utilizar -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)