Functor实例是唯一的吗？

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)

问题：

• 可以从假设它是map的Functor实例开始得出data List a = Nil | Cons a (List a)的定义吗？如果是这样，为了做到这一点，必须做出哪些假设？
• 是否有任何Haskell数据类型有多个Functor实例满足函子定律？
• 什么时候ghc可以得到一个functor实例，什么时候不能呢？
• 所有这些都取决于我们如何定义平等吗？ Functor定律用值的相等表示，但我们不要求Functors有Eq实例。那么这里有一些选择吗？

关于平等，肯定有一种我称之为“构造函数平等”的概念，它允许我们推断[a,a,a]与任何类型的[a,a,a]的任何值都与a“相等”，即使a没有为其定义(==)。所有其他（有用的）平等概念可能比这种等价关系更粗糙。但我怀疑Functor法律中的平等更多是“推理平等”关系，并且可以是特定于应用的。有什么想法吗？

Answer 1

看Brent Yorgey的Typeclassopedia：

与我们将遇到的其他类型类不同，给定类型最多只有一个Functor的有效实例。这个can be proven通过free theorem为fmap的类型。实际上，GHC can automatically derive Functor实例适用于许多数据类型。

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，Nodes和Faces的引用。

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只比一次）和内存消耗（O（n）vs O（1） ））。