Difference of constraints in Semigroup and Monoid instances

Question

Why Monoid instance need (Ord a, Ord b) constraints while Semigroup instance doesn't?

Does this depend on the Category.Constrained class or the use of GADT to define the data type?

{-# LANGUAGE GADTs, TypeFamilies, ConstraintKinds, StandaloneDeriving #-}

module Question3 where

import Control.Category.Constrained as CC
import Data.Set as S
import Data.Map as M

data RelationMS a b where
  IdRMS :: RelationMS a a
  RMS :: (Ord a, Ord b) => Map a (Set b) -> RelationMS a b 
deriving instance (Show a, Show b) => Show (RelationMS a b)

RMS mp2 `compRMS` RMS mp1
  | M.null mp2 || M.null mp1 = RMS M.empty
  | otherwise = RMS $ M.foldrWithKey 
        (\k s acc -> M.insert k (S.foldr (\x acc2 -> case M.lookup x mp2 of
                                                    Nothing -> acc2
                                                    Just s2 -> S.union s2 acc2
                                         ) S.empty s
                                ) acc
        ) M.empty mp1

instance Category RelationMS where
    type Object RelationMS o = Ord o
    id = IdRMS
    (.) = compRMS

instance Semigroup (RelationMS a b) where 
    RMS r1 <> RMS r2 = RMS $ M.foldrWithKey (\k s acc -> M.insertWith S.union k s acc) r1  r2 

instance (Ord a, Ord b) => Monoid (RelationMS a b) where
    mempty = RMS $ M.empty
    mappend = (<>)

leftaroundabout leftaroundabout · Accepted Answer · 2019-06-03T15:18:16

This certainly has nothing to do with the category instances.

The Semigroup instance does, at least conceptually, also require Ord, however you've already packed that in the GADT (except in the Id case, where it's not needed because it's trivial), so there's no need to mention the constraint in the instance head.

For mempty however, you don't have a RelationMS value at hand from which you could read out the (Ord a, Ord b) constraints. Quite the opposite: you need to provide these constraints, because you're now trying to wrap up such a GADT! That's why the Monoid instance needs the constraint in its head, but the Semigroup one doesn't.

Difference of constraints in Semigroup and Monoid instances

2 Answers