Edited at

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

More than 1 year has passed since last update.


やりたいこと

a -> bEqのインスタンスにしたいです。

-- (構想)

instance Eq (a -> b) where
f == g = ...


きっかけ


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


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


関数の等価性の定義

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

そのため、関数の定義が異なっても等価なものもあります。

例えば、以下のように定義が異なってもpow2pow2'は等価な関数のはずです。

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 -> bEqのインスタンスにできました。

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を使って等価性を調べてみます。

以下のようにordordなら等価になります。

> ord == ord

True

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

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

> ord == nextOrd
False

次は、定義が違うpow2pow2'を比較します。

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