函子和非归纳类型

Question

我正在学习Typeclassopedia中有关Functor的部分。

一个简单的直觉是，Functor表示一种“容器”，以及能够统一地将函数应用于容器中每个元素的能力。

好的。因此，对于诸如列表或树之类的归纳类型，functor似乎非常自然。

如果元素的数量固定在较低的数量上，functor也会变得非常简单。例如，在Maybe中，您只需要关心“Nothing”或“Just a”-两件事情。

那么，如何使像图这样的可能具有循环的数据结构成为Functor的实例？更广义的说法是，非归纳类型如何“适合”Functor中？

---

我越想越清楚的是，归纳/非归纳并不重要。归纳类型只是更容易定义fmap...

如果我想将图作为Functor的实例，我必须在fmap内部实现图遍历算法；例如，它可能需要使用一个帮助函数来跟踪已访问的节点。此时，我现在在思考为什么要将其定义为Functor而不是仅编写一个函数？例如，对于列表，map与fmap...？

我希望有经验、战斗经历和伤疤的人能够阐明一些问题。谢谢！

- brooksbp

---

我能给你的最好建议是：如果你认为某个东西是一个函子，那就将其变成一个函子实例。这样做最终会很有用。你一定会想要对它应用fmap函数。GHC通过DeriveFunctor扩展使得这一过程非常简单。 - nomen

Answer 1

好的，假设你定义了一个像这样的图：

data Graph a = Node a [Graph a]

那么fmap的定义就像你预期的那样精确定义了。

instance Functor Graph where
  fmap f (Node a ns) = Node (f a) (map (fmap f) ns)

现在，如果有一个循环，那么我们将不得不做类似于下面的事情。

foo = Node 1 [bar]
bar = Node 2 [foo]

现在，fmap足够惰性了，你可以评估其部分结果而不强制执行其余计算，因此它与任何打结图表示一样有效！

通常的技巧是：fmap是惰性的，因此您可以像处理Haskell中的任何非归纳值一样处理它的结果（：小心处理）。

此外，您应该定义fmap与其他随机函数之间的区别，因为：

1. fmap是一个良好的、众所周知的具有规则的API
2. 您的容器现在与期望Functor的东西相匹配
3. 您可以将程序的其他部分抽象出来，使它们依赖于Functor，而不是您的图形

通常，当我看到某物是一个函子时，我就会想：“啊，太棒了，我知道该如何使用它”，而当我看到

superAwesomeTraversal :: (a -> b) -> Foo a -> Foo b

我有点担心这会做出意想不到的事情..

- Daniel Gratzer

---

那么，如果我执行 seq (fmap f bar)，会陷入无限循环吗？我不能像上面的 jozefg 那样定义 fmap 吗？相反，我必须实现一个终止的图遍历算法吗？这就是你所说的“它的效果与任何打结图表示法一样好”，jozefg？有没有关于在 Haskell 中表示图的问题的好文章？ - brooksbp

@jozefg，那么你在编写更简单的代码（例如Graph的Functor实例）可能会出现活锁和编写更复杂的代码之间如何划分界限，但它保证了即使是“打结”/循环数据也能终止？你的Functor实例非常棒，因为它向我展示了它可以多么简单，但我不明白为什么你会想要编写类似Functor的Graph遍历..也许如果你能做出这样的假设，即输入是一个形式为生成树的图，即没有循环，那么你就可以这样做？ - brooksbp

@brooksbp，你可以试一下看看。我断言它不会这样做。 - luqui

让我们在聊天中继续这个讨论：http://chat.stackoverflow.com/rooms/55104/discussion-between-luqui-and-brooksbp。 - luqui

这意味着fmap没有引起活锁。 - AndrewC