Ковариантность в программировании на уровне типов

Question

Я пытаюсь создать типы Tuple, эквивалентные типам в библиотеке Scala, только с помощью метода: +, который расширяет Tuple до Tuple путем добавления значения N + 1st - так, чтобы я мог построить кортежи рекурсивно:

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

Это компилируется, но как только я раскомментирую определение Tuple # Next, я получаю:

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

Почему это? Можете ли вы предоставить обходной путь, который позволил бы мне рекурсивно создавать кортежи (смешанных типов значений, безопасных для типов)?

Спасибо.

Answer 1

HList in shapeless является полностью ковариантным и поддерживает преобразование в соответствующие типы кортежей.

Проблема, с которой вы столкнулись (переменные ковариантного типа, появляющиеся в контравариантной позиции), в общем, устраняется путем "отклонения от нормы": базовые элементы HList ADT определяются минимально, подобно тому, как это делал Оуэн в верхней части своего ответа. и определения, которые должны использовать переменные типа контравариантно, добавляются посредством неявного преобразования.

Операция кортежа обеспечивается с помощью ортогонального механизма: результирующий тип кортежа вычисляется на уровне типа с использованием комбинации неявных определений классов типов (в действительности это функциональная зависимость ) и зависимых типов методов (так используйте -Ydependent-method-types или 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)

Answer 2

Вы можете сделать то, что Марк Харра делает в 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)
}

То есть, нет члена типа для следующего типа. Там могут быть вещи, которые вы не можете сделать, как это ... вы заметите, что HList up не является ковариантным по этой причине .

Мне бы очень хотелось, чтобы кто-то мог указать общий способ сделать тип члены ковариантны. Я боюсь, что причина, почему они не находятся над моей головой, хотя это может как-то связано с этим предложением из статьи Мартина Одеркси :

Значение членов всегда вести себя ковариантно; член типа становится инвариантным как как только это будет сделано бетоном. Это связано с тем, что Скалина не допускает позднего связывания для членов типа.

Хотя, если бы кто-то мог объяснить мне это предложение, я был бы рад;)

---

Редактировать: вот еще один подход, который ближе к тому, что вы изначально просили. На написав это, я понял, что не уверен, что это действительно будет делать то, что вы хотите ... может быть, вы могли бы привести пример того, как вы собираетесь использовать эти кортежи?

Поскольку у нас не может быть ковариантных членов типа, мы можем поместить логику "следующего кортежа" в отдельную черту:

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

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

А затем неявно преобразовать в него:

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)

Это общая техника, которую я нашел полезной: Скала не жалуется, если вы неявно преобразуйте ковариантный тип в инвариантный тип.

Это позволяет вам сделать на 2 вещи больше, чем вы могли бы делать с обычными кортежами:

1) Построить пошаговый кортеж вручную и сохранить информацию о типе:

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

2) Динамически создать кортеж и, к сожалению, потерять информацию о типе:

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)

Что мы действительно хотели бы сделать было бы написано

trait Add {
    type N[T] <% Add

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

То есть убедитесь, что после добавления 1 элемента результат может иметь больше вещи, добавленные к этому; иначе мы не могли бы динамически создавать кортежи. К сожалению, Scala не принимает границы просмотра для членов типа. К счастью, граница представления - не более чем метод, который выполняет преобразование; так что все мы нужно вручную указать метод; следовательно nextAdd.

Это может быть не то, что вы ищете, но, возможно, это даст вам некоторые идеи как приблизиться к своей цели.