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

我试图解决与"Haskell Programming from First Principles"第15章中的this other question相同的练习。我已经创建了一个Semigroup实例，并且在编写练习的QuickCheck部分时遇到了麻烦。如何测试此数据类型的半群法则？

半群实例应该满足：

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

<>哪里是半群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的函数），但练习文本表明这样的事情是可能的。

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

编辑：

作者给出一个提示本练习：

提示：此功能最终将应用于单值类型的。但是，您将拥有多个可以生成类型b的值的函数。我们如何组合多个值，所以我们有单个b？这一个可能会很棘手！请记住，组合内的值的类型是函数的值。如果你找不到CoArbitrary，不要担心这个问题QuickChecking 。

@李霞瑶的回答似乎是最好的答案。但是，我不应该使用这个CoArbitrary实例来做什么吗？

来源

2016-12-27 Thales MG

最新的QC支持版本[功能]（https://hackage.haskell.org/package/QuickCheck-2.9.2/docs/Test-QuickCheck-Function.html），但你必须改变你的type - 'newtype Combine'fun ab = Combine（fun ab）;键入Combine = Combine'（ - >）;类型Combine_Test = Combine'Fun'（或创建一个复制结构的独特类型，但用'Fun'替换' - >'） – user2407038

虽然对于这个例子他们希望你总体上使用'quickCheck'，使用lambda演算可以减少函数一般证明平等。 –

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

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

-- 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的类型是什么，我们可以称之为“可测试平等” funEquality :: X -> X -> Property替换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) => CombineAssoc a b 
combineAssoc f g h = ((f <> g) <> h) `funEquality` (f <> (g <> h))

编辑：在这一点上我们实际上仍然缺少一个Show实例Combine。 QuickCheck提供了一个封装器(:->)来生成和显示函数作为反例。

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

来源

2016-12-28 00:21:56

这真是一个很好的答案！但请看我的编辑。看来作者打算使用/为此类型创建一个CoArbitrary实例并使用它来测试。但是如何？ –

提示并不是建议使用“CoArbitrary（Combine a b）”，而是使用“CoArbitrary a”实例来执行“Arbitrary（Combine a b）”。当使用由QuickCheck库提供的“Fun”生成函数时，我隐式使用'CoArbitrary a'（在参数类型上），提示是关于如何实现这样的函数生成器。 –

确实这是不可能的，或者至少不可行，但是你并不真的需要一个像Int这样大的参数类型的测试用例！

对于较小的类型，例如Int16，你可以彻底尝试所有可能的参数来确定平等。该universe package有一个方便的类：

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

来源

2016-12-27 18:35:36 leftaroundabout

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

回答

相关问题