Haskell中Semigroup/Monoid实例重叠问题排查与解决

我尝试用Haskell结合Monoid类型类实现惰性构造非确定有限自动机（NFA），参考旧的F#实现编写了如下代码：

{-# LANGUAGE TypeSynonymInstances, FlexibleInstances #-}

module NFA where

data State = State Match State | Split State State | Final deriving (Show)
data Match = Any | Char Char | ... deriving (Show)

type StateF = State -> State

complete :: StateF -> State -> State
complete statef exit = statef exit

connect :: StateF -> StateF -> StateF
connect fst snd = complete fst . complete snd

empty :: StateF
empty = id

instance Semigroup StateF where
  (<>) = connect

instance Monoid StateF where
  mempty = empty

编译时出现实例重叠错误，我的疑问是：

• 我并未给State实现Monoid，为什么StateF（即State -> State）会和GHC.Base中的内置实例重叠？
• 有没有办法不用把StateF包装成新数据类型（比如data StateF = StateF (State -> State)）来解决这个问题？

编译器错误信息如下：

src\NFA.hs:10:10: error:
    * Overlapping instances for Semigroup StateF
        arising from a use of `GHC.Base.$dmsconcat'
      Matching instances:
        instance Semigroup b => Semigroup (a -> b) -- Defined in `GHC.Base'
        instance Semigroup StateF -- Defined at src\NFA.hs:10:10
    * In the expression: GHC.Base.$dmsconcat @(StateF)
      In an equation for `GHC.Base.sconcat':
          GHC.Base.sconcat = GHC.Base.$dmsconcat @(StateF)
      In the instance declaration for `Semigroup StateF'
   |
10 | instance Semigroup StateF where
   |          ^^^^^^^^^^^^^^^^

src\NFA.hs:10:10: error:
    * Overlapping instances for Semigroup StateF
        arising from a use of `GHC.Base.$dmstimes'
      Matching instances:
        instance Semigroup b => Semigroup (a -> b) -- Defined in `GHC.Base'
        instance Semigroup StateF -- Defined at src\NFA.hs:10:10
    * In the expression: GHC.Base.$dmstimes @(StateF)
      In an equation for `GHC.Base.stimes':
          GHC.Base.stimes = GHC.Base.$dmstimes @(StateF)
      In the instance declaration for `Semigroup StateF'
   |
10 | instance Semigroup StateF where
   |          ^^^^^^^^^^^^^^^^

src\NFA.hs:13:10: error:
    * Overlapping instances for Semigroup StateF
        arising from the superclasses of an instance declaration
      Matching instances:
        instance Semigroup b => Semigroup (a -> b) -- Defined in `GHC.Base'
        instance Semigroup StateF -- Defined at src\NFA.hs:10:10
    * In the instance declaration for `Monoid StateF'
   |
13 | instance Monoid StateF where
   |          ^^^^^^^^^^^^^

src\NFA.hs:13:10: error:
    * Overlapping instances for Monoid StateF
        arising from a use of `GHC.Base.$dmmappend'
      Matching instances:
        instance Monoid b => Monoid (a -> b) -- Defined in `GHC.Base'
        instance Monoid StateF -- Defined at src\NFA.hs:13:10
    * In the expression: GHC.Base.$dmmappend @(StateF)
      In an equation for `mappend':
          mappend = GHC.Base.$dmmappend @(StateF)
      In the instance declaration for `Monoid StateF'
   |
13 | instance Monoid StateF where
   |          ^^^^^^^^^^^^^

src\NFA.hs:13:10: error:
    * Overlapping instances for Monoid StateF
        arising from a use of `GHC.Base.$dmmconcat'
      Matching instances:
        instance Monoid b => Monoid (a -> b) -- Defined in `GHC.Base'
        instance Monoid StateF -- Defined at src\NFA.hs:13:10
    * In the expression: GHC.Base.$dmmconcat @(StateF)
      In an equation for `mconcat':
          mconcat = GHC.Base.$dmmconcat @(StateF)
      In the instance declaration for `Monoid StateF'
   |
13 | instance Monoid StateF where
   |          ^^^^^^^^^^^^^

解答 #

为什么会出现实例重叠？ #

GHC内置的Semigroup (a -> b)和Monoid (a -> b)实例采用结构匹配：只要类型是函数类型，就会被视为该实例的候选，与函数返回值类型是否满足Semigroup/Monoid约束无关——约束仅在实际使用该实例时才会检查。

你的StateF是State -> State的类型同义词，和a -> b的结构完全匹配，因此GHC会同时把内置实例和你自定义的实例视为有效候选。由于两个实例的匹配优先级相同，GHC无法自动选择，从而抛出重叠错误。这和State是否实现Semigroup/Monoid没有关系。

无需包装新数据类型的解决办法 #

方法1：启用OverlappingInstances扩展（不推荐）

添加OverlappingInstances扩展到文件顶部，GHC会优先选择更具体的实例（这里StateF比泛型的a -> b更具体）：

{-# LANGUAGE TypeSynonymInstances, FlexibleInstances, OverlappingInstances #-}

注意：该扩展在GHC 8.0之后被标记为过时，可能导致代码行为不可预料，尤其是在大型项目中，不推荐长期使用。

方法2：使用自定义运算符替代Monoid实例

放弃为StateF实现Semigroup/Monoid，直接使用自定义的组合逻辑：

-- 自定义NFA组合运算符
(<++>) :: StateF -> StateF -> StateF
(<++>) = connect

-- 空NFA
emptyNFA :: StateF
emptyNFA = id

这种方式完全避免了实例冲突，代码逻辑清晰，适合不需要依赖Monoid多态的场景。

推荐方案：使用newtype轻量包装（几乎无性能开销） #

虽然你提到不想包装，但newtype是Haskell处理这类问题的标准做法，编译后会被优化为原始函数类型，没有额外性能开销：

{-# LANGUAGE GeneralizedNewtypeDeriving #-}

module NFA where

data State = State Match State | Split State State | Final deriving (Show)
data Match = Any | Char Char deriving (Show)

newtype StateF = StateF (State -> State)

-- 运行StateF的辅助函数
runStateF :: StateF -> State -> State
runStateF (StateF f) = f

complete :: StateF -> State -> State
complete statef exit = runStateF statef exit

connect :: StateF -> StateF -> StateF
connect (StateF fst) (StateF snd) = StateF $ complete (StateF fst) . complete (StateF snd)

empty :: StateF
empty = StateF id

instance Semigroup StateF where
  (<>) = connect

instance Monoid StateF where
  mempty = empty

这种方式既符合Haskell的类型安全原则，又能正常使用Monoid的所有功能。

内容的提问来源于stack exchange，提问作者Good Night Nerd Pride