[Haskell] instance宣言に関するエラーの原因いろいろ

そこそこ長くなっちゃいました。

必ずしもこの記事を全部読んで完璧に覚えようとする必要はないと思います。
エラーが起こった時だけエラーメッセージでページ内検索するような使い方をしてもらうのも良いかもしれません。

けっこう厳しいルールですが、これのおかげで実行時のややこしさが減ると思えば大好きになります　(*´σｰ｀)ｴﾍﾍ


# はじめに
Haskellのinstance宣言に関するルールについてです。
意外と詳しく説明してくれている記事が少ないので書かせてもらいます

詳しいことは栄光のHaskellコンパイラ利用手引の[インスタンス宣言](http://www.kotha.net/ghcguide_ja/7.8.2/type-class-extensions.html#instance-decls)とかを読めば良いんですが、**「言語拡張なんて使ってないのにエラーが出た。なにが悪いかわからない」**という人が読むには少し重たいのではないかと思います。

instance宣言まわりには強力で面白い言語拡張がたくさんあって面白いのですが、それらについてのルールについて一つの記事にまとめるのは難しいので、今回の記事では**言語拡張を使う場合については詳しく触れません。**
# ルール
さっそくですが、言語拡張のない場合についてのinstance宣言に関するルールを以下に挙げていきます。

1. class宣言とinstance宣言で種（kind）を合わせる必要がある
- 参照されるinstance宣言に複数の候補ができてしまう書き方はできない
- シノニムは使えない
- 型変数は型コンストラクタに適用させる必要がある
- 型コンストラクタに型変数ではない具体的な型を適用させてはいけない
- 同じ型変数は複数回使えない

（言及し忘れていることがあったら、ご指摘お願いします）

次の章から詳しくこれらについて一つずつ説明していきます。

# 1. class宣言とinstance宣言で種（kind）を合わせる必要がある
さっそく種（kind）という、多くの入門サイトには書いていないワードが出てきて驚くかもしれませんが、理解してしまえばあたりまえのことを言っているだけです。

## 種とはなにか
（ちょっと長いし難しいです。最悪、読み飛ばしてもinstance宣言のルールは理解できますが、重要な語彙なので、知らない方はぜひ理解してください）

種は、よく「型の型」であると説明されます。
**全ての値に型があるように、全ての型には種があります**

ある値`x`が、型`t` を持つとき、`x :: t` と書くように、
ある型`t`が、種`k` を持つとき、`t :: k` のように書きます。
（実際にコード中に種注釈を書くには KindSignatures拡張が必要です）

そして、Haskellにおいて値を持つ型は、**全て種 `*`（スター）の要素です。**

`Int`、`[Bool]`、`(Int, Char)`、`Maybe Double`、 `String -> Int` などなど、挙げていけばキリがありませんが、値を持つ型は全て、`*`という種を持ちます。

それでは `*` 以外の種を持つものは何なのかというと、**型コンストラクタ**がその代表です。
たとえば、`Maybe`という型コンストラクタは、種 `* -> *` を持ちます。
これは関数に値を適用すると戻り値が得られるのと同じように、Maybeという型コンストラクタに種 `*` の型を適用すると種 `*` の型が得られる（値を持つ型になれる）ことを示しています。

同じように、Eitherという型コンストラクタは種 `* -> * -> *` を持ちますが、これは種 `*` の型を2つ与えると、種 `*` の型が得られるという意味です。

言語拡張を使わない限り、Haskellで扱う種は `*` や、`* -> *`、 `* -> * -> *` といったものばかりです（言語拡張を使うとNat、Symbol、Constraintなど色々な種がワンサカでてきます）

型や型コンストラクタの種は、ghciで以下のように調べることができます。

```:ghci
> :kind Int
Int :: *

> :kind Either
Either :: * -> * -> *
```

いろんな型や型コンストラクタの種を調べて、種の感覚をつかんでおきましょう。


##instance宣言と種
閑話休題です。
「class宣言とinstance宣言で種（kind）を合わせる必要がある」とはどういう意味なのか。

それはつまり、以下のinstance宣言がエラーになるということです。

```:ghci
> instance Eq Maybe
<interactive>:1:13 error:
    ・Expecting one more argument to ‘Maybe’
      Expected a type, but ‘Maybe’ has kind ‘* -> *’
...
```

Maybeは型ではなく型コンストラクタであるから、Eqのインスタンスになれないんですね。

「そりゃそうだろ」と思うかもしれませんが、種（kind）という単語が分からないと、エラーメッセージが読めなくて困ったりします。

「Expected a type,...」 の type とは種 `*` の型のことです。

同様に以下もエラーとなります。

```:ghci
> :i Functor
class Functor (f :: * -> *) where
...

> instance Functor Int
    ・Expected kind ‘* -> *’, but ‘Int’has kind‘*’
...
```

class宣言のほうで、Functorクラスのインスタンスになれるのは `* -> *` の種を持つものだと宣言しているので、種`*`であるIntはFunctorにできないんですね。

このあたりの理解があやふやだと、自作の型をモナドにしようとして、Functorのインスタンスにする時点でエラーになって挫折したりします（体験談）

ちなみに、Eitherは種 `* -> * -> *`のはずですが、どうやってFunctorになっているかというと、

```:ghci
> :i Either
...
instace Functor (Either a) -- Defined in ‘Data.Either’
...
```

とあるように、型変数`a :: *`を部分適用することで、`Either a :: * -> *`という種を持つようにしているんですね。

ですので、「EitherはFunctorである」というのは正確には間違っていて、
「任意の型aに対してEither a はFunctorである」というのが正しいです。

# 2. 参照されるinstance宣言に複数の候補ができてしまう書き方はできない

以下のコードはコンパイルエラーとなります。

```hs:instance.hs
newtype MyType a = MT a

class ClassA a where
  foo :: a -> String

instance Num a => ClassA (MyType a) where
  foo = const "Num!!"

instance Show a => ClassA (MyType a) where
  foo = const "Show!!"
```

```:error
instance.hs:6:10 error:
    Duplicate instance declarations:
      instance Num a => ClassA (MyType a) -- Defined at instance.hs:6:10
      instance Show a => ClassA (MyType a) -- Defined at instance.hs:9:10
```

このようなinstance宣言が許されていない理由は、上記のコードで、`foo (3 :: Int)` のような呼び出しがされたときに、戻り値が"Num!!"になる関数と"Show!!"になる関数のどちらの宣言を参照すれば良いのか決定できないからです。

このコンパイルエラーは、実際にコード中でfooの呼び出しがされていなくても、instance宣言が重複していたらその時点で発生します。

# 3. シノニムは使えない
これは有名ですね。

```hs:instance.hs
newtype MyType a = MT a

class ClassA a where
  foo :: a -> String

type MySynonym a = MyType a

instance ClassA (MySynonym a) where
  foo = const "Hello!!"
```

```:error
instances.hs:8:10 error:
    ・Illegal instance declaration for `ClassA (MySynonym a)'
        (All instance types must be the form (T a1 ... an)
         where T is not a synonym.
         Use TypeSynonymInstances if you want to disable this.)
```

この制約から、`String`型に対するinstance宣言は行なえません。
また、後に紹介する「型コンストラクタに型変数ではない具体的な型を適用させてはいけない」という制約から、`[Char]`型に対するinstance宣言も不可能です。

どうしても`[Char]`だけに特別なinstance宣言が必要な場合は、OverlappingInstances拡張（GHC7.10以降では非推奨）を使うか、OVERLAPPING, OVERLAPPABLE, OVERLAPS プラグマを使う必要があります。

これらの使い方については今後また記事を書きたいと思っています。

# 4. 型変数は型コンストラクタに適用させる必要がある
以下のコードはコンパイルを通りません。

```hs:instance.hs
class ClassA

instance Eq a => ClassA a
```

```:error
instances.hs:3:10 error:
・Illegal instance declaration for `ClassA a'
    (All instance types must be the form (T a1 ... an)
     where a1 ... an are *distinct type variables*,
     and each type variable appears at most once in the instance head.
     Use FlexibleInstances if you want to disable this.)
```

型変数`a`が型コンストラクタに適用されずに使われているからです。

おそらく、型変数`a`に対する宣言は一般的過ぎて「参照されるinstance宣言に複数の候補ができてしまう書き方はできない」というルールに高確率で違反してしまうため、このような形でのinstance宣言を許さない方針になったのだと思います。

ちなみに、この制限はFlexibleInstances拡張で緩和できます。
ただし、それによって宣言が重複してしまった場合はOVERLAPSプラグマ等を使ってオーバーラップの規則を決めましょう。

詳しくはまたこんど記事にします。

# 5. 型コンストラクタに型変数ではない具体的な型を適用させてはいけない
```hs:instances.hs
newtype MyType a = MT a

class ClassA a where
  foo :: a -> String

instance ClassA (MyType Int) where
  foo = const "Hello!!"
```

```:error
instances.hs:6:10 error:
・Illegal instance declaration for `ClassA (MyType Int)'
    (All instance types must be the form (T a1 ... an)
     where a1 ... an are *distinct type variables*,
     and each type variable appears at most once in the instance head.
     Use FlexibleInstances if you want to disable this.)
```

`MyType`が、型変数ではなく`Int`という具体的な型に適用されているのが問題だということですね。

型コンストラクタをつかわない場合は型変数はNGで具体的な型はOKだったんですが、型コンストラクタを使う場合は具体的な型はNGで型変数がOKになります。

`newtype MyInt = MyInt (MyType Int)`のようにラッピングして、`MyInt`に対するinstance宣言を書くようにしましょう。

ちなみに、この制限はFlexibleInstances拡張で緩和できます。
ただし、それによって宣言が重複してしまった場合はOVERLAPSプラグマ等を使ってオーバーラップの規則を決めましょう。

詳しくはまたこんど記事にします。

# 6. 同じ型変数は複数回使えない
以下のコードもコンパイルエラーが起こります

```hs:instances.hs
newtype MyType a b = MT (a, b)

class ClassA

instance ClassA (MyType a a)
```

```:error
instances.hs:6:10 error:
・Illegal instance declaration for `ClassA (MyType a a)'
    (All instance types must be the form (T a1 ... an)
     where a1 ... an are *distinct type variables*,
     and each type variable appears at most once in the instance head.
     Use FlexibleInstances if you want to disable this.)
```

`MyType a a`のように同じ型変数を2回使うことも許されていません。
これもinstanceの重複を防ぐためでしょう。

このようなことがしたい場合は、`newtype MyType2 a = MyType a a`のようにラッピングして、`MyType2 a`に対してinstance宣言をしましょう。

もしくは、FlexibleInstances拡張を使えばこのような宣言も許容されます。
それによって重複が発生したら、OVERLAPSプラグマなどを使いましょう。

また、GADTs拡張やTypeFamilies拡張を使うと、

```hs:
instance (a ~ b) => ClassA (MyType a b)
```

のように書くことで、`(a ~ b)`（aとbが同じ型である）という制約を書けるようになります。


# まとめ
instance宣言に関するルールは以上です。
もう一度確認すると、

1. class宣言とinstance宣言で種（kind）を合わせる必要がある
- 参照されるinstance宣言に複数の候補ができてしまう書き方はできない
- シノニムは使えない
- 型変数は型コンストラクタに適用させる必要がある
- 型コンストラクタに型変数ではない具体的な型を適用させてはいけない
- 同じ型変数は複数回使えない

とのことでした。
書き漏らしがあったら是非指摘してください。