Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationEventAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
9
Help us understand the problem. What are the problem?

More than 3 years have passed since last update.

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

やりたいこと

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
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
9
Help us understand the problem. What are the problem?