Functors and Non-Inductive Types

Question

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.

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.

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?

---

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...

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!

Answer 1

Well let's assume you define a graph like this

data Graph a = Node a [Graph a]

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]

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!

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).

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

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..