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.

Dihedron

You need the Coarbitrary constraint because the Arbitrary instance for functions requires it (to see why, look at how the Arbitrary instance is defined). However, there is nothing preventing a type from being both Arbitrary and Coarbitrary (indeed, most types have both instances). Why does this seem contradictory to you? – Hardset

I think I got confused with ` Arbitrary (Comp a)` I assumed the a was a type like in Comp String, as is used in CompAssoc, but the a here represents the function that you pass when constructing a Comp. You only use the concrete types when declaring functions. I guess I mixed up type constructors and data constructors. – Dihedron

Still confused. I changed the data constructor to Compp and it still requires the type constructor for the Arbitrary declaration. but the Type Constructor takes a type like String or whatever has a Semigroup instance. But here we are trying to generate functions, i.e. the thing passed to the data constructor. How can we limit Comp a (the data constructor to need CoArbitrary when it expects something like String which is something that has a Semigroup instance? – Dihedron

I'm afraid I don't see where your confusion lies. Is there a specific thing you are trying to accomplish which you are having trouble with? – Hardset

no, just understand why the test passes. I think I am understanding that by putting the CoArbitrary restraint on the a going to Comp, that is restraining the arg and return type of the unComp function, saying that I must be able to generate a function that takes a type a – Dihedron

or more broadly, if I were to not have CoArbitrary a as a restraint, but just Arbitrary a, then I can return a random a value. But when I add CoArbitrary a, the random value that is returned is a function that can accept an a. That is, CoArbitrary speaks about returning a function that accepts values of a certain type. – Dihedron

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.

Dihedron