函子和非感应类型 [英] Functors and Non-Inductive Types

问题描述

我正在研究 Typeclassopedia 中有关函子的部分.

I am working through the section on Functors in the Typeclassopedia.

一个简单的直觉是，函子代表某种容器"，并且具有将功能均匀地应用于容器中每个元素的能力.

A simple intuition is that a Functor represents a "container" of some sort, along with the ability to apply a function uniformly to every element in the container.

好.因此，对于像列表或树这样的归纳类型，函子显得很自然.

OK. So, functors appear pretty natural for inductive types like lists or trees.

如果元素的数量固定为低数，则功能键也显得非常简单.例如，使用Maybe，您只需要担心什么都没有"或只需一个"就可以了.

Functors also appear pretty simple if the number of elements is fixed to a low number. For example, with Maybe you just have to be concerned about "Nothing" or "Just a" -- two things.

那么，您将如何制作像图这样的东西，它可能具有循环(例如Functor的实例)?我认为更概括地说，非归纳类型如何适合"函子?

So, how would you make something like a graph, that could potentially have loops, an instance of Functor? I think a more generalized way to put it is, how do non-inductive types "fit into" Functors?

我思考的越多，我越意识到电感性/非电感性并不重要.归纳类型只是更容易来定义 fmap 用于...

The more I think about it, the more I realize that inductive / non-inductive doesn't really matter. Inductive types are just easier to define fmap for...

如果要使图成为Functor的实例，则必须在fmap中实现图遍历算法；例如，可能必须使用帮助程序功能来跟踪所访问的节点.在这一点上，我现在想知道为什么要麻烦地将其定义为Functor，而不仅仅是将其编写为函数本身?例如.map与fmap的列表...?

If I wanted to make a graph an instance of Functor, I would have to implement a graph traversal algorithm inside fmap; for example it would probably have to use a helper function that would keep track of the visited nodes. At this point, I am now wondering why bother defining it as a Functor instead of just writing this as a function itself? E.g. map vs fmap for lists...?

我希望有经验，战争故事和伤疤的人能有所启发.谢谢！

I hope someone with experience, war stories, and scars can shed some light. Thanks!

推荐答案

让我们假设您定义了一个这样的图

Well let's assume you define a graph like this

data Graph a = Node a [Graph a]

然后 fmap 正是按照您期望的那样定义的

Then fmap is just defined precisely as you would expect

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

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

Now, if there's a loop then we'd have had to do something like

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

现在 fmap 足够懒惰，您可以在不强制执行其余计算的情况下评估其部分结果，因此它的工作原理与任何打结图表示法一样！

Now fmap is sufficiently lazy that you can evaluate part of it's result without forcing the rest of the computation, so it works just as well as any knot-tied graph representation would!

通常，这是窍门: fmap 是惰性的，因此您可以像对待Haskell中的任何非归纳值一样小心对待它的结果(:小心).

In general this is the trick: fmap is lazy so you can treat it's results just as you would treat any non-inductive values in Haskell (: carefully).

此外，您应该定义 fmap 与其他随机函数，因为

Also, you should define fmap vs the random other functions since

1. fmap 是一个很好的，有规则的知名API
2. 您的容器现在可以放置期望 Functor s
的东西了
3. 您可以抽象出程序的其他位，以便它们依赖于 Functor ，而不是您的Graph

1. fmap is a good, well known API with rules
2. Your container now places well with things expecting Functors
3. You can abstract away other bits of your program so they depend on Functor, not your Graph

通常，当我看到某物是一个函子时，我会认为啊，太好了，我知道该如何使用它"

In general when I see something is a functor I think "Ah wonderful, I know just how to use that" and when I see

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

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

I get a little worried that this will do unexpected things..

这篇关于函子和非感应类型的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！