如何測試此數據類型的半羣法則？

我試圖解決與"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

如何測試此數據類型的半羣法則？

回答

相關問題