type roleについて学ぶ

[Haskell Advent Calendar 2015](http://qiita.com/advent-calendar/2015/haskell) の 3日目は、最近 [洗濯機](https://twitter.com/SplatoonJP/status/670183349864894464) を新調した [@hiratara](https://twitter.com/hiratara) がお送りします。

気が付けばもうクリスマスシーズン、みなさんは今年どのくらいHaskellのコードを書きましたか？ 私は最近はGoとPerlしか書いてないのですが、今年の夏 [レガシーなコードをstackでビルドできるようにする](https://github.com/perl6/Pugs.hs/pull/30) ってことをやっていました。今日はその時に出くわしたあるエラーに関連する話を書きます。 ~~イカ~~ 以下がそのエラーなのですが、これを見てパッと対処法が浮かびますか？

```
    src/MO/Run.hs-boot:6:1:
        Type constructor ‘AnyResponder’ has conflicting definitions in the module
        and its hs-boot file
        Main module: type role AnyResponder nominal
                     data AnyResponder (m :: * -> *) where
                       MkResponder :: ResponderInterface m c => (m c) -> AnyResponder m
        Boot file:   abstract AnyResponder (m :: * -> *)
        The roles do not match. Roles default to ‘representational’ in boot files
```

エラー文言中に `type role ... nominal` とか見慣れない記法のコードが見られますね。いったいghcは何を言っているのでしょう。

## Role とは

まずは天下り的にRoleについて説明します。Haskellの型変数には、暗黙的に以下の3種類のRoleのうちいずれかが付けられています。

* Nominal
* Representational
* Phantom

先頭に挙げたエラーで言うと、型 `AnyResponder m` の型変数 `m` がいずれかのRoleを持っていることになります。エラーメッセージを読むと次のことが分かります。ghcの `*.hs` と `*.hs-boot` ファイルに書かれている型の定義は一致する必要がありますが、 `Run.hs` の中では型変数 `m` の Role が Nominal 、一方で `Run.hs-boot` の中では Role が Representational として定義されているためにghcが怒っているのです。

ということで、冒頭のエラーは [このコミット](https://github.com/perl6/Pugs.hs/commit/009d0ed328ea30b931cce8f6dd8d53c6aafcbd27) のように `RoleAnnotations` プラグマを有効にした上で、 `Run.hs-boot` 側で `type role AnyResponder nominal` と `AnyResponder` がとる型変数の Role が Nominal であると明示してやると直すことができます。めでたしめでたし。

## GeneralizedNewtypeDeriving 拡張

型変数に Role なんてものが割り当てられていなければ、こんなわかりにくいエラーに出くわすこともなかったはずです。 Role とはどのような働きをしているのでしょうか。

この Role と密接に関わるGHC拡張が、 `GeneralizedNewtypeDeriving` です。この拡張は、内部的な表現が同じ型について、すでに実装された定義をそのまま用いて型クラスのインスタンス定義を行ってくれるというものです。内部的な表現が同じ型、というのは、GHCの場合具体的に言うと `newtype` で宣言された型のことです。例えば、本当にどこででも見るよくある例を挙げると、

```hs
newtype Age = Age Int
```

と定義をした場合の `Age` 型は、型システムで区別されるというだけで実行時は単なる `Int` 型として処理されます。内部実装が同じなのであれば、 `Int` に対して実装された様々なコードを `Age` に対してもそのまま使えるとすごく便利です。例えば、 `Int` は `Num` のインスタンスなので足し算や引き算ができますが、 `Age` も実体が `Int` の実装を内部的に使ってくれるだけで足し算や引き算ができるようになるはずです。そのために、以下のように定義をします。

```hs
{-# LANGUAGE GeneralizedNewtypeDeriving #-}
newtype Age = Age Int deriving (Num)
```

`Age -> Age -> Age` という型と `Int -> Int -> Int` という型は内部表現が一致しますので、この定義によって `(-) :: Int -> Int -> Int` の実装を `Age` でも使いまわし、

```
*Lib> Age 38 - Age 19
Age 19
```

というように引き算をすることができるようになります。(ただし、ここではわかりやすさのため `Show` のインスタンスも定義しています)

この拡張のおかげで、 `Monad` のインスタンスなどもっと複雑なボイラープレートが必要となる型を扱う場合に、「`newtype` で包むのはいいんだけど手で定義するのめんどうだしな」ってのがなくなるわけです。やってることが単純なくせに効果が高い良い拡張ですね！

## GeneralizedNewtypeDeriving 拡張の危険性

ところがこの単純明快な拡張が、型システムの健全さを崩すリスクを持ってます。えっ、と思われるかもしれませんので、実際に例を見てみましょう。GHCには別の拡張で `TypeFamilies` という拡張があり、型を受け取って型を返す関数を定義することができます。例えば、以下の関数 `F` は `Int` を受け取ると `Int64` を返し、 `Age` を受け取ると `Int8` を返します。

```hs
type family F x
type instance F Int = Int64
type instance F Age = Int8
```

この `F` を使った `getF` という関数を持つクラスを考えます。 `getF` は `F` を施した表現を得るための関数というイメージです。

```
class GetF a where
    getF :: a -> F a
```

 `Int` は `Int64` の値を取り出せればいいはずですので、以下のようにインスタンスを定義することができます。

```
instance GetF Int where
    getF n = toEnum n
```

さて、 `Int` と `Age` は同じものでした。ので、何もしなくても `Age` も `GetF` のインスタンスになりそうなものですよね。ところが、そうしてしまうとまずいことになります。 `F Age` は `Int8` としましたから、 `Age` のインスタンスの `getF` の定義は `Age -> Int8` という型になるべきです。ところが、 `Int` 向けに用意した `getF` の実装は `Int -> Int64` という型です。引数は `Age` と `Int` で内部表現が同じものですが、戻り値が完全に別のものであり、矛盾しています。 これでは安心して `GeneralizedNewtypeDeriving` 拡張を使うことはできません。どうやら、 `Int` のインスタンス定義を無差別に`Age` のインスタンス定義として用いることを許すのはいいアイデアではないようです。

## Role が GeneralizedNewtypeDeriving 拡張の健全さを守る

Roleによって `deriving` できる型クラスを制限することで、この問題を解決できます。

最初の3種類のRoleの定義に戻りましょう。Representational は `GeneralizedNewtypeDeriving` を有効にするために必要なRoleであり、内部表現が同じものを型変数に入れて適用した場合に、きちんと内部表現が同じ型が生成されるということを表します。例えば `data G x = G x` のように定義された場合の `x` が Representational であり、 `G Int` と `G Age` は同じ内部表現を持ってくれます。

一方で先に定義した `F x` の `x` はそのような保証はなく、これを Nominal な Role といいます。実際、 `F Int` と `F Age` は違う内部表現を持つのでした。

このように Representational と Nominal を区別することで、どのような場合に内部表現が同じ実装を使いまわせるかを判断することができます。具体的に型クラス `GetF a` についてみてみましょう。このクラスのインスタンスを他の内部表現が同じ型のインスタンスでも使いまわしたい場合に、実際に使いまわすのは `getF` の実装ということになります。ところが、この `getF` の型の定義において、 `GetF a` の型変数 `a` が、 Nominal な型変数である `F x` の `x` へ代入されています。そのため、型の内部表現が一緒であっても、 `getF` の実装においては違う内部表現であることがありうるため、この実装を使いまわすことができないということがわかります。

Phantom については、その型変数が使われていないことを意味します。使われていないものは気にする必要がありません。

## Role の推論

Roleは自動で推論されます。安全性を担保するためのものが人の手によって勝手に定められるのは危険なのでそりゃそうですよね。今回のエラーの元となった `AnyResponder` の定義は以下の通りです。

```hs
data AnyResponder m = forall c. ResponderInterface m c => MkResponder !(m c)
```

さて、この `m` の Role はどうなるでしょうか。 `m` が型定義のどの位置で使われているかがポイントとなります。使われていなければ Phantom となります。この例の場合、 `ResponderInterface` という型クラスにおいて使われています。型クラスは、 `newtype` で宣言した同じ内部表現を持つ型について別の振舞を持つようにインスタンスを定義できる機能ですので、デフォルトではすべての型変数が Nominal と推論されます。ということで、 `m` は Nominal であるということが言えます。

通常であればここで Role が決定されて特に問題もなく終了するのですが、今回は `*.hs-boot` ファイルにおいても `AnyResponder` 型を定義しています。こちらは何も情報がないため、 `data` 型のすべての型変数の Role は Representational と推論されます。そのためギャップが生じて表題のエラーが出ていたわけです。 `*.hs` での推論結果を尊重するため、 Role Annotation によって明示的にRoleを指定してやると万事解決ということになります。

## そして Data.Coerce へ

`GeneralizedNewtypeDeriving` 拡張の同じ内部表現なら同じ実装を使えばいいじゃないって考え、素晴らしいですよね。これをさらに推し進めるのが [Data.Coerce](https://downloads.haskell.org/~ghc/7.10.1/docs/html/libraries/Data-Coerce.html) です。この型クラスが提供する `coerce` 関数を使うだけで、内部表現が同じ異なる型を行き来できます。特に、同じ内部表現を持つコンテナのような構造を内部を舐めることなく一挙に裸にできるのは強力です。もちろん、パフォーマンスの向上にも寄与します。

```
*Data.Coerce> coerce [[Age 10, Age 20], [Age 30]] :: [[Int]]
[[10,20],[30]]
```

当然、この変換にも `GeneralizedNewtypeDeriving` の時のような危険性があるため、 Role が活躍しています。 Role って、表舞台には出てこないけど重要なものなんですね！

## まとめ

このエントリでは、(少なくとも私は)普段あまり触れることがないType Roleについて、ドキュメントに書いてある程度のことを日本語で解説しました。本当は [3年前に @mr_konn さんが書かれていた](http://konn-san.com/articles/2012-06-06-promoted-types-and-list-arguments.html) ような `DataKinds` 拡張や、`Typeable` 型クラスの定義になくてはならない `PolyKinds` 拡張の話とかにつなげるつもりだったのですが、書き終わってみると全く出てきませんでした :p どちらもKindに対する拡張機能ですが、Roleも型の種類を分別していると思えばKindの一種という見方もできます。Kindの拡張にもっと興味がある方はこの @mr_konn さんのエントリも読んでみると面白いでしょう。

以上、イカもいいけどヤーナムとポッケ村もね、の @hiratara がお送りしました。 クリスマスまで残り22日、明日以降のAdvent Calendarもお楽しみに！

## 参考文献

* [Roles](https://downloads.haskell.org/~ghc/7.10.1/docs/html/users_guide/roles.html)
    * 元論文 [Generative type abstraction and type-level computation](http://www.seas.upenn.edu/~sweirich/papers/popl163af-weirich.pdf)
* [Generalising the deriving clause](https://downloads.haskell.org/~ghc/7.10.1/docs/html/users_guide/deriving.html#generalized-newtype-deriving)
* [Type families](https://downloads.haskell.org/~ghc/7.10.1/docs/html/users_guide/type-families.html)
* [Data.Coerce](https://downloads.haskell.org/~ghc/7.10.1/docs/html/libraries/Data-Coerce.html)
    * 元論文 [Safe Zero-cost Coercions for Haskell](https://downloads.haskell.org/~ghc/7.10.1/docs/html/libraries/Data-Coerce.html)