Haskell arbitrary typeclass instance return type

Question

From the Haskell Book chapter on Monoids, I am writing quickcheck tests for

semigroupAssoc :: (Eq m, S.Semigroup m) => m -> m -> m -> Bool
semigroupAssoc a b c =
    (a S.<> (b S.<> c)) == ((a S.<> b) S.<> c)

type IdentAssoc = Identity String -> Identity String -> Identity String -> Bool

, invoking with

quickCheck (semigroupAssoc :: IdentAssoc)

Here is the arbitrary typeclass instance

instance (Arbitrary a) => Arbitrary (Identity a) where
    arbitrary = do
        a <- Test.QuickCheck.arbitrary
        return (Identity a)

My question is that in my arbitrary instance, I can return either (Identity a) or just a. (Identity a) is correct, but just a gives no compiler error and causes an infinite loop when run. Why is this?

Answer 1

Type inference changes the arbitrary call to point at the same instance we are defining right now, causing an infinite loop.

instance (Arbitrary a) => Arbitrary (Identity a) where
   arbitrary = do
        x <- Test.QuickCheck.arbitrary  -- this calls arbitrary @ a
        return (Identity x)

instance (Arbitrary a) => Arbitrary (Identity a) where
   arbitrary = do
        x <- Test.QuickCheck.arbitrary  -- this calls arbitrary @ (Identity a)
        return x

Every time we call a class method, the compiler infers which instance to call.

In the former case, the compiler infers x :: a (only this type makes the code type check!), hence it calls arbitrary @ a.

In the latter case, the compiler infers x :: Identity a (only this type makes the code type check!), hence it calls arbitrary @ (Identity a), causing the infinite loop.

Answer 2

If you write it as:

instance Arbitrary a => Arbitrary (Identity a) where
    arbitrary = do
        x <- arbitrary
        return x

(I renamed a to x to cause less confusion).

Then Haskell will do the type plumbing, and it will derive that, since you write return x, x must have type Identity a. And we are lucky, since there exists an arbitrary :: Arbitrary a => Gen a, the one we just defined (put in boldface here).

So that means that we have constructed an infinite loop. For instance in Java, it would look like:

public int foo(int x) {
    return foo(x);
}

Of course we can define such a function, and it is correct if we check the types. But there is of course no progress, since we keep calling the same function that will again call that function and again, and again,...

If you however write:

instance Arbitrary a => Arbitrary (Identity a) where
    arbitrary = do
        x <- arbitrary
        return Identity x

Haskell will derive that x has type a. And we are again lucky, since we have defined that Arbitrary a should hold, some somewhere there is an arbitrary :: Arbitrary a => Gen a function, but it is a different one (that's why I did not write it in boldface here), and that one will generate the value that we wrap in the Identity constructor.

Note that in the first example, we do not even have to add the Arbitrary a constraint: indeed:

instance Arbitrary (Identity a) where
    arbitrary = do
        x <- arbitrary
        return x

this compiles just fine, since we never generate an arbitrary a.