이 데이터 유형에 대한 Semigroup 법칙을 테스트하는 방법은 무엇입니까?

Question

"Haskell Programming from First Principles"의 15 장에있는 this other question과 같은 연습 문제를 해결하려고합니다. Semigroup 인스턴스를 이미 만들었고 QuickCheck 부분을 작성하는 데 문제가 있습니다.

반군 인스턴스 만족해야 <>은 반군의 mappend이다

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

.

나는 다음과 같이 올라와있다 :

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) 

모두는 No instance for (Eq (Combine Int Bool)) arising from a use of ‘semigroupAssoc’이 불평 quickCheck 라인을 제외하고 컴파일합니다.

임의의 두 함수가 같은지 테스트하는 방법은 없다고 생각합니다. (함수는 Combine로 감싸졌지만) 연습용 텍스트는 그러한 것이 가능함을 나타냅니다.

내가 어떻게이 작업을 할 수 있는지에 대한 아이디어가 있습니까?

편집 :

저자는이 운동에 대한 힌트를 줄 :

힌트 :이 기능은 결국 하나의 값을 입력의 에 적용됩니다. 그러나 유형 b의 값을 생성 할 수있는 여러 함수가 있습니다. 하나의 b 값을 갖도록 여러 값을 결합하려면 어떻게해야합니까? 이건 아마 까다 롭습니다! Combine 내부의 값 유형은 함수의 값임을 기억하십시오. 이 CoArbitrary를 알아 내지 못하면 빠른 검사에 대해 걱정하지 마십시오.

@ Li-yao Xia의 답변이 가장 좋은 답변 인 것 같습니다. 하지만이 CoArbitrary 인스턴스를 사용해서는 안됩니까?

Answer 1

두 가지 기능이 동일한 지 여부는으로 결정할 수 없습니다. 하지만 시험을 시험 할 수 있습니다!

두 함수는 동일한 입력을 제공 할 때만 동일한 출력을 제공합니다. 이것은 테스트 가능한 속성입니다. 입력을 생성하고 출력을 비교하십시오. 그것들이 다른 경우, 당신은 반대 사례를 가지고 있습니다."decidable 평등"(==) :: X -> X -> Bool의 종류에 Bool 결과는 우리가 "검증 평등"funEquality :: X -> X -> Property를 호출 할 수 있습니다 무엇에 Property으로 대체되는 것을

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

알 수 있습니다. 실제로 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)) 

편집 :이 시점에서 우리는 실제로 여전히 Combine에 대한 Show 인스턴스를 놓치고있어. QuickCheck는 반자본으로 함수를 생성하고 표시하는 래퍼 (:->)을 제공합니다. QC 지원

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

Answer 2

실제로 가능하지 않거나 적어도 가능하지는 않지만 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)으로 변경하는 것이 좋습니다.