人でもわかる型推論

追記: この記事を書いてから早2年弱。今は数式のほうがわかりやすいなあと思うようになりました。

# これは何？
- この記事は、最近 Hindley Milner (Algorithm W) 型推論を理解したばかりの私が、型推論のことをなるべくわかりやすく解説するものです。
- 簡略化したOCamlのようなコードが登場します。
- わかりやすさ重視で書いていくつもりなので、専門用語(自由変数とか)はあまり出てきません。
間違いなどあったらコメントしていただけると幸いです。

# まずは単相から
ここからは図を使って説明していきます。(ビジュアルなほうがわかりやすいハズ)

## とても簡単な例
以下にとても簡単なコードを示します。
![ad_base.jpg](https://qiita-image-store.s3.amazonaws.com/0/69622/75873370-9625-b5f2-2100-333f91c2e4f6.jpeg)

見ればわかりますが、``x``の型は``int``ですね。
ですが、どのようにして``int``だとわかったのでしょうか。

![ad_01.jpg](https://qiita-image-store.s3.amazonaws.com/0/69622/b071fd66-b363-ccb5-d304-1dcae8fe602a.jpeg)


すでにわかっていることを書き出しだしてみました。リテラルの右肩を見てください。
``1``の型は当然ながら``int``、``x``の型はとりあえず``0``というidをつけておきました。このidが重要な役割を果たします。

``let x = y`` という式があったとき、``x``と``y``の型は当然ながら等しくなります。
したがって、先ほどのidが``0``の``x``の型は``int``ということになります。
以下の``T(id)``はidが``id``の変数の型を表しています。

![ad_02.jpg](https://qiita-image-store.s3.amazonaws.com/0/69622/87e30ac6-94c6-e204-0b5d-4a8b4e8961ea.jpeg)

``T(0) = int``となりました。
``print_int``の引数に``x``がありますが、``x``のidは``0``なので、``T(0) = int``より``x``の型は``int``だとわかります。

## 関数
以下の画像を見てください。

![ad_03.jpg](https://qiita-image-store.s3.amazonaws.com/0/69622/7fff9d5d-e6bc-01c3-8db4-31dc96fdc9df.jpeg)


先ほどの例よりも少し難しくなりました。先に言っておくと、``f``の型は``int -> int``、``x``は当然ながら``int``ですね。
まずは先ほどと同じようにわかることを書き出してみます。

![ad_04.jpg](https://qiita-image-store.s3.amazonaws.com/0/69622/cc398646-16b6-f4d2-f604-2ee306b617ca.jpeg)

``let f x y = x + y``という式があったとき、``f``の型は``xの型 -> yの型 -> x + yの型``と等しくなります。
let式の中身を見てみると、``x + 1``とあります。これは``x``の型は1の型、すなわち``int``と等しいということになります。

![ad_05.jpg](https://qiita-image-store.s3.amazonaws.com/0/69622/ffb43614-3fe2-8e2d-9278-a68eb84b5c54.jpeg)

``x + 1``の型は``int``だとわかりました。すると``f``の型は``int -> int``だとわかります。
``xの型 -> x + 1の型``ということですね

![ad_06.jpg](https://qiita-image-store.s3.amazonaws.com/0/69622/537bbd96-d50d-c997-8d7e-809d0fc66f1f.jpeg)

## 関数2

もうちょっとややこしく。
![ad_07.jpg](https://qiita-image-store.s3.amazonaws.com/0/69622/870f34df-336e-6321-cc6b-3802b730b701.jpeg)

わかっていることを書いて。
![ad_08.jpg](https://qiita-image-store.s3.amazonaws.com/0/69622/f0b88c4b-9958-8f3c-877d-be6e146a54e4.jpeg)


letの式の中身を評価していきます。

``g``の中の``x + y``は``int``。
よって``g``は``xの型 -> x + yの型``で``int -> int``。
![ad_09.jpg](https://qiita-image-store.s3.amazonaws.com/0/69622/34649ce7-1596-6a91-dc2b-2295ec40b17d.jpeg)

``f``の中は``let g x = x + y in g x``ですが、結局は``g x``です。
``g``は``int -> int``なので``g``の引数の``x``は``int``、``g x``も``int``とわかります。
結果的に``f``の型は``xの型 -> yの型 -> g xの型``で``int -> int -> int``とわかります。
![ad_10.jpg](https://qiita-image-store.s3.amazonaws.com/0/69622/5e36cc85-64d6-f6a3-0226-2fc956fe23e9.jpeg)

以上、単相型推論の簡単な解説でした。

# そして多相へ

さて、多相になるとちょっと難しくなります。

一番最初の例ですが、ちょっと複雑なコードを示します:
![ad_0_0.png](https://qiita-image-store.s3.amazonaws.com/0/69622/ca22eb09-d3b7-dd42-73cc-5564e6ec8d60.png)

わかることを書き出します:
![ad_0_1.png](https://qiita-image-store.s3.amazonaws.com/0/69622/2227e0fa-922e-d6b8-d447-09b5f0d9e8a8.png)

続いて、**単相のときと同じように**型を推論してみます。
![ad_0_2.png](https://qiita-image-store.s3.amazonaws.com/0/69622/854c16f5-bd2e-dbb9-3959-d701e47698a1.png)


一見正しく型推論できているようですが、
このままだと``f 1 2``を評価したときに ``T(0)``が``int -> int -> bool``となってしまい、以降``f``が呼び出された時に多相性が失われてしまいます。``f``が``'a -> 'a -> bool``だったはずなのに、``'a``が``int``で上書きされてしまいます。
``f 1.2 3.4``などとすると型エラーになるわけです。これではいけません。

ここからは多相型推論の手順を説明します。
下の図の``T(2) -> bool``の右下をみてください。
![ad_0_3.png](https://qiita-image-store.s3.amazonaws.com/0/69622/3be75825-f81b-a76c-d3f8-9ef9e2974c3c.png)
何か``{}``という物がついていますね。ここには**その型に含まれるidから, その型環境に含まれるすべての型のそれぞれに含まれるidからそのそれぞれの型の{}に含まれるidを取り除いたもの, を取り除いたもの**が含まれます。

... 多分今の説明で理解できた人は少ないと思います ...
ここからは、多相型推論を理解する上で知っておかなくてはならないことをまとめます。

まず型環境というのは、簡単に言えば、ある型を推論する時点ですでに存在が知られている型の集合です。
上の図で3行目までを読み込んで``g``の型を推論する場合なら、``f``, ``x [id=1のやつ]``, ``y``がそうです。``g``の型を推論するのですから、``g``や``x [id=4のやつ]``は含まれません。

そして肝心の ``{}`` の役割ですが、ある``{}``を持つ型は、**instantiate**されるときにその``{}``に含まれるidと同じidの型を新しいidの型に変えます。instantiateというのは、ある変数が使われるときに、型の多相性を実現するために、その変数の型に今説明した手順を実行することです。図に示すと次のようになります:
![ad_0_4.png](https://qiita-image-store.s3.amazonaws.com/0/69622/5f4d9b99-a2ba-7fa5-a4cc-519040b4cc7e.png)

``T(0) -> T(0) -> T(0)``という型があったとして、``{0}``がくっついているなら、その中の``T(0)``を全て新しい``T(1)``で置換します。``T(1)``というのは、まだ使われていないidならなんでも良いはずです。

そして、先ほどの長くて難しい文章、``{}``に含ませるidを決定する操作のことを**generalize**といいます。汎用的になるんですね。すべての変数はgeneralizeされて``{}``を持つことになります。

さて、ここまでで一応、多相型推論はできるようになったはずです。やってみましょう。
もう一度先ほどの画像です:
![ad_0_3.png](https://qiita-image-store.s3.amazonaws.com/0/69622/3be75825-f81b-a76c-d3f8-9ef9e2974c3c.png)

ここまでで``g``の型がわかっています。次は``f``ですね。
画像内のコードの４行目で``x [id=1]``の型が決定されます。
letでgが定義されているのでgの型には``{}``が付き、gにxが適用されるので``g``がinstantiateされます。
{}の中身を表で計算してみましょう。

|集合名|中身|
|:---|:---|
|型環境に含まれるすべての型|T(0), T(1), T(2), int, bool|
|型環境に含まれるすべての型のid| 0, 1, 2 |
|型環境に含まれる型の``{}``に含まれるもの||
|型環境に含まれるすべての型のidから``{}``に含まれるものを除いたもの|0, 1, 2|
|gの型に含まれるid| 2 |
|gに含まれるidから, その型環境に含まれるすべての型のそれぞれに含まれるidからそのそれぞれの型の{}に含まれるidを取り除いたもの, を取り除いたもの||
よって、{}の中身には何も入りません。

![ad_0_5.png](https://qiita-image-store.s3.amazonaws.com/0/69622/59f1cc76-ea5d-6898-2203-a797ecce67c2.png)
``g``がinstantiateされましたが、``{}``の中身が空なのでこの場合特に変化はありません。
``f``の返却型は``g x``より``bool``です。
このままだと、``f``の型は``T(2) -> T(2) -> bool``ですが、``{}``のことを思い出してみましょう。
あのgeneralizeの長い難しい文章通りに手順を踏めば、``{2}``という結果が得られるはずです。
やってみましょう。

|集合名|中身|
|:---|:---|
|型環境に含まれるすべての型|int, bool|
|型環境に含まれるすべての型のid||
|型環境に含まれる型の``{}``に含まれるもの||
|型環境に含まれるすべての型のidから``{}``に含まれるものを除いたもの||
|fの型に含まれるid| 2 |
|fに含まれるidから, その型環境に含まれるすべての型のそれぞれに含まれるidからそのそれぞれの型の{}に含まれるidを取り除いたもの, を取り除いたもの|2|
正しく``{2}``という結果が得られました。
![ad_0_6.png](https://qiita-image-store.s3.amazonaws.com/0/69622/3c0fd0a1-606d-0950-e906-b1beb1f82ca3.png)
こうすれば、``f 1 2``を評価した時には``f``の型は``T(5) -> T(5) -> bool``と評価されて多相性が実現されます。``int``で上書きされないんですね。


以上が多相型推論の説明でした。この記事自体、急いで書いたので(ただいま 12/19 20:00)わかりづらいところや間違っている部分もあると思います。
コメントお待ちしております。