Разница ограничений в экземплярах полугрупп и моноидов - PullRequest
Новая
       21

Разница ограничений в экземплярах полугрупп и моноидов

2 голосов
/ 03 июня 2019

Почему экземпляру Monoid нужны ограничения (Ord a, Ord b), а экземпляру Semigroup - нет?

Зависит ли это от класса Category.Constrained или от использования GADT для определения типа данных? 

{-# 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 = (<>)

Ответы [ 2 ]

8 голосов
/ 03 июня 2019

Это, безусловно, не имеет никакого отношения к экземплярам категории.

Экземпляр Semigroup требует, по крайней мере, концептуально, также Ord, однако вы уже упаковали это в GADT (за исключениемслучай Id, где он не нужен, потому что он тривиален), поэтому нет необходимости упоминать ограничение в заголовке экземпляра.

Для mempty однако у вас нет значение RelationMS под рукой, из которого вы могли бы прочитать ограничения (Ord a, Ord b).Скорее наоборот: вам нужно предоставить эти ограничения, потому что вы сейчас пытаетесь свернуть такой GADT!Вот почему экземпляр Monoid нуждается в ограничении в своей голове, а экземпляр Semigroup - нет.

2 голосов
/ 03 июня 2019

Зачем экземпляру Monoid нужны ограничения (Ord a, Ord b), а экземпляру Semigroup нет?

Попробуйте удалить ограничение, и GHC скажет вам, почему. 

ac.hs:33:14: error:
    • No instance for (Ord a) arising from a use of ‘RMS’
      Possible fix:
        add (Ord a) to the context of the instance declaration
    • In the expression: RMS $ M.empty
      In an equation for ‘mempty’: mempty = RMS $ M.empty
      In the instance declaration for ‘Monoid (RelationMS a b)’
   |
33 |     mempty = RMS $ M.empty
   |

Итак, RMS требуется Ord a?Вы сказали: 

  RMS :: (Ord a, Ord b) => Map a (Set b) -> RelationMS a b

Итак, да.

...