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?

This is called dependent typing, and Scala does not have it. [Shapeless](https://stackoverflow.com/questions/28287612/how-to-require-typesafe-constant-size-array-in-scala) can get you partway there. — Chris Martin, Apr 06 '16 at 03:12
In this case it does not have to be dependent (typing). You can define a hierarchy of types using Peano numbers and as long as they match your code would compile, and otherwise it won't. — yǝsʞǝla, Apr 06 '16 at 03:33

yǝsʞǝla · Accepted Answer · 2016-04-06T03:55:56.013

4

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.

edited Apr 06 '16 at 03:55

answered Apr 06 '16 at 03:48

yǝsʞǝla

16,272
2
44
65

This is pure Scala, no special libraries. I'm sure there must be more proper and complete implementations of type safe math structures and operations out there. – yǝsʞǝla Apr 06 '16 at 04:02
This is cool in showing how Scala supports the contortions needed to do this, but those error messages are... opaque. And the boilerplate needed to do Matrix[_100, _256] or something would be immense. – The Archetypal Paul Apr 06 '16 at 07:38
1

Shapeless already provides a way to avoid boilerplate with `Nat`s. See for example here: http://stackoverflow.com/questions/21296099/limits-of-nat-type-in-shapeless or here: https://github.com/milessabin/shapeless/blob/master/core/src/main/scala/shapeless/nat.scala. Also: https://github.com/fthomas/refined – yǝsʞǝla Apr 06 '16 at 08:11
I don't see what having `Succ` here buys you. Why not just have `trait _75`, `trait _124` etc? Then you can just create `Matrix[_75,_124]` without any boilerplate. – Dima Apr 06 '16 at 10:27
@Dima that would work too in this case but would limit you in other operations. You might want to take a subset of matrix and then compiler can verify the arithmetic. – yǝsʞǝla Apr 06 '16 at 11:17
1

@AlekseyIzmailov not really, it'll only validate that you have annotated the types correctly. If you choose to return a 3x5 array, and call it Matrix[_10,_12], there is nothing that prevents that fro happening. Just like in your example `Matrix[_1,_2]` is really a `String`. The fact that your types are actually Peano numbers, doesn't help anything. – Dima Apr 06 '16 at 13:41
@Dima I suggest for you to follow the links in the comments and prove to yourself that it's possible to use Nat type in that way. It's more than just a string. It's a nested type and each nesting defines next number. You can make compiler check that type you return is +1 of the type you pass. Similar thing with HLists - you know exact length of the list at compile time and when you take tail it will be length - 1 known at compile time. – yǝsʞǝla Apr 06 '16 at 14:40
@AlekseyIzmailov I know there are some tricks that can be done with shapeless. Just saying that _your_ suggestion has nothing to do with them, and doesn't actually seem to be useful at all. – Dima Apr 06 '16 at 15:50

Size Parameterization in Scala

1 Answers1