类型级编程中的协方差

Question

我正在尝试创建类似于Scala库中的类型的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

你可以做什么马克哈拉做在了:

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

也就是说,没有下一种类型的类型成员.可能有些事你不能这样做......你会注意到由于这个原因,up的HList不是协变的.

如果有人能指出一种使类型成员协变的一般方法,我真的很喜欢它.我担心他们之所以不在我的头上,尽管这可能与Martin Oderksy的论文中的这句话有关:

价值成员总是表现得很协调; 一个类型成员一旦具体化就变得不变.这与Scalina不承认类型成员的后期绑定有关.

虽然如果有人可以向我解释这句话我会很高兴;)

编辑:这是另一种更接近你原来要求的方法.在写这篇文章时,我意识到我不确定这是否会真正做你想要的...也许你可以举例说明你打算如何使用这些元组？

由于我们不能拥有协变类型成员,我们可以将"下一元组"逻辑放入一个单独的特征:

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)

这是我发现有用的一般技术:如果你隐式地将协变类型转换为不变类型,Scala不会抱怨.

然后,这使您可以执行两项高于常规元组的操作:

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.

这可能不是你想要的,但它可能会给你一些如何更接近你的实际目标的想法.

Answer 2

的HList在不成形完全协变,并支持转化为相应的元组类型.

你所遇到的问题(协变型变量出现在逆变位置)通常是通过"拉开方差"来避免的:基本的HList ADT元素是最低限度定义的,类似于Owen在他的答案顶部所做的方式,以及需要使用类型变量的定义通过隐式转换添加.

tupling操作由正交机制提供:使用隐式类型定义(实际上是函数依赖)和依赖方法类型的组合在类型级别计算得到的元组类型(因此使用-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)