Overlapping Instancesと戦う

一般に、Instance resolutionで述べたように、 GHCは、型クラス制約を解決するために使用されるinstance宣言が曖昧ではないことを要求する。 GHCは、 最も具体的な形が存在する時に限って 複数のinstanceにマッチすることを許すという方法で、instanceの解決を緩める方法も提供している。さらに、これはもっと緩くすることもできて、最も具体的な形があるかどうかにかかわらず、複数のinstanceにマッチすることを許すこともできる。この節で詳しく述べる。

instanceの選択をコントロールするには、それぞれのinstanceについてオーバーラップしたときの挙動を指定することができる。 instance キーワードの直後に次のいずれかのプラグマを書けば良い: {-# OVERLAPPING #-}, {-# OVERLAPPABLE #-}, {-# OVERLAPS #-} または {-# INCOHERENT #-}

INCOHERENT はinstanceが自由にoverlapしたりされたりすることを許すが、使わないほうがいいプラグマなので出来る限り避けたほうがいい。 また、後にもあるように OVERLAPS は OVERLAPPING と OVERLAPPABLE のいずれにもなるので OVERLAPS で事足りる場合も多いと思う。

また、いちいちプラグマを書かなくてもいいように、デフォルトの挙動を指定するための拡張 -XIncoherentInstances と -XOverlappingInstances も あるけれど使用は出来る限り避けよう。

さて、あるクライアントモジュールで (C ty1 .. tyn) なる制約の対象になるようなinstanceを探しているとしよう。この検索は次のようにして行われる:

• 対象となる制約に マッチする instance I を全て見つける。つまり、対象となる制約 (C ty1 .. tyn) に何かを代入した形が、ここでいうinstance I である。このinstance宣言を 候補 と呼ぶ。

• 次の両方を満たす候補 IX を除く。

  • 他により具体的な候補 IY が存在する。すなわち、 IY は IX に何かを代入した形であるが、逆は成り立たないもの。

  • IX が overlappable であるか、または IY が overlapping である(ここが「かつ」ではなく「または」となっているのは、ライブラリ側を変更せずに、クライアント側で故意にライブラリのinstanceをオーバーライドできるようにするためである)。

• 残った候補がちょうど1つの場合、それを選択する(訳注: 原文ではnon-incoherentな、というのがついているが下の説明と整合しないのでこれは不要か？)。残った全ての候補がincoherentである場合は、最も任意性のあるものを選ぶ。それ以外の場合は、instanceの選択に失敗する(これはすなわち、残った複数の候補がincoherentではない場合である)。

• 上で選択した候補がincoherentでない場合、検索に成功したのでそれを返す。

• そうではない場合、対象の制約に マッチしない が、 単一化(unify)する instanceを全て見つける。この、候補ではないinstanceは、対象の制約がより細かくインスタンス化された場合にマッチする可能性がある。この時得られたinstanceが全てincoherentであれば、検索は成功し、選ばれた候補を返す。そうでなければ検索には失敗する。

incoherentプラグマを積極的に使う場面はないと思うので、incoherent関連の説明はあまり気にしなくても大丈夫だと思う。大事なのは2つ目の項目で、 具体的な候補が他にあるoverlappableな候補は選ばれないこと が大事。 また、overlapping instanceエラーは上の検索が起こった場合にしかおきないので、おかしなinstanceを書いただけでは特にエラーにはならないことに注意。

さて、次のstackoverflowの質問を例に挙げる。

How to resolve overlapping instance

簡単に言うと次のコードを考える:

  instance Transformable a a where ...
  instance (Transformable l l', Transformable r r') => Transformable (Either l r) (Either l' r') where ...

これは特定の条件下でoverlapping instance errorを引き起こすが、なぜか、そしてどうすれば解決できるか分かるだろうか。 これが分かっていれば、多分overlapping instanceに悩まされることはもうないと思う。

Transformable (Either a b) (Either a b) のinstanceを見つけようとすると、この2つはいずれも候補であり、さらにいずれも上で説明した検索アルゴリズムによって排除されない。 これは、上も下も互いのinstanceのより具体的な候補になっていないからである。

よって答えとしては次のようにinstanceを書き換えるのが正解(ベストアンサーになってるやつ)

  instance {-# OVERLAPS #-} (a ~ b) => Transformable a b where ...
  instance (Transformable l l', Transformable r r') => Transformable (Either l r) (Either l' r') where ...

制約の a ~ b はinstanceの検索には影響しないので、この場合は下の方が上より常に具体的になる(上に適切な代入を行うと下になる)。 よって下にoverlapping、または上にoverlappableの指定をすればoverlap問題は解決される。

何かの参考になれば。