CODEWITHSUNDEEP
scalatype-level-computation
Markus Appel
Markus Appel

Reputation: 3238

Type mismatch for typesafe vectors implementation

I am trying to implement typelevel vectors. It all worked well until I tried to implement the function add, which is meant to add two vectors (of same dimensions).

This is what I have so far:

object Vector {

  type Vector1[A] = Ex[A, Vector0[A]]

  def of[A](a1: A): Vector1[A] = Ex(Vector0[A](), a1)

  type Vector2[A] = Ex[A, Vector1[A]]

  def of[A](a1: A, a2: A): Vector2[A] = of(a1).ex(a2)

  type Vector3[A] = Ex[A, Vector2[A]]

  def of[A](a1: A, a2: A, a3: A): Vector3[A] = of(a1, a2).ex(a3)

}

trait Vector[A] {

  type Same[B] <: Vector[B]
  type Self <: Vector[A]

  def ex(a: A): Vector[A]

  def add(that: Self): Self

  def map[B](f: A => B): Same[B]

  def forEach(f: A => Unit): Unit
}

case class Vector0[A]() extends Vector[A] {

  type Same[B] = Vector0[B]
  type Self = Vector0[A]

  def ex(that: A): Ex[A, Self] = Ex[A, Self](this, that)

  def add(that: Self): Self = Vector0[A]()

  def map[B](f: A => B): Same[B] = Vector0[B]()

  def forEach(f: A => Unit): Unit = ()
}

case class Ex[A, V <: Vector[A]](v: V, a: A) extends Vector[A] {

  type Same[B] = Ex[B, V#Same[B]]
  type Self = Ex[A, V]

  def ex(that: A): Ex[A, Self] = Ex[A, Self](this, that)

  def add(that: Self)(implicit num: Numeric[A]): Self = Ex[A, V](v.add(that.v), num.plus(a, that.a))

  def map[B](f: A => B): Same[B] = Ex[B, V#Same[B]](v.map(f), f(a))

  def forEach(f: A => Unit): Unit = {
    v.forEach(f)
    f(a)
  }
}

This is more code than might be necessary for solving the problem, but it might be helpful for any discussion.

Now, take a look at add in Ex ("ex" stands for "extrude", e.g. adding one more dimension to a vector).

I get the following compile error:

[error]  found   : that.v.type (with underlying type V)
[error]  required: Ex.this.v.Self
[error]   def add(that: Self)(implicit num: Numeric[A]): Self = Ex[A, V](v.add(that.v), num.plus(a, that.a))
                                                                                    ^

This does not make sense to me, as both v and that.v are guaranteed to be of type V.

I am using mill with Scala 2.13.0-M5.

What am I missing?

Upvotes: 0

Views: 83

Answers (1)

Tim
Tim

Reputation: 27356

The problem is that the type Self in Vector is abstract and is only defined for a non-abstract subclass of Vector. You can have values of type Vector but the compiler cannot know the type of Self for that value. Therefore you cannot call add on that value because it is impossible to check that the argument is the right type (because the type is unknown).

In your Ex class the value v is type V <: Vector[A] which means it could be Vector[A]. But add is not defined for Vector[A] because Self is not defined, so the compiler complains when you try to call v.add.

Here is a simplified example:

 trait A {
   type Self // Abstract type
   def add(a: Self, b: Self): Self
 }

 case class A1() extends A {
   type Self = Int // Concrete type
   def add(a: Int, b: Int) = a + b
 }

 case class A2() extends A {
   type Self = String // Concrete type
   def add(a: String, b: String) = a + b
 }

 val a1 = new A1
 val a2 = new A2

 a1.add(1, 1) // Argument type is Int

 a2.add("A", "B") // Argument type is String

This all works fine because the types are known. But now make a value of type A and call add on that:

 val a: A = a1
 a.add(1, 1) // fails to compile
 a.add("A", "B") // fails to compile

This does not compile, because you have lost the type information for Self because in A it is abstract.

Put simply, you can't call a method whose arguments are declared to be abstract types.

Upvotes: 1

Related Questions