如何为Free Group实现Eq实例（无需重复定义类型）？

可以不用额外定义公共的结构化类型来实现FreeGroup的Eq实例，核心思路是利用自由群的泛性质：两个自由群元素相等，当且仅当它们在任意群中的同态像都相等。我们只需要在实例实现内部构造一个可判定相等的“标准”自由群（即简化字表示），通过同态映射到这个群来判断相等性。

具体实现步骤 #

1. 内部构造简化字群 #

首先定义一个仅在Eq实例内部使用的简化字类型，实现Group和Eq实例，确保字的化简逻辑（相邻逆元自动抵消）：

-- 仅用于Eq实例内部的简化字类型：Bool标记正负（True为正，False为逆）
data ReducedWord a = EmptyWord | Append Bool a (ReducedWord a)
  deriving (Eq)

-- 辅助函数：添加元素时自动化简相邻逆元
reduce :: Eq a => Bool -> a -> ReducedWord a -> ReducedWord a
reduce sign x EmptyWord = Append sign x EmptyWord
reduce sign x (Append s y rest)
  | x == y && sign /= s = rest  -- 正负元素抵消，丢弃这一对
  | otherwise = Append sign x (Append s y rest)

instance Eq a => Semigroup (ReducedWord a) where
  EmptyWord <> w = w
  w <> EmptyWord = w
  Append sign x rest <> w = reduce sign x (rest <> w)

instance Eq a => Monoid (ReducedWord a) where
  mempty = EmptyWord

instance Eq a => Group (ReducedWord a) where
  inverse EmptyWord = EmptyWord
  inverse (Append sign x rest) = inverse rest <> Append (not sign) x EmptyWord

2. 实现FreeGroup的Eq实例 #

借助自由群的泛性质，将FreeGroup a的元素同态映射到上述简化字群，通过比较像的相等性来判断原元素相等：

instance Eq a => Eq (FreeGroup a) where
  x == y = runFree x embed == runFree y embed
    where
      -- 将生成元a映射为正的单元素简化字
      embed :: a -> ReducedWord a
      embed = Append True

原理说明 #

自由群的泛性质保证：若两个自由群元素在某个自由群的同态像相等，那么它们在所有群中的像都相等，即原元素本身相等。这里的ReducedWord a正是由a生成的自由群的标准实现——每个自由群元素对应唯一的简化字，因此同态到该群的像相等等价于原FreeGroup元素相等。

这种方式下，你的FreeGroup核心定义完全保持简洁，无需暴露任何结构化类型，也不用处理无效状态（化简逻辑在内部自动完成）。

内容的提问来源于stack exchange，提问作者Wheat Wizard