Map数据结构实现：此Functor实例存在什么问题？

嘿，咱们来一步步拆解这段代码里的问题：

首先先把给出的代码贴出来方便对照：

data Map k v = Map [(k, v)] deriving (Show, Eq)
instance Functor (Map a) where
    fmap _ (Map []) = Map []
    fmap f (Map xs) = Map xs' where xs' = map (\(k, v) -> (f k, v)) xs

1. 完全违背Functor的核心语义 #

Functor的设计初衷是让我们能映射容器内部的值，对于Map k v这种键值对容器来说，fmap应该用来批量修改所有v类型的「值」，而不是k类型的「键」。但这段代码里，fmap把函数f硬生生作用到了键k上，完全搞反了操作对象。

2. 类型签名不合法，编译器直接报错 #

从Haskell类型系统的角度看，Functor的fmap必须遵循固定签名：

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

对于instance Functor (Map a)来说，f对应Map a，b对应Map的第二个类型参数v，也就是说fmap的合法类型应该是：

fmap :: (v -> v') -> Map a v -> Map a v'

但给出的代码里，fmap把函数应用到了a（键的类型）上，实际类型变成了：

fmap :: (a -> a') -> Map a v -> Map a' v

这完全不符合Functor的类型要求，编译器会直接拒绝这个实例。

3. 即便忽略类型问题，也违反Functor定律 #

假设我们强行绕开类型检查，这个实现也不满足Functor的基本定律：

• 恒等定律：fmap id = id。虽然id k等于k，但fmap id会遍历所有键值对重新构造一遍（只是键没变），和id直接返回原Map的语义并不一致；
• 组合定律：fmap (f . g) = fmap f . fmap g。就算这个定律看起来在键的操作上成立，但这根本不是Functor应该做的事——Functor的组合应该针对值的变换，而非键的修改。

正确的Functor实例参考 #

给你一个符合要求的实现，它把函数正确应用到值上：

instance Functor (Map k) where
    fmap _ (Map []) = Map []
    fmap f (Map xs) = Map (map (\(k, v) -> (k, f v)) xs)

内容的提问来源于stack exchange，提问作者barnabas markus