函子实例是唯一的吗？

Question

我在想，在Haskell中，Functor实例在多大程度上是由函子法则唯一确定的。

由于ghc可以为至少“常规”数据类型派生Functor实例，因此它们在很多情况下至少是唯一的。

为了方便起见，Functor定义和函子法则如下：

class Functor f where
  fmap :: (a -> b) -> f a -> f b

fmap id = id
fmap (g . h) = (fmap g) . (fmap h)

问题：

• 是否可以从假设 data List a = Nil | Cons a (List a) 是 Functor 实例出发推导出 map 的定义？如果是，为了实现这一点需要做出哪些假设？

• 是否有任何 Haskell 数据类型拥有多个满足函子定律的 Functor 实例？

• 在什么情况下 ghc 能够派生出一个 functor 实例，而在什么情况下则不能？

• 所有这些都取决于我们如何定义相等性吗？Functor 定律是以值相等性来表达的，然而我们并不要求 Functors 拥有 Eq 实例。那么这里有一些选择吗？

关于相等性，显然存在一种我称之为“构造函数相等性”的概念，它允许我们推理出对于任何类型为 a 的值，[a,a,a] 都与另一个值为 [a,a,a] 相等，即使类型 a 没有定义 (==)。所有其他有用的相等性概念可能都比这种等价关系粗略。但我怀疑 Functor 定律中的相等性更像是“推理相等性”关系，可以是应用程序特定的。对此有何想法？

- ErikR

---

“Either a b”可以有两种方式成为一个函子。同样的，(a, b)也可以。这些都是微不足道的例子，但我认为可能会有一些非微不足道的例子。 - Benjamin Hodgson

不行，使用类型柯里化的情况下，唯一实现它的方法是将 f 应用于 Right 值，否则不做任何操作。 - daniel gratzer

你说得对 - 我想这是_Haskell类型类_ Functor和_数学概念_ 'functor'之间冲突的一个焦点。 - Benjamin Hodgson

请参阅Haskell Functor implied law。 - Daniel Wagner

Answer 1

参见 Brent Yorgey 的类型类百科全书：

与我们遇到的其他某些类型类不同，一个给定的类型最多只有一个有效的Functor实例。这可以通过fmap类型的自由定理进行证明。实际上，GHC可以自动为许多数据类型派生Functor实例。

可以证明

fmap的类型的自由定理

GHC可以自动派生Functor实例

- Matt Fenwick

Answer 2

“ GHC 什么时候可以衍生出一个函子实例，什么情况下不行？”

当我们有意的循环数据结构时，类型系统无法表达我们强制循环的意图。因此，GHC 可以派生出一个与我们想要的类似但不完全相同的实例。

---

循环数据结构可能是唯一需要以不同方式实现 Functor 的情况。但再一次地，它将具有相同的语义。

data HalfEdge a = HalfEdge { label :: a , companion :: HalfEdge a }

instance Functor HalfEdge where
    fmap f (HalfEdge a (HalfEdge b _)) = fix $ HalfEdge (f a) . HalfEdge (f b)

---

编辑：

HalfEdges是计算机图形学、3D网格等领域中表示图形中无向边的结构。你可以在其中找到对于任意一端点的引用。通常，它们还会存储相邻HalfEdges、节点和面的更多引用。

newEdge :: a -> a -> HalfEdge a
newEdge a b = fix $ HalfEdge a . HalfEdge b

从语义上讲，不存在fix $ HalfEdge 0 . HalfEdge 1 . HalfEdge 2，因为边缘总是由正好两个半边组成。

---

编辑2：

在Haskell社区中，引用"Tying the Knot"被用于此类数据结构。它涉及到的数据结构是语义上无限的，因为它们是循环的。它们仅消耗有限的内存。例如：给定ones = 1:ones，我们将得到这些语义上等效的实现twos：

twos = fmap (+1) ones
twos = fix ((+1)(head ones) :)

如果我们遍历（前n个元素）twos并且仍然有对该列表开头的引用，这些实现在速度（每次计算1 + 1 vs仅一次）和内存消耗（O（n）vs O（1））方面有所不同。

- comonad

---

只要你只遵循有限数量的边，一切都没问题。附：你不正确的函数实现当然也会产生无限对象！附言：如果这是运行时差异（顺便说一下，这取决于编译器实现），那么你应该在回答中说明。在这种情况下，我仍然建议使用另一种数据结构（仅包含两个实数值并提供循环访问），并给它一个正确的函数实例。结论：如果你的类型允许不支持的行为，从而浪费了 Haskell 最大的优势，那么你的程序就不是类型安全的！ - Johannes Gerer

@JohannesGerer 请了解一下结果值的记忆/缓存。这与Haskell的类型系统或惰性（非严格性）无关，也不依赖于编译器。惰性并不神奇，除了显而易见的记忆之外，它不支持额外的记忆。如果您有两个相互指向的对象，并沿着其无限遍历fmap函数，则将在相同的值上无限多次应用该函数，评估为无限个不同但等效的对象。只有当您没有保留对该列表头的引用时，它们才会被垃圾回收。 - comonad

阅读有关CoData（您称之为无限对象）与Data（有限对象）的内容。在命令式语言中，您可以拥有可以引用自身的数据结构（直接或间接递归），例如图形中的节点。在严格的纯函数语言中，您只有有限的树或dag数据结构。在非严格（您称之为惰性）函数语言中，您可以具有递归引用自身和CoData（如无限列表）的数据结构。很久以前曾经有过没有monads的时代……不确定是Miranda还是Haskell1.0……有main :: String→String。 - comonad

好吧，可惜到了这个地步，你实际上并没有回复我说的话。（你可能也会对我有同样的看法）。我们可以互相学习，并且应该试着向世界展示Haskell是一门多么优秀的语言。如果你有兴趣进行建设性的对话，我已经给你发了一封电子邮件。 - Johannes Gerer

听起来不错。我想我们的思维方式相似，只是因为有不同的基本假设而导致了不同的观点。 - comonad