How to define a superclass constraint for free monoids?

Question

Consider the following type class for free monoids.

class FreeMonoid f where
    inj :: a -> f a
    univ :: Monoid m => (a -> m) -> f a -> m

inj injects a value into the free monoid, and univ is the universal property of free monoids.

Instances of this class should satisfy the following laws.

• Identity: univ f . inj = f
• Free empty: univ f mempty = mempty
• Free append: univ f (m <> n) = univ f m <> univ f n

Note that if f is an instance of FreeMonoid then (f a) must be an instance of Monoid. Otherwise, the last two laws don't make sense. So, how do I specify this constraint? Here's what I tried.

class Monoid (f a) => FreeMonoid f where
    inj :: a -> f a
    univ :: Monoid m => (a -> m) -> f a -> m

Not having this constraint makes it inconvenient to use this class. For example, consider the following function.

mapFreeMonoid :: (FreeMonoid f, Monoid (f b)) => (a -> b) -> f a -> f b
mapFreeMonoid f = univ (inj . f)

Since f is an instance of FreeMonoid, we shouldn't have to specify the Monoid (f b) constraint. Ideally, we should be able to define the above function as follows.

mapFreeMonoid :: FreeMonoid f => (a -> b) -> f a -> f b
mapFreeMonoid f = univ (inj . f)

Answer 1

You can try experimenting with the QuantifiedConstraints extension.

class (forall a. Monoid (f a)) => FreeMonoid f where
   ...

Your code then compiles without the additional constraint.

mapFreeMonoid :: FreeMonoid f => (a -> b) -> f a -> f b
mapFreeMonoid f = univ (inj . f)

Answer 2

You may use the QuantifiedConstraints extension as chi’s answer said. Take a look at the analogous definition for free categories, the CFree constraint here.