型安全なリストを作りたい Part. 1

最終的な目標としては、行列の計算がしたい。

  1 2 3       1 4       1*1+2*2+3*3 1*4+2*5+3*6       14 32
(       ) * ( 2 5 ) = (                         ) = (       )
  4 5 6       3 6       4*1+5*2+6*3 4*4+5*5+6*6       32 77

こんな感じのやつ。
2行3列の行列は3行2列の行列との積を求めることができて、結果は2行2列の行列になる。

もう少し一般化すると、m行n列 * n行p列 = m行p列で、 1つ目の行列の列数と2つ目の行列の行数が一致していないといけない。

これを普通にコンパイラが判定してくれるようにできればいいなという話。

ただ、全通りつくるとかはどう考えても現実的ではないので、 サイズ付きの行列を作ろうというのが主題です。

ちなみに、shapelessというライブラリにはSizedListみたいな型があるそうなので、
仕事とかですぐに必要であればそちらのソースを読んだりするべきですが、
今回は思考そのものを楽しむことが目的なので特に原典もなく間違いも気にせず進みます。

1. サイズを型で表現する。

いきなり難しいことは考えずに、とりあえずサイズ付きの集合型を考えることから始めます。
EmptyList, OneItemList, TwoItemsListのようなのがList[0], List[1]ってできればいいのですね。

まずは単純に数値0を表す型を作ってみます。

sealed trait Size
sealed trait Zero extends Size

ここまでは決め事なのでこれでいいとして、問題はこの先です。 One, Twoなんて続けていったらいつまで経っても終わりません。

そこで、ちょっと前に書いたScalaの型推論って難しいのチャーチ数を使ってみます。

final case class Succ[S <: Size]() extends Size

これで1がSucc[Zero], 2がSucc[Succ[Zero]]なんてふうに表現できるようになりませんか？
どんどん長くなっていくけどこの際気にしない。

2. サイズを型引数にもつリストを定義

これが正しく動作するのかを試すために、Listを定義してみます。
名前は標準ライブラリとかぶらないように適当につけます。

trait SizedList[S <: Size, +A] {
  def :+:[B >: A](b: B): SizedList[Succ[S], B] = new :+:(b, this)
}
case object SizedNil extends SizedList[Zero, Nothing]
case class :+:[S <: Size, A](head: A, tail: SizedList[S, A]) extends SizedList[Succ[S], A]

object SizedList {
  def empty[A]: SizedList[Zero, A] = SizedNil
}

replで動作確認。。。

scala> val a = SizedList.empty[Int]
a: SizedList[Zero,Int] = SizedNil

scala> val b = 2 :+: SizedList.empty
b: SizedList[Succ[Zero],Int] = :+:(2,SizedNil)

scala> val c = 9 :+: 1 :+: 2 :+: 4 :+: 7 :+: SizedList.empty
c: SizedList[Succ[Succ[Succ[Succ[Succ[Zero]]]]],Int] = :+:(9,:+:(1,:+:(2,:+:(4,:+:(7,SizedNil)))))

とりあえず問題なく動いてはいそうです。
まだ値を取り出すことすらできませんが。

次回予告(いつ！？)

次回はこれにheadやtailを足してみましょう。

まだ漠然としか考えていませんが、値がOrderedじゃないとソートできないとかそういうのと同じ機構を使えばできそうです。

reverseが定義できればきっとそれなりのことができるはずです。