为何MSet无法成为Functor的合法实例？

数据类型与需求说明 #

我定义了表示多重集合的自定义类型MSet：

data MSet a = MSet [(a, Int)]

其中每个元组(a, Int)代表元素a及其重数（正整数），该类型需维持以下不变量：

• 列表中无重复元素（不存在两个a值相同的元组）
• 添加已存在元素时，需将重数相加

需要实现函数mapMSet：

mapMSet :: (a -> b) -> MSet a -> MSet b

该函数将给定函数f :: a -> b应用于MSet的所有元素，若f将不同元素映射为同一值，需合并重数以维持MSet的不变量。例如：

ms = MSet[(1,2),(2,3)]
f x = 1

mapMSet f ms的结果为：

MSet [(1,5)]

Functor相关困惑 #

我了解Functor类型类要求实现fmap：

fmap :: (a -> b) -> f a -> f b

且fmap必须满足两条函子定律：

• 恒等律：fmap id = id
• 复合律：fmap (f . g) = fmap f . fmap g

我困惑于为何无法用mapMSet作为fmap为MSet定义合法的Functor实例，已知问题与维持MSet的不变量相关，特请教以下问题：

1. 维持不变量（合并重复项）如何与函子定律冲突？
2. 若不在mapMSet中合并重复项会怎样？
3. 带有结构不变量的数据类型能否成为合法的Functor实例？

两种情况的分析 #

情况1：mapMSet合并重复项 #

此场景下会违反恒等律。例如：

ms = MSet [(1, 1), (1, 2)] 

对ms应用fmap id：

fmap id ms
= mapMSet id ms
= MSet [(1,3)] -- 合并重复项后

此时ms != fmap id ms，违反恒等律，但结果符合MSet的不变量。

情况2：mapMSet不合并重复项 #

此场景下恒等律与复合律均成立，mapMSet表现得像标准fmap，但结果可能违反MSet的不变量。例如：

f x = 1 -- 将所有元素映射为1
g x = id -- 恒等函数

应用fmap (f . g)：

fmap (f . g) ms
= mapMSet (f . g) ms
= MSet [(1,1),(1,2)] -- 存在重复项！

结果不符合MSet规范，但复合律成立：

fmap (f . g) ms == fmap f (fmap g ms)

内容的提问来源于stack exchange，提问作者Daniele Caliandro