Haskell中如何编写检查两个函数外延相等的checkEquality函数

你当前的实现无法通过编译，核心原因是Haskell没有为函数类型提供默认的Eq实例，直接用==比较两个函数是语法不支持的操作，也不符合你要的外延相等需求。

正确实现逻辑 #

你需要的外延相等，核心判定规则是：对定义域内的所有合法输入，两个函数的输出都相等。这就要求输入类型的定义域是有限可枚举的，我们才能遍历所有输入完成校验。

调整后的类型签名和实现如下：

-- 新增Bounded约束用来获取定义域的上下边界
checkEquality :: (Bounded a, Enum a, Eq b) => (a -> b) -> (a -> b) -> Bool
checkEquality f g = all (\x -> f x == g x) [minBound .. maxBound]

使用示例 #

针对Bool、固定位宽Int这类有限定义域类型的函数可以正常校验：

-- 测试Bool类型函数
> checkEquality (\x -> x && True) id
True
-- 测试Int类型的平方函数
> checkEquality (\x -> x * x :: Int) (\x -> x ^ 2 :: Int)
True

使用限制 #

• 仅支持输入类型a同时实现了Bounded和Enum的场景，也就是定义域必须是有限可枚举的，Integer、字符串这类无限定义域的类型无法用该方法比较。
• 理论上不存在通用的、支持无限定义域的函数外延相等判定算法，这是停机问题的直接推论，没有通用实现方案。
• 如果不需要全定义域校验，仅需要针对指定测试用例验证相等，可以使用自定义测试用例的版本：

checkEqualityWithCases :: Eq b => [a] -> (a -> b) -> (a -> b) -> Bool
checkEqualityWithCases cases f g = all (\x -> f x == g x) cases

使用时传入你需要测试的输入列表即可，不需要Bounded和Enum约束：

> checkEqualityWithCases [1,2,3,4,5] (\x -> x*x :: Integer) (\x -> x^2 :: Integer)
True

内容的提问来源于stack exchange，提问作者m1759