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

见布伦特Yorgey的Typeclassopedia：

不像一些其他类型的课程，我们会遇到，给定类型有函子的最多一个有效的实例。这个can be proven通过free theorem为fmap的类型。实际上，对于许多数据类型，Functor实例是GHC can automatically derive。

Answer 2

“什么时候GHC可以派生一个函子实例，什么时候不能呢？”

当我们有故意的循环数据结构。类型系统不允许我们表达强制循环的意图。 因此，ghc 可以从派生出一个实例，类似到我们想要的，但不一样。

---

通函数据结构 可能是在函子应实行不同方式的唯一情况。但是再一次，它会具有相同的语义。

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：

在哈斯克尔社区，该帖“绑结”是已知的这种数据结构。它是关于数据结构在语义上无限的，因为它们循环。它们只消耗有限的内存。例如：给定ones = 1:ones，我们将具有twos这些语义上等价的实现：

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

如果我们遍历（第一n的元素）twos并且仍然具有到开始该列表的参考，这些实施方案在速度不同（每次评估1 + 1 vs只有一次）和内存消耗（O（n）vs O（1））。