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 = (<>)
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.