CoArbitrary in Haskell

Question

I am working through the Haskell Book and have come to the point of writing an Arbitrary instance for newType Comp. The code is below

instance Show (Comp a) where
    show f = "Unicorns!!"

newtype Comp a =
    Comp { unComp :: (a -> a) }

instance (Semigroup a) => S.Semigroup (Comp a) where
    (Comp fx) <> (Comp fy) = Comp (fx . fy)

instance (CoArbitrary a, Arbitrary a) => Arbitrary (Comp a) where
    arbitrary = do
        f <- Test.QuickCheck.arbitrary
        return (Comp f)

type CompAssoc = String -> Comp String -> Comp String -> Comp String -> Bool

compAssoc :: (S.Semigroup a, Eq a) => a -> Comp a -> Comp a -> Comp a -> Bool
compAssoc v a b c = (unComp (a <> (b <> c)) $ v) == (unComp ((a <> b) <> c) $ v)

and tested with

main :: IO ()
main = do
    quickCheck (compAssoc :: CompAssoc)

My question revolves around the Arbitrary instance. It is generating a function to be passed to return (Comp f). I understand (though not fully why) that this has to be scoped to CoArbitrary. But if that thing passed to return (Comp f) is CoArbitrary, how can it also be Arbitrary? I guess it seems to be like these constraints both refer to the pass/return type of the function and the function itself. I'm a little confused.

Answer 1

This is a beginner's, high-level, very probably incorrect in the underlying details explanation of the relationship between Arbitrary and CoArbitrary.

The article https://begriffs.com/posts/2017-01-14-design-use-quickcheck.html gives you a better explanation but it uses Applicative and Functor and I haven't gotten there yet as I am still on the SemiGroup chapter of "The Haskell Book".

If you want to generate a function from a -> b, b must have an instance of Arbitrary. We're going to be generating random stuff anyways, so we need a Gen b as usual. But we need to vary this b just like a normal function would, that is, in the sense of if I pass a different value to a function like double, I'd expect a different response. But how can we vary a generator based on some random a? Well, if we think about the way we generate random bs in the first place, it has to do with numbers. I.e. if I want a random b (say, Int), I just generate a random number. Easy peasy. Random string? Start with random numbers, convert them to ASCII chars. Same with any other data type you want, and quickcheck provides a lot of Arbitrary instances that do just that.

OK, so at the base it is numbers. We could change those numbers by getting some other number and then, say, multiplying/subtracting/adding/dividing. Or any other math operation. But how do we get that other number? That's where CoArbitrary comes in! If I mark a type as needing to have an instance of CoArbitrary, effectively I am saying "I need to be able to reduce your type down to a number so that I can vary (add/mult/etc) the Generator for type b. So if type a is a string, for ex., reduce that string to a number, pass it to the gen for type b in order to let the Gen for type b do the mult/add/etc operation on the number(s) it would use to generate a b.