型クラスの歴史を軽くひも解く

現在、型クラスは Haskell のみならず、様々な言語で実装されたり似たようなものが実装されている言語機能です。
そういった風潮にも拘わらず、型クラスはどうにも大仰に捉えられがちに感じます。勿論、Haskell でも当初の仕様に比べると、最新の仕様はややこしいし、GHC の拡張や他機能と組み合わせるともっとややこしいのは事実ですが。

ということで、型クラスとはそもそもどういう motivation で発明、導入されたのか、簡単に調べてみます。

Haskell の型クラスは 1992 年の Haskell 1.2 で導入されました。1.2 のレポートに以下のような記述があるので間違ってないはず（他の言語でより早く実装されてるかもしれないけどそこまで調べてると時間なくなるので見ないふりをする。）。

>Haskell is a large and complex language. designed for a wide spectrum of purposes. It
also introduces a major new technical innovation. namely using type classes to handle
overloading in a systematic way. This innovation permeates every aspect of the language.

勿論、提案自体はそれ以前にされていますし、motivation もレポートよりはそういった提案論文とかに書いてあるはずなので、そちらを調べてみましょう（調べながら書いてます）。

ML （メーリングリストの方）等でもやり取りはされてたのでしょうが、paper という形で type class が提案された最初の論文は、多分（間違ってたら教えてください）Wadler 先生が first author の "How to make ad-hoc polymorphism less ad hoc" だと思います。違ってたらすいません。前述の論文のアブストには以下のような記述があります。

>Type classes permit overloading of arithmetic operations such as multiplication, and generalise the "eqtype variable" of Standard ML.

ML 系の言語、Standard ML や OCaml 等を知っている人からすればなじみの深い話だと思うのですが、実は + （加算）や * （乗算）や == （equality）が、様々な型で自然に利用できるというのは、意外に簡単な話ではないのです。素朴な Hindly/Milner の型システムの上では、`1 + 1` と `1.0 + 1.0` という記述を同時に許すことは叶いません。C や Java 等の他言語ではごく普通に記述できるのに（仕様が簡単とはいってない）意外と感じる人も多いかもしれません。

FPL では、演算子も基本的には単なる関数のうちの一つである場合が多いです。一方で前述した C や Java 等の演算子は、関数とは異なる扱いの特別な物として提供されています。この違いが「異なる型の整数値の演算について、同じ演算子を使いたい」という素朴な問題を難しくしてしまっているのですね。
単なる関数に見えてそうでなかったりするものの例として、OCaml の [= 演算子等](https://github.com/ocaml/ocaml/blob/019f469aa36c65d5436c0cc107aff310aa399735/stdlib/pervasives.mli#L51)があります。external 修飾子がついていますね。これは OCaml コードでは実装しないよ、C とかに任せるよ、という意味です。
より具体的にはどうなのかというと、自分の記憶が間違っていなければ、OCaml コンパイラは、コンパイル時に型推論器から得られた型情報を用いて、演算子に渡されている値が、ある種の型に定まる場合に関しては、その型のために用意された関数を利用するコードにし、それ以外の場合は実行時型情報を用いる関数を利用するコードにします。間違ってたら識者コメントお願いします。

同じ名前のある関数に関して、異なる型シグネチャの実装が複数定義できればいいだけの話じゃないか、と思う人は多いでしょう。それは正しく、関数のオーバーロードと呼ばれているものです。様々な言語で関数のオーバーロードは提供されています。そしてこれが、上述した論文のタイトルにあった ad-hoc polymorphism と呼ばれているものの大体の正体でもあります。ad-hoc polymorphism、案外身近なものです。
しかし、FPL で使われる Hindly/Milner や System F、またそれらの拡張といった型システム的には、関数のオーバーロードはちょっと困る言語機能なのです。詳細は略。
早い話が、FPL は採用する型システムの都合で、関数のオーバーロードは提供し難い、ということです。

調べながら書いてるため話の流れが大分不自然になりましたが…兎も角、四則演算などを複数の型で利用できるようにするために提案されたのが型クラス、ということになります。やれ Monad だ Functor だ Applicative だといった、型クラスといったらこれ、といった人気のワードからは大分遠く、素朴なところに辿り着きましたね。

型クラスは関数のオーバーロードなしに ad-hoc polymorphism をどのように実現しているのでしょうか。
実装としては非常に簡単です。dictionary と呼ばれる物を利用するよう関数定義を変換することで、異なる型の値をうまく捌きます。

クラス宣言では、制約を満たす型について、適用の許されるメソッド（関数）の宣言を列挙します。定義を持つことも可能です（関連型も持てますが高度な機能なので今回はなし）。
例えば equality のための型クラス Eq は以下のようになります。

```hs
class Eq a where
  (==), (/=) :: a -> a -> Bool

  x /= y =  not (x == y)
  x == y =  not (x /= y)
```

この型クラスの宣言について、様々な型で instance が定義されていたり、自分で定義したり（殆ど deriving でしょうが）します。手元の ghc（バージョンが古い…）で少し調べてみましょう。

```hs
Prelude> :info Eq
class Eq a where
  (==) :: a -> a -> Bool
  (/=) :: a -> a -> Bool
        -- Defined in ‘GHC.Classes’
instance (Eq a, Eq b) => Eq (Either a b)
  -- Defined in ‘Data.Either’
instance Eq Integer
  -- Defined in ‘integer-gmp-1.0.0.0:GHC.Integer.Type’
instance Eq a => Eq [a] -- Defined in ‘GHC.Classes’
instance Eq Word -- Defined in ‘GHC.Classes’
instance Eq Ordering -- Defined in ‘GHC.Classes’
instance Eq Int -- Defined in ‘GHC.Classes’
instance Eq Float -- Defined in ‘GHC.Classes’
instance Eq Double -- Defined in ‘GHC.Classes’
instance Eq Char -- Defined in ‘GHC.Classes’
instance Eq Bool -- Defined in ‘GHC.Classes’
...
```

数値型などは大体インスタンスが定義されていることが分かりました。インスタンスの定義されている型であれば、メソッドの適用が可能です。よって、以下のような記述がようやくできます。やったね。

```hs
1 == 1
```

```
ここにメソッドの実装の話、OCaml 等が採用しない理由の話、他続きを書く
```

後で書く。
ほぼ書いたようなものな気もする…続きが書かれなかったら論文読んでください。