Covariance in type-level programming

Question

I'm trying to create types Tuple equivalent to the ones in the Scala library, only with a :+ method that extends a Tuple into a Tuple by addition of the N+1st value -- so that I will be able to construct Tuples recursively:

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

This compiles, but as soon as I uncomment the definition of Tuple#Next, I get:

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

Why is that? Can you provide a workaround which would allow me to build Tuples (of mixed, type-safe value types) recursively?

Thanks.

Answer 1

You could do what Mark Harrah does 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)
}

That is, don't have a type member for the next type. There may be things you can't do like this... you'll notice that up's HList is not covariant for this reason.

I would really like it if someone could point out a general way to make type members covariant. I'm afraid the reason why they are not is above my head, though it might have something to do with this sentence from Martin Oderksy's paper:

Value members always behave covariantly; a type member becomes invariant as soon as it is made concrete. This is related to the fact that Scalina does not admit late-binding for type members.

Though if someone could explain that sentence to me I would be delighted ;)

---

Edit: Here is another approach that is closer to what you originally asked for. On writing it I realized I'm not sure if this will really do what you want... maybe you could give an example of how you're intending to use these tuples?

Since we can't have covariant type members, we can put the "next tuple" logic into a separate trait:

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

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

And then implicitly convert to it:

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)

This is a general technique I have found useful: Scala doesn't complain if you implicitly convert a covariant type to an invariant type.

This then allows you to do 2 things above what you could do with regular tuples:

1) Build a tuple manually in steps, and preserve type information:

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

2) Build a tuple dynamically and, sadly, lose type information:

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)

What we really would have liked to do would be to have written

trait Add {
    type N[T] <% Add

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

That is, ensure that after adding 1 element, the result can then have more things added to it; otherwise we could not build tuples dynamically. Unfortunately, Scala does not accept view bounds on type members. Luckily, a view bound is nothing more than a method that does the conversion; so all we have to do is manually specify the method; hence nextAdd.

This may not be what you are looking for, but maybe it will give you some ideas how to get closer to your actual goal.

Answer 2

The HList in shapeless is fully covariant and supports conversion to corresponding tuple types.

The problem you had (covariant type variables appearing in contravariant position) is avoided in general by "pimping away variance": the base HList ADT elements are defined minimally, similarly to the way that Owen has done at the top of his answer, and the definitions which need to use the type variables contravariantly are added via an implicit conversion.

The tupling operation is provided by an orthogonal mechanism: the resulting tuple type is computed at the type level using a combination of implicit type class definitions (in effect a functional dependency) and dependent method types (so use -Ydependent-method-types or 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)