型レベルで自然数を足し算してみよう

## はじめに

先週末に[shapeless勉強会](http://connpass.com/event/27049/)に行ってきました。

どの発表もレベルが高かったことは言うまでもありません。

私の理解できる範囲で要約するならば、implicit で loop という謎の言葉が交わされる勉強会でした。

この記事は、型レベルで計算することに慣れていない初学者向けのものです。

私自身理解が浅いこともあり、間違いなどあるかもしれません。

コメントなどで指摘していただけると幸いです。

## 関数を定義してみる

まずは、関数を定義してみます。

``` scala
scala> def tokyo(s: String): String = s
tokyo: (s: String)String
```

この関数はパラメータリストに String 型を1つ受け取って、String　型の戻り値を返します。

これは String 型の値を受け取って、String 型の値を返す単純な関数です。

呼び出し元はこのようになります。

``` scala
scala> tokyo("one")
res0: String = one
```

## 型パラメータを使って関数を定義してみる

次に、型パラメータを使った関数を定義してみます。

``` scala
scala> def tokyo[T](t: T): T = t
tokyo: [T](t: T)T
```

これは任意の型の値を受け取って、受け取った型の値を返す単純な関数です。

呼び出し元はこのようになります。

``` scala
scala> tokyo("one")
res0: String = one

scala> tokyo(10)
res1: Int = 10
```

## 型レベルの関数を定義してみる

型レベルの関数を定義してみます。

``` scala
scala> type Id[T] = T
defined type alias Id
```

これは任意の型を受け取って、受け取った型を返す関数です。

呼び出し元はこのようになります。

``` scala
scala> def tokyo(s: Id[String]): Id[String] = s
tokyo: (s: String)String

scala> tokyo("one")
res3: String = one
```

Scala では`:`の後ろや角括弧の内側などに型を指定します。

この型レベルの関数は型を返すので、`:`の後ろや角括弧の内側などで使います。

## 型レベルの定数を定義してみる

次に、型レベルの定数を定義してみます。

``` scala
type Const[C] = { type Lambda[T] = C }
```

ちょっと発想の転換が必要かもしれません。

`f(x) = C(定数)`が理解の助けになるかもしれません。

呼び出し元はこのようになります。

``` scala
scala> def tokyo(s: Const[String]#Lambda[_]): Const[String]#Lambda[_] = s
tokyo: (s: String[])String[]
```

`#`は`.`みたいなもので、内部の型を使うのに使います。

## 型レベルで自然数の足し算を定義してみる

こちらを参照しました。

link: [Scalaで型レベル"だけ"でクイックソート](http://postd.cc/typelevel-quicksort-in-scala/)

``` scala
sealed trait Nat
final class _0 extends Nat
final class Succ[P <: Nat]() extends Nat

type _1 = Succ[_0]
type _2 = Succ[_1]
type _3 = Succ[_2]
type _4 = Succ[_3]
type _5 = Succ[_4]

trait Sum[A <: Nat, B <: Nat] { type Out <: Nat }
 
object Sum {
  def apply[A <: Nat, B <: Nat](implicit sum: Sum[A, B]): Aux[A, B, sum.Out] = sum
 
  type Aux[A <: Nat, B <: Nat, C <: Nat] = Sum[A, B] { type Out = C }
 
  implicit def sum1[B <: Nat]: Aux[_0, B, B] = new Sum[_0, B] {
    type Out = B
  }
 
  implicit def sum2[A <: Nat, B <: Nat](implicit sum : Sum[A, Succ[B]]): Aux[Succ[A], B, sum.Out] = new Sum[Succ[A], B] {
    type Out = sum.Out
  }
}
```

`Magnet Pattern`と`Aux Pattern`を知っておく理解が深まります。

link: [Scala2.10.0のDependent method typesと型クラスを組み合わせた『The Magnet Pattern』がヤバい件](http://yuroyoro.hatenablog.com/entry/2013/01/23/192244)
link: [The Aux Pattern](http://gigiigig.github.io/posts/2015/09/13/aux-pattern.html)

今回は implicit で loop のトリックだけにせまってみたいと思いますので、`Magnet Pattern`と`Aux Pattern`については割愛します。

呼び出し元はこのようになります。

``` scala
scala> Sum[_0, _3]
res0: Sum[_0,Succ[Succ[Succ[_0]]]]{type Out = Succ[Succ[Succ[_0]]]} = Sum$$anon$1@1292acd4

scala> Sum[_5, _1]
res1: Sum[Succ[Succ[Succ[Succ[Succ[_0]]]]],Succ[_0]]{type Out = Succ[Succ[Succ[Succ[Succ[Succ[_0]]]]]]} = Sum$$anon$2@8c7e762
```

### Sum[_0, _1]の呼び出しをトレース

まず、`Sum[_0, _1]`の呼び出しをトレースしてみます。

``` scala
scala> Sum[_0, _1]
res2: Sum[_0,Succ[_0]]{type Out = Succ[_0]} = Sum$$anon$1@27f125fa
```

型パラメータ`A`に_0、型パラメータ`B`に_1を指定して`Sum#apply`メソッドを呼び出しています。

なので、implicitパラメータリストのところで`Sum[_0, _1]`のインスタンスが供給されます。

これは`sum1`によって供給されます。

多分、こんな感じで供給されるのだと思います。

``` scala
scala> Sum.sum1[_1]
res3: Sum.Aux[_0,_1,_1] = Sum$$anon$1@365782b4
```

戻り値は供給された`Sum[_0, _1]`のインスタンスです。

また、その戻り値の型は`Sum[_0,Succ[_0]] { type Out = Succ[_0] }`です。

途中式は`Aux[_0, _1, _1] = Sum[_0, _1] { type Out = _1 } = Sum[_0,Succ[_0]] { type Out = Succ[_0] }`のようになります。

### Sum[_1, _0]の呼び出しをトレース

次に、`Sum[_1, _0]`の呼び出しをトレースしてみます。

``` scala
scala> Sum[_1, _0]
res4: Sum[Succ[_0],_0]{type Out = Succ[_0]} = Sum$$anon$2@6ec619dd
```

型パラメータ`A`に_1、型パラメータ`B`に_0を指定して`Sum#apply`メソッドを呼び出しています。

なので、implicitパラメータリストのところで`Sum[_1, _0]`のインスタンスが供給されます。

これは`sum2`によって供給されます。

多分、こんな感じで供給されるのだと思います。

``` scala
scala> Sum.sum2[_0, _0]
res5: Sum[Succ[_0],_0]{type Out = Succ[_0]} = Sum$$anon$2@3802fe21
```

`sum2`によって`Sum[_1, _0]`のインスタンスが供給されるためには、型パラメータ`A`に_0、型パラメータ`B`に_0を指定して`Sum#sum2`メソッドを呼び出したと考えられます。

なので、`sum2`のimplicitパラメータリストのところで`Sum[_0, Succ[_0]]`のインスタンスが供給されます。

先ほど確認したやつとほとんど同じ型ですね。

戻り値は供給された`Sum[_1, _0]`のインスタンスです。

また、その戻り値の型は`Sum[Succ[_0],_0] { type Out = Succ[_0] }`です。

注目したいのは`type Out = sum.Out`のところです。

これは供給された`Sum[_0, Succ[_0]]`のインスタンスを経由したOut型です。

### Sum[_3, _1]の呼び出しをトレース

最後に、implicit で loop にせまってみたいと思います。

`Sum[_3, _1]`の呼び出しをトレースしてみます。

``` scala
scala> Sum[_3, _1]
res6: Sum[Succ[Succ[Succ[_0]]],Succ[_0]]{type Out = Succ[Succ[Succ[Succ[_0]]]]} = Sum$$anon$2@a44f6e7
```

型パラメータ`A`に_3、型パラメータ`B`に_1を指定して`Sum#apply`メソッドを呼び出しています。

なので、implicitパラメータリストのところで`Sum[_3, _1]`のインスタンスが供給されます。

これは`sum2`によって供給されます。

多分、こんな感じで供給されるのだと思います。

``` scala
scala> Sum.sum2[_2, _1]
res7: Sum[Succ[Succ[Succ[_0]]],Succ[_0]]{type Out = Succ[Succ[Succ[Succ[_0]]]]} = Sum$$anon$2@392c1f9
```

`sum2`によって`Sum[_3, _1]`のインスタンスが供給されるためには、型パラメータ`A`に_2、型パラメータ`B`に_1を指定して`Sum#sum2`メソッドを呼び出したと考えられます。

なので、`sum2`のimplicitパラメータリストのところで`Sum[_2, Succ[_1]]`のインスタンスが供給されます。

これは`sum2`によって供給されます。

`sum2`によって`Sum[_2, Succ[_1]]`のインスタンスが供給されるためには、型パラメータ`A`に_1、型パラメータ`B`にSucc[_1]を指定して`Sum#sum2`メソッドを呼び出したと考えられます。

なので、`sum2`のimplicitパラメータリストのところで`Sum[_1, Succ[Succ[_1]]]`のインスタンスが供給されます。

これは`sum2`によって供給されます。

`sum2`によって`Sum[_1, Succ[Succ[_1]]]`のインスタンスが供給されるためには、型パラメータ`A`に_0、型パラメータ`B`にSucc[Succ[_1]]を指定して`Sum#sum2`メソッドを呼び出したと考えられます。

なので、`sum2`のimplicitパラメータリストのところで`Sum[_0, Succ[Succ[Succ[_1]]]]`のインスタンスが供給されます。

これは`sum1`によって供給されます。

ここでOut型が`Succ[Succ[Succ[Succ[_0]]]]`のように決まります。

## まとめ

implicit で loop のトリックですが、implicitパラメータリストがないimplicit defを loop の終了条件にして、implicitパラメータリストがあるimplicit defで型レベルの処理を繰り返すというものでした。

型レベルの処理の結果はOut型です。

## 参照URL

- [First-class polymorphic function values in shapeless (1 of 3) — Function values in Scala - Miles Sabin](http://milessabin.com/blog/2012/04/27/shapeless-polymorphic-function-values-1/)
- [First-class polymorphic function values in shapeless (2 of 3) — Natural Transformations in Scala - Miles Sabin](http://milessabin.com/blog/2012/05/10/shapeless-polymorphic-function-values-2/)
- [shapeless_study - Twitter検索](https://twitter.com/search?f=tweets&vertical=default&q=shapeless_study&src=typd)