如何测试这种数据类型的半群法则？

Question

我正在尝试解决与 in Chapter 15 of "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.

@夏丽瑶的回答好像是最好的回答。但是我不应该使用这个 CoArbitrary 实例吗？

Answer 1

事实上这是不可能的或者至少是不可行的，但是你真的不需要像 Int!

这样的大参数类型的测试用例

对于较小的类型，例如Int16，你可以穷举所有可能的参数来确定是否相等。 universe package 有一个方便的 class：

import Data.Universe

instance (Universe a, Eq b) => Eq (Combine a b) where
  Combine f == Combine g = all (\x -> f x == g x) universe

然后您的原始检查将起作用，尽管速度慢得令人无法接受；我建议将其更改为 quickCheck (semigroupAssoc :: CombineAssoc Int16 Bool).

Answer 2

您无法决定两个函数是否相等。但是你可以测试它！

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

-- 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

请注意 "decidable equality" (==) :: X -> X -> Bool 类型的 Bool 结果被替换为 Property 我们可能称之为 "testable equality" 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))

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

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

如何测试这种数据类型的半群法则？

How to test Semigroup law for this data type?

haskell

types

typeclass

quickcheck