如何测试此数据类型的Semigroup定律？

Question

我试图解决与"第一原理的Haskell编程"第15章中的另一个问题相同的练习.我已经创建了一个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),但是练习文本表明这样的事情是可能的.

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

编辑:

作者给出了这个练习的提示:

提示:此函数最终将应用于a类型的单个值.但是你将拥有多个可以产生类型b值的函数.我们如何组合多个值,以便我们只有一个b？这个可能会很棘手!请记住,Combine中的值的类型是函数的类型.如果你无法弄清楚CoArbitrary,不要担心QuickChecking这个.

@ 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"decidable equality"类型的结果将(==) :: X -> X -> Bool替换为Property我们可能称之为"testable equality"的结果funEquality :: X -> X -> Property.实际上没有必要使用property和转换函数a -> Property(或者a -> Bool如果你使用的话(==))Property,但是类型看起来更整洁.

我们需要重写与associativity属性相对应的函数,因为我们不再依赖它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)