Generating arbitrary `JointList` with concrete types

I am writing tests for one of the exercises of this course homework.

In this homework the following data type is defined:

data JoinList m a = Empty
              | Single m a
              | Append m (JoinList m a) (JoinList m a)
              deriving (Eq, Show)

To carry out the tests, I would like to generate random JointList elements using QuickCheck, in such a way that m is a Monoid that carries information about the number of elements in the list. This is, I would like to define arbitrary as follows:

instance (Sized m0, Monoid m0, Arbitrary a0) => 
    (Arbitrary (JoinList m0 a0)) where
  arbitrary = oneof [ return Empty
                    , liftM (Single (Size 1)) arbitrary
                    , liftM2 (doAppend) arbitrary arbitrary
                    ]
              where doAppend jxs jys = Append (tag jxs <> tag jys) jxs jys

where <> is defined as the sum of the sizes of the two operands, and the Sized class is defined as follows:

newtype Size = Size Int
    deriving (Eq, Ord, Show, Num)

class Sized a where
  size :: a -> Size

However, this results in the following compiler error:

Couldn't match expected type ‘m0’ with actual type ‘Size’
  ‘m0’ is a rigid type variable bound by
       the instance declaration at test/Spec.hs:35:10
Relevant bindings include
  arbitrary :: Gen (JoinList m0 a0) (bound at test/Spec.hs:36:3)
In the first argument of ‘Single’, namely ‘(Size 1)’
In the first argument of ‘liftM’, namely ‘(Single (Size 1))’

Is there a way to achieve this?

Solution

I suspect that rather than supporting producing random lists annotated by user-chosen instances of Sized, you really intended just to support producing random lists annotated by the specific type Size. You can modify your Arbitrary instance declaration this way to do that:

instance (m ~ Size, Arbitrary a) => Arbitrary (JoinList m a) where
    -- as before

You will want to declare the obvious Monoid instance for Size:

instance Monoid Size where
    mempty  = 0
    mappend = (+)

You can skip declaring the Sized class entirely.

Alternately, if you really did intend to produce random lists annotated by user-chosen instances, then you need the Sized class to provide a way to produce annotations, rather than consuming them as the class currently provides. Thus, for example:

class Sized a where size :: Int -> a
instance Sized Size where size = Size

Then the Arbitrary instance declaration would remain the same, but would replace Size with size in the production for Single.