任何与fmap具有相同多态类型的函数都必须等于fmap吗？

Question

我正在阅读 Haskell 的第二版编程，我遇到了这句话：

... there is only one way to make any given parameterised type into a functor, and hence any function with the same polymorphic type as fmap must be equal to fmap.

不过我觉得这不对。我可以看到每个 Functor 类型只有一个 valid 定义 fmap ，但我肯定可以定义任意数量的 [=14 类型的函数=] 哪个不等价？

为什么会这样？或者，这只是作者的错误？

Answer 1

这是一个错误。以下是一些与 fmap 类型相同的函数示例，用于不是 fmap:

的列表

\f -> const []
\f -> concatMap (replicate 2 . f)
\f -> map (f . head) . chunksOf 2
\f -> map f . reverse

还有很多。一般来说，给定一个函数 ixf 从列表长度到不大于该长度的数字列表（即列表中的有效索引），我们可以构建

maybeIt'sFmapLol :: (Int -> [Int]) -> (a -> b) -> [a] -> [b]
maybeIt'sFmapLol ixf elemf xs = [map elemf xs !! ix | ix <- ixf (length xs)]

使用 Int 的适当惰性变体来处理无限列表。可以为其他类似容器的仿函数构建类似的函数模式。

Answer 2

你误读了作者的意思。

...any function with the same polymorphic type as fmap...

这意味着，任何具有签名

的函数

Functor f => (a -> b) -> f a -> f b

必须等同于 fmap。（当然，除非您允许最低值。）

这个说法是正确的；如果您尝试定义这样一个函数，则可以很容易地看到：因为除了它是一个函子之外，您对 f 一无所知，因此获得非 ⊥ f b 值的唯一方法是通过 fmapping f a 一个。

引用中的逻辑含义不太明确：

there is only one way to make any given parameterised type into a functor, and hence any function with the same polymorphic type as fmap must be equal to fmap.

我认为作者的意思是有，因为Functor f => (a -> b) -> f a -> f b函数必须调用fmap，并且因为fmap总是唯一参数化类型的有效函子映射，任何 Functor f => (a -> b) -> f a -> f b 实际上也会遵守函子法则，即它将是 the fmap.

我同意“因此”的措辞有点糟糕，但原则上引用是正确的。

Answer 3

我认为引用是指这种情况。假设我们定义了一个参数化类型：

data F a = .... -- whatever

为此我们不仅可以编写一个，还可以编写两个 fmap 实现

fmap1 :: (a -> b) -> F a -> F b
fmap2 :: (a -> b) -> F a -> F b

满足函子定律

fmap1 id = id
fmap1 (f . g) = fmap1 f . fmap1 g
fmap2 id = id
fmap2 (f . g) = fmap2 f . fmap2 g

根据这些假设，我们有 fmap1 = fmap2。

这是与 fmap 的多态类型关联的 "free theorem" 的理论结果（请参阅 Lemma 1 下的注释）。从实用上讲，这确保了我们从 deriving Functor 获得的实例是唯一可能的实例。

任何与fmap具有相同多态类型的函数都必须等于fmap吗？

Any function with the same polymorphic type as fmap must be equal to fmap?

haskell

functor