Haskellの関数に等価性を定義したい！

やりたいこと

a -> bをEqのインスタンスにしたいです。

-- （構想）
instance Eq (a -> b) where
  f == g = ...

きっかけ

一般的に関数の型をEqクラスのインスタンスにするのが実現不可能な理由は何か? どういった場合に実現可能か？

1年ぐらい前に、友人から上記の問いを出されて、その時に定義したものをまとめたいと思います。

関数の等価性の定義

おそらく、「同じ引数なら同じ戻り値を返す」関数同士は等価と言えるはずです。

そのため、関数の定義が異なっても等価なものもあります。
例えば、以下のように定義が異なってもpow2とpow2'は等価な関数のはずです。

pow2 x = x * x

pow2' x = x ^ 2

すべての値を列挙する

Eqのインスタンスにする方針としては、

1. すべての引数を列挙する
2. すべての引数に対してのすべての戻り値が等価か調べる
   です。

列挙するためには、Enum型クラスが使えそうです。
すべてを列挙するためにはBound型クラスが使えそうです。

つまり、以下ですべて列挙できます。

allRange :: (Enum a, Bounded a) => [a]
allRange = [minBound..maxBound]

使ってみるとこうなります。

-- Boolをすべて列挙
> allRange :: [Bool]
[False,True]

-- 独自型Colorを列挙
> data Color = Red | Green | Blue | White | Black deriving (Show, Enum, Bounded)
> allRange :: [Color]
[Red,Green,Blue,White,Black]

-- すべてのCharの数を調べる
> length (allRange :: [Char])
1114112

-- すべてのIntの数を調べる
length (allRange :: [Int])
(時間がかかります)

(a -> b)をEqのインスタンスにする

(Enum a, Bounded a, Eq b)という制約つきで、a -> bをEqのインスタンスにできました。

instance (Enum a, Bounded a, Eq b) => Eq (a -> b) where
  f == g = fmap f allRange == fmap g allRange
    where
      allRange :: (Enum a, Bounded a) => [a]
      allRange = [minBound..maxBound]

実際に関数同士を比較してみる

まずはord :: Char -> Intを使って等価性を調べてみます。
以下のようにordとordなら等価になります。

> ord == ord
True

以下はordと自作関数nextOrdは等価じゃないので、Falseです。

> nextOrd c = ord c + 1 -- nextOrdは自作関数
> ord == nextOrd
False

次は、定義が違うpow2とpow2'を比較します。
（Intだと現実的な時間で計算が終わらないので、Int8を使いました）

import           Data.Int

pow2 :: Int8 -> Int8
pow2 x = x * x

pow2' :: Int8 -> Int8
pow2' x = x ^ 2

以下のようにTrueになります。

> pow2 == pow2'
True

最後に、カリー化された関数でも試してみます。

import           Data.Int

-- 足し算
add = (+) :: Int8 -> Int8 -> Int8
-- 引き算
sub = (-) :: Int8 -> Int8 -> Int8

以下のように、うまく関数同士で、等価性の比較できました。

> add == add
True

> sub == sub
True

> add == sub
False

> sub == add
False