I'm trying to solve the same exercise as this other question in Chapter 15 of "Haskell Programming from First Principles". I've already made a Semigroup instance, and I'm having trouble writing the QuickCheck part of the exercise.
A Semigroup instance should satisfy:
a <> (b <> c) == (a <> b) <> c
where <>
is the Semigroup mappend.
I have come up with the following:
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)
Everything compiles except for the quickCheck
line, where it complains that there is No instance for (Eq (Combine Int Bool)) arising from a use of ‘semigroupAssoc’
.
I don't think there is a way to test if two arbitrary function are equal (the functions wrapped up by Combine
), but the exercise text suggests that such a thing is possible.
Any ideas on how I could make this work?
EDIT:
The authors give a hint for this exercise:
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.
@Li-yao Xia's answer seems to be the best answer. But shouldn't I use this CoArbitrary instance for something?
You can't decide whether two functions are equal. But you can test it!
Two functions are equal if and only if for any input they give the same output. This is a testable property: generate some inputs, compare the outputs. If they are different, you've got a counter-example.
Notice that the
Bool
result in the type of "decidable equality"(==) :: X -> X -> Bool
is replaced withProperty
in what we might call "testable equality"funEquality :: X -> X -> Property
. It's actually not necessary to useproperty
and convert the functiona -> Property
(ora -> Bool
if you use(==)
) toProperty
, but the types look neater that way.We need to rewrite the function corresponding to the associativity property, since we no longer rely on
Eq
.Edit: at this point we're actually still missing a
Show
instance forCombine
. QuickCheck provides a wrapperFun
to both generate and show functions as counterexamples.