Functors and non-inductive types

Question

I am working on the Functors section of Typeclassopedia .

A simple intuition is that the Functor is a “container” of some kind, as well as the ability to evenly apply a function to each element in the container.

OK So functors seem quite natural for inductive types like lists or trees.

Functors also seem pretty simple if the number of elements is fixed at a low number. For example, perhaps you just need to worry about “nothing” or “just” - about two things.

So, how would you do something like a graph that could have loops, an instance of Functor? I think a more generalized way of expressing this is how non-inductive types "fit into" functors?

---

The more I think about it, the more I understand that inductive / non-inductive does not really matter. Inductive types are easier to define fmap for ...

If I wanted to make the graph an instance of Functor, I would have to implement a graph traversal algorithm inside fmap; for example, you may have to use a helper function that will track visited sites. Right now I'm wondering why you need to define it as a Functor instead of just writing it as a function? For instance. map vs fmap for lists ...?

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

Answer 1

Well suppose you define such a graph

 data Graph a = Node a [Graph a] 

Then fmap defined exactly as you would expect

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

Now, if there is a loop, we would have to do something like

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

Now fmap is lazy enough that you can evaluate part of its result without forcing the rest of the calculations, so it works as well as any node-related graph representation!

In general, this is a trick: fmap lazy, so you can handle it the same way you handle any non-inductive values ​​in Haskell (: carefully).

In addition, you must define fmap against random other functions, since

• fmap is a good, well-known API with rules
• There are things waiting for Functor s in your container
• You can abstract the other bits of your program so that they depend on the Functor and not on your schedule.

In general, when I see that something is a functor, I think: “Ah, great, I know how to use it,” and when I see

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

I'm a little worried that this will do unexpected things.