Kowariancja w programowaniu na poziomie typu

Question

Próbuję utworzyć typy typu Tuple równoważne z tymi w bibliotece Scala, tylko z metodą: +, która rozszerza Tuple na Tuple, dodając wartość N + 1 - tak że będę w stanie skonstruować krotek rekurencyjnie:

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

kompiluje to, ale jak tylko odkomentowaniu definicji krotki # Next, otrzymuję:

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 

Dlaczego tak jest? Czy możesz podać obejście, które pozwoli mi rekursywnie budować krotki (mieszane typy wartości bezpiecznych)?

Dzięki.

Answer 1

Można robić to, co robi Mark Harrah w 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) 
} 

Oznacza to, że nie ma elementu typu dla następnego typu. Mogą być rzeczy, których nie możesz zrobić, jak to ... zauważysz, że up's HList is not covariant for this reason.

Bardzo bym mi się spodobał, gdyby ktoś mógł wskazać ogólny sposób, aby typ kowariantki typu . Obawiam się, że powodem, dla którego nie jest ponad moją głową, choć może to mieć coś wspólnego z tym zdaniu z Martin Oderksy's paper:

członkowie Wartość zawsze zachowywać covariantly; element typu staje się niezmienny jako wkrótce, gdy zostanie wykonany jako konkretny. Jest to związane z faktem, że Scalina nie przyjmuje późnego wiązania dla członków typu.

Chociaż jeśli ktoś mógłby wyjaśnić mi to zdanie byłbym zachwycony;) ​​

---

Edycja: Oto kolejny podejście, które jest bliżej do tego, co pierwotnie prosiłem. Na pisząc to zdałem sobie sprawę, nie jestem pewien, czy to naprawdę zrobi to, co chcesz ... może możesz podać przykład, w jaki sposób zamierzasz używać tych krotek?

Ponieważ nie możemy mieć kowariantna członków typ, możemy umieścić „obok krotki” logikę do osobnego cechy:

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

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

A potem niejawnie przekonwertować do niego:

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) 

Jest to ogólna technika, którą uznałem za użyteczną: Scala nie uskarża się, jeśli użytkownik niejawnie przekształca typ kowariantny w typ niezmienniczy.

To wtedy pozwala zrobić 2 rzeczy ponad to, co można zrobić z regularnych krotek:

1) Budowanie krotki ręcznie w krokach i zachować informacje typu:

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

2) zbudować krotka dynamicznie i, niestety, tracą informacje typu:

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) 

Co naprawdę wolałby zrobić byłoby napisane

trait Add { 
    type N[T] <% Add 

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

Oznacza to, upewnić się, że po dodaniu 1 elementu, wynik może wtedy mieć więcej rzeczy dodaje się do niej; w przeciwnym razie nie moglibyśmy dynamicznie budować krotek. Niestety, Scala nie akceptuje granic widoku na członkach typu. Na szczęście granica widoku nie jest niczym więcej jak metodą, która dokonuje konwersji; więc wszystko, co musimy zrobić, to ręcznie określić metodę; stąd nextAdd.

Może to nie jest to, czego szukasz, ale może przyniesie Ci to kilka pomysłów: , jak zbliżyć się do rzeczywistego celu.

Answer 2

Czy Twoje krotki muszą mieć tę samą klasę podstawową? Jeśli nie, to nie jest wymagane rekurencji i równie dobrze można po prostu pimp krotki 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

HList w shapeless jest w pełni kowariantna i obsługuje konwersję do odpowiednich typów krotka.

Twój problem (zmienne typu kowariancji pojawiające się w pozycji przeciwwariantowej) jest ogólnie unikany przez "odchylenie od wariancji": podstawowe elementy HList ADT są zdefiniowane minimalnie, podobnie do sposobu, w jaki Owen wykonał u góry odpowiedź, a definicje, które wymagają niestosownego użycia zmiennych typu, są dodawane poprzez niejawną konwersję.

Operacja tupling jest ortogonalnym mechanizmu: wynikowa krotka jest obliczane na poziomie typu stosując połączenie definicji ukrytych klasy typu (w efekcie functional dependency) i zależnymi od rodzaju metoda (więc używać -Ydependent-method-types lub 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)