Size Parameterization in Scala

Question

Is there anyway to parametrize a type via a value in scala? For example, to parametrize a matrix with it's size so something like...

val m1 = new Matrix[2,3]()
val m2 = new Matrix[5,1]()

val m3 = m1 multiply m2

would fail to compile because the you can't multiply a [2,3] matrix by a [5,1]?

This would also be useful in implementing other types such as Tuples, or Vectors. Does anyone know of a way to achieve this?

Answer 1

Using Peano numbers we can define types that all are natural numbers starting from 0. Here they are all subtypes of Nat but _1 and _2 are distinct types, so they can't be used in place of each other without variance.

Define natural numbers:

scala> sealed trait Nat
defined trait Nat

scala> sealed trait _0 extends Nat
defined trait _0

scala> sealed trait Succ[N <: Nat] extends Nat
defined trait Succ

scala> type _1 = Succ[_0]
defined type alias _1

scala> type _2 = Succ[_1]
defined type alias _2

The Matrix is invariant in its parameter types:

scala> case class Matrix[A <: Nat, B <: Nat](ignoreThis: String)
defined class Matrix

The multiplication function is also invariant:

scala> def multiply[R1 <: Nat, C1 <: Nat, C2 <: Nat](m1: Matrix[R1, C1], m2: Matrix[C1, C2]) = Matrix[R1, C2](m1.ignoreThis + m2.ignoreThis)
multiply: [R1 <: Nat, C1 <: Nat, C2 <: Nat](m1: Matrix[R1,C1], m2: Matrix[C1,C2])Matrix[R1,C2]

Compiler will do the checks for you, dimensions match:

scala> multiply(Matrix[_1, _2]("one"), Matrix[_2, _1]("two"))
res0: Matrix[_1,_1] = Matrix(onetwo)

dimensions don't match, compile time error is much better than runtime:

scala> multiply(Matrix[_1, _2]("one"), Matrix[_1, _1]("two"))
<console>:19: error: type mismatch;
 found   : Matrix[_1(in object $iw),_2]
    (which expands to)  Matrix[Succ[_0],Succ[Succ[_0]]]
 required: Matrix[_1(in object $iw),Succ[_ >: _0 with _1(in object $iw) <: Nat]]
    (which expands to)  Matrix[Succ[_0],Succ[_ >: _0 with Succ[_0] <: Nat]]
Note: _2 <: Succ[_ >: _0 with _1 <: Nat], but class Matrix is invariant in type B.
You may wish to define B as +B instead. (SLS 4.5)
       multiply(Matrix[_1, _2]("one"), Matrix[_1, _1]("two"))
                              ^
<console>:19: error: type mismatch;
 found   : Matrix[_1(in object $iw),_1(in object $iw)]
    (which expands to)  Matrix[Succ[_0],Succ[_0]]
 required: Matrix[Succ[_ >: _0 with _1(in object $iw) <: Nat],_1(in object $iw)]
    (which expands to)  Matrix[Succ[_ >: _0 with Succ[_0] <: Nat],Succ[_0]]
Note: _1 <: Succ[_ >: _0 with _1 <: Nat], but class Matrix is invariant in type A.
You may wish to define A as +A instead. (SLS 4.5)
       multiply(Matrix[_1, _2]("one"), Matrix[_1, _1]("two"))
                                                     ^

I was too lazy to write actual multiplication implementation hence ignoreThis placeholder.