shapeless で型安全に行列の積を計算する

 
この記事では、Scala のジェネリックプログラミングライブラリ shapeless を使ってベクトルや行列を表現して、**型安全**に和や積を計算してみる。

## はじめに
以前受けていたオンラインの機械学習講座で、プログラミング課題[^octave]を試行錯誤しながら解いていく中で、行列の積の計算でサイズが合わない場合に発生する実行時エラーがとても面倒だった。

本来は、どのようなサイズの（つまり何行×何列の）行列同士で積が成立するかは、結果の行列のサイズとともに計算する前から分かっていることなので、ふだん型のある言語をメインに使っているプログラマとしては、やはりコンパイル時に検出させて**型安全**を実現してみたくなる。

ただし、そのためには型にサイズ情報を含めた上で、これを計算したり、新しい型を作ったりする仕組みが必要になる。幸い Idris のような依存型言語や、Scala のような静的型付き言語で依存型をサポートするライブラリを使うと、ある程度これができるようになる。

この記事では Scala の [shapeless](https://github.com/milessabin/shapeless) で、これを試してみたい。shapeless はバージョン 2.3.3 のものを使った。動くソースは IntelliJ の Scala Worksheet を[ここ](https://gist.github.com/yasuabe/a64e9f9afae85d1f07ef4f55e4689eec)に置いた。

[^octave]: Octave という言語を使うものだった

## Idris の場合
Scala のコードを書く前に、Idris の依存型をちょっとだけ観察してみる。

Idris では固定サイズのコレクションを表現する  [Data.Vect](https://www.idris-lang.org/docs/current/base_doc/docs/Data.Vect.html) でベクトルが表せる。サイズまで型に含めることができ、3次元ベクトルを2次元ベクトルとして扱おうとしたりすると、評価する前に型の違いが検出される。

```
Idris> :module Data.Vect
*Data/Vect> :let v2 = the (Vect _ _) [3, 4]    -- リスト [3, 4] から2次元ベクトルを作成
*Data/Vect> v2
[3, 4] : Vect 2 Integer
*Data/Vect> :let v3 = the (Vect _ _) [3, 4, 5] -- リスト [3, 4, 5] から3次元ベクトルを作成
*Data/Vect> v3
[3, 4, 5] : Vect 3 Integer
*Data/Vect> the (Vect 2 Integer) v2 -- 同じ型へのキャスト; 当然成功する
[3, 4] : Vect 2 Integer
*Data/Vect> the (Vect 2 Integer) v3 -- サイズの違いが type mismatch として検出される
(input):1:5:When checking argument value to function Prelude.Basics.the:
        Type mismatch between
                Vect 3 Integer (Type of v3)
        and
                Vect 2 Integer (Expected type)

        Specifically:
                Type mismatch between
                        1
                and
                        0
```
Scala の場合、Idris の `Vect` の代わりに、shapeless で提供されている `Sized` と自然数型  `Nat` を用いて似たようなことができる。これらを型安全なベクトル／行列の計算に応用してみたい。

## ベクトル
数学をおさらいすると、ベクトルには下記のような**スカラー倍**と**和**の計算があった。

```math
\vec{a}=\binom{a}{b},\,\vec{b}=\binom{c}{d}\, に対して\\
k\vec{a}=\binom{ka}{kb}\\
\vec{a}+\vec{b} =\binom{a+c}{b+d}
```
上の例では2次元ベクトルだったが、一般化して $N$次元とするとScala + shapelessでは下記のように書ける。

```scala
type Vect[N <: Nat] = Sized[IndexedSeq[Int], N]
```
この型表現でベクトルの計算を実装してみる。

### スカラー倍
スカラー倍は以下のように書ける。

```scala
def vect = Sized.apply[IndexedSeq]

def times[L <: Nat](k: Int, v1: Vect[L]): Vect[L] = v1.map(_ * k)

times(3, vect(1, 2)) // (3, 6)
times(0, vect(1, 2)) // (0, 0)
```
標準のタプルを使って平面上の位置などを表している場合、$k$ 倍する計算が $x$ 成分、$y$ 成分で重複してしまうが、Sized では `map` が使えるので一度書くだけですむ。

### 和
ベクトルの和は以下のように書ける。ただし数学での計算と同様に、次元が同じものに限られる。

```scala
def addVect[L <: Nat](v1: Vect[L], v2: Vect[L]): Vect[L] =
  Sized.wrap[IndexedSeq[Int], L]((v1, v2).zipped.map(_ + _))
```

`v1` と `v2` の対応する各要素を足してから、`Sized` に戻している。[^sized_wrap]

実行すると以下のようになる。

```
addVect(Sized(1, 2, 3), Sized(3, 4, 5))                    // [4, 6, 8]
List(vect(10), vect(100)).fold[Vect[_1]](vect(1))(addVect) // [111]
// addVect(vect(1, 2, 3), vect(3, 4)) type mismatch
```
コメントアウトした行のように次元が異なるベクトルを加算しようとすると、**コンパイル時に失敗** する。
[^sized_wrap]: `Sized.wrap` そのものは要素数が `L` と違っていても `Sized[_, L]` にラップしてしまうが、`addVect` 内では要素数がコンパイル時に保証されているので矛盾は生じない。

## 行列
行列にも和やスカラー倍があるが、ここでは**積**に絞ってみる。まず数学のおさらいから。あえて正方行列は避けて、3行×2列と2行×4列の積を示してみた。

```math
A=\begin{pmatrix} a_{11} & a_{12}\\a_{21} & a_{22}\\a_{31} & a_{32} \end{pmatrix},\,
B=\begin{pmatrix} b_{11} &b_{12} &b_{13} &b_{14} \\b_{21} &b_{22} &b_{23} &b_{24}\end{pmatrix}\, に対して\\
A \times B = \begin{pmatrix}
a_{11}b_{11}+a_{12}b_{21} & a_{11}b_{12} + a_{12}b_{22} & a_{11}b_{13}+a_{12}b_{23} & a_{11}b_{14}+a_{12}b_{24} \\
a_{21}b_{11}+a_{22}b_{21} & a_{21}b_{12} + a_{22}b_{22} & a_{21}b_{13}+a_{22}b_{23} & a_{21}b_{14}+a_{22}b_{24} \\
a_{31}b_{11}+a_{32}b_{21} & a_{31}b_{12} + a_{32}b_{22} & a_{31}b_{13}+a_{32}b_{23} & a_{31}b_{14}+a_{32}b_{24} \\
\end{pmatrix}
```
このように、$A$ の列数と $B$ の行数が一致している必要があり、また結果のサイズは$A の行数 \times Bの列数$となる。

Scala での型表現としては、先の `Vect` を用いて下のように定義できる。

```scala
type Matrix[R <: Nat, C <: Nat] = Sized[IndexedSeq[Vect[C]], R]
```
次のようにインスタンスを作る。コメントアウトした `m3` は、サイズの異なる行が含まれているため、**コンパイルに失敗** する [^matrix] 。

```scala
def matrix = Sized.apply[IndexedSeq]

val m1: Matrix[_3, _2] =                          //[[1, 2]
  matrix(vect(1, 2), vect(3, 4), vect(5, 6))      // [3, 4]
                                                  // [5, 6]]
val m2: Matrix[_2, _4] =                          //[[ 7,  8,  9, 10]
  matrix(vect(7, 8, 9, 10), vect(11, 12, 13, 14)) // [11, 12, 13, 14]]
// val m3: Matrix[_3, _2] = matrix(vect(1, 2), vect(3, 4, 5), vect(5, 6))
```
次に、この `m1` と `m2` の積を型安全に計算してみる。

[^matrix]: 変数の型を指定しないと、インスタンスを作るだけなら最大の行サイズに合わせてコンパイルが通ってしまう。

### 積
上述のとおり積の計算は `Matrix[R, RC] × Matrix[RC, C] -> Matrix[R, C]` のような型になる。以下のように実装できる。

```scala
def multiply[R <: Nat, RC <: Nat, C <: Nat](
  m1: Matrix[R,  RC],
  m2: Matrix[RC, C]
)(implicit R: ToInt[R], C: ToInt[C]): Matrix[R, C] = m1.map(w1 =>
  Sized.wrap[IndexedSeq[Int], C](
    m2.transpose.map(w2 => (w1, w2).zipped.map(_ * _).sum))
)
```
`m2` の転置行列[^transpose]を作って、通常の行列の掛け算の手順どおり計算している。

```scala
multiply(m1, m2) // [[ 29,  32,  35,  38]
                 //  [ 65,  72,  79,  86]
                 //  [101, 112, 123, 134]]
// multiply(m2, m1) type mismatch
```

コメントアウトした `multiply(m2, m1)` では、`m2` の列数と `m1` の行数がちがうので、**コンパイル時** にエラーとなる。
[^transpose]: 行列の行と列を入れ替えたもの。

## まとめ  
やっぱ型安全ええなー