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?
newtype Combine' fun a b = Combine (fun a b); type Combine = Combine' (->); type Combine_Test = Combine' Fun
(or create a distinct type replicating the structure but replacing->
withFun
) – user2407038quickCheck
on the whole, reducing functions using lambda calculus can generally prove equality. – Eli Sadoff