haskell - 如何测试这种数据类型的半群定律？

Question

我正在尝试解决与 this other question 的第 15 章中的 "Haskell Programming from First Principles" 相同的练习。我已经创建了一个 Semigroup 实例，但在编写练习的 QuickCheck 部分时遇到了麻烦。

Semigroup 实例应满足:

a <> (b <> c) == (a <> b) <> c

其中 <> 是 Semigroup mappend。

我想出了以下几点:

import Data.Semigroup
import Test.QuickCheck

semigroupAssoc :: (Eq m, Semigroup m) => m -> m -> m -> Bool
semigroupAssoc a b c = (a <> (b <> c)) == ((a <> b) <> c)

newtype Combine a b = Combine { unCombine :: (a -> b) }

instance Semigroup b => Semigroup (Combine a b) where
  (Combine f) <> (Combine g) = Combine (\x -> (f x) <> (g x))

instance CoArbitrary (Combine a b) where
  coarbitrary (Combine f) = variant 0

instance (CoArbitrary a, Arbitrary b) => Arbitrary (Combine a b) where
  arbitrary = do
    f <- arbitrary
    return $ Combine f

type CombineAssoc a b = Combine a b -> Combine a b -> Combine a b -> Bool

main :: IO ()
main = do
  quickCheck (semigroupAssoc :: CombineAssoc Int Bool)

除了 quickCheck 行之外，所有内容都可以编译，它提示存在 No instance for (Eq (Combine Int Bool)) arising from a use of ‘semigroupAssoc’ 。

我认为没有办法测试两个任意函数是否相等(由 Combine 包装的函数)，但练习文本表明这样的事情是可能的。

关于如何完成这项工作的任何想法？

编辑:

作者对此练习给出了提示:

Hint: This function will eventually be applied to a single value of type a. But you’ll have multiple functions that can produce a value of type b. How do we combine multiple values so we have a single b? This one will probably be tricky! Remember that the type of the value inside of Combine is that of a function. If you can’t figure out CoArbitrary, don’t worry about QuickChecking this one.

@Li-yao Xia 的答案似乎是最好的答案。但是我不应该使用这个 CoArbitrary 实例吗？

Answer 1

你不能决定两个函数是否相等。但是你可以测试它!

两个函数相等当且仅当对于任何输入它们给出相同的输出。这是一个可测试的属性:生成一些输入，比较输出。如果它们不同，那么您就有了一个反例。

-- Test.QuickCheck.(===) requires (Eq b, Show b)
-- but you can use (==) if you prefer.
funEquality :: (Arbitrary a, Show a, Eq b, Show b) => Combine a b -> Combine a b -> Property
funEquality (Combine f) (Combine g) =
  property $ \a -> f a === g a

注意 Bool导致“可判定相等”的类型 (==) :: X -> X -> Bool替换为 Property在我们可以称之为“可测试的平等” funEquality :: X -> X -> Property . property 其实没必要用并转换函数 a -> Property (或 a -> Bool 如果您使用 (==) )到 Property ，但这样的类型看起来更整洁。

我们需要重写关联属性对应的函数，因为我们不再依赖 Eq。 .

type CombineAssoc a b = Combine a b -> Combine a b -> Combine a b -> Property

combineAssoc :: (Arbitrary a, Show a, Eq b, Show b, Semigroup b) => CombineAssoc a b
combineAssoc f g h = ((f <> g) <> h) `funEquality` (f <> (g <> h))

编辑:此时我们实际上仍然缺少 Show Combine 的实例. QuickCheck 提供了一个包装器 Fun生成和显示函数作为反例。

main = quickCheck $ \(Fn f) (Fn g) (Fn h) ->
  (combineAssoc :: CombineAssoc Int Bool) (Combine f) (Combine g) (Combine h)