Constrain function based on origin (Path Dependent type? Type Generation?)

Question

Sorry about terrible title, not sure of a better one. Here's a gross simplification of my problem (Sorry if it seems so trivial, that it's pointless):

class RList[T](data: List[T]) {
   def map[V](f: T=>V): RList[V] = ...
}

The idea of an RList (Restricted List) is that you can't resize it, or change the order of the elements in it. But you can use functions that give you a new RList with changed data in it.

Now there needs to be a function that creates RLists. It might have a signature something like:

def toRList[T](values: List[T]): RList[T] = ...

So far, so good. But now the tricky part. I need a function that works like this:

def zip[T, V](left: RList[T], right: RList[V]): RList[(T,V)]

But with the additional constraint that left and right have the same origin. Thus, they are guaranteed to be the same size.

e.g. Code that should compile:

val x = toRList(List(1, 2, 3))
val y = x.map(_ * 2)
val z = y.map(_.toString)
zip(y,z)

e.g. Code that should fail to compile

val y = toRList(List(2, 4, 6))
val z = toRList(List("one", "two"))
zip(y,z)

*Note: In my original problem the constraint on zip needs to be that they are from the same 'source'. Merely guaranteeing they are the same length isn't good enough (Not to mention, the size of the list isn't known at compile time) *

I also need to be able to use zip multiple times, so something like this should compile

zip(a,zip(b,c))

(assuming a, b and c are from the same source)

Thanks!

Answer 1

One of the disadvantages of making RList an inner trait of a producer is that it becomes less pleasant to write methods or functions with RList arguments outside of the producer—you end up with a lot of this:

def foo[P <: RListProducer, T](rl: P#RList[T]) = ???

An alternative is to give RList a type member that will be unique for each "source" RList, but that each source will pass on to its "children". Something like this:

trait RList[T] { outer =>
  type S
  protected val wrapped: List[T]

  def map[V](f: T => V) = new RList[V] {
    type S = outer.S
    protected val wrapped = outer.wrapped.map(f)
  }

  def zip[V](r: RList[V] { type S = outer.S }) = new RList[(T, V)] {
    type S = outer.S
    protected val wrapped = outer.wrapped.zip(r.wrapped)
  }
}

object RList {
  def toRList[T](ts: List[T]) = new RList[T] {
    type S = this.type
    protected val wrapped = ts
  }
}

Now assume we have the following:

val a = RList.toRList(1 :: 2 :: 3 :: Nil)
val b = a.map(_.toString)
val c = RList.toRList("1" :: "2" :: "3" :: Nil)

Now a zip b (or a zip b zip a zip a, etc.) will compile, but if you throw in a c you'll get a compiler error.

---

Note: I'd originally written zip as follows:

def zip[V](r: RList[V])(implicit ev: r.S =:= S) = new RList[(T, V)] { ... }

This gives a slightly nicer compiler error message, but if you're working pre-2.10 it requires turning on dependent method types with -Ydependent-method-types.

Answer 2

Does this work for you?

object PathDependentTypes {
  trait RListProducer {
    trait RList[T] {
      def map[V](f: T => V): RList[V]
      def zip[V](r: RList[V]) : RList[(T, V)]
    }
    def getList[T]: RList[T] = ???
  }

  class A extends RListProducer

  def main(args: Array[String]) {
    val aSource = new A
    val a = aSource.getList[Int]
    val anotherSource = new A
    val b = anotherSource.getList[String]

    val m1 = a.map( _ * 2)
    val m2 = a.map( _.toString)

    val z1 = m1.zip(m2)
    //val z2 = a.zip(b) //doesn't compile because A and B aren't the same.
    val z3 : A#RList[(Int, (Int, String))] = a zip (m1 zip m2)
  }
}