8

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!

brooksbp
  • 1,886
  • 4
  • 16
  • 17
  • 1
    The best intuition I can give you is: if you think something is a functor, make it a functor instance. It will be useful eventually. You **will** want to apply fmap to it. GHC makes it really easy, with the DeriveFunctor extension. – nomen Jun 05 '14 at 00:22

1 Answers1

10

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

daniel gratzer
  • 52,833
  • 11
  • 94
  • 134
  • Can you elaborate on the lazy aspect? For example, if I do `fmap f bar` I would think it goes like this: f 2, map f [foo] .. f 1, map f [bar] .. f 2, map f [foo] .. infinite loop. – brooksbp Jun 05 '14 at 00:40
  • @brooksbp Since Haskell is lazy by default, it won't enter the infinite loop until you force it to. For example, you can easily do things like `fmap (+1) [1..]`, where `[1..]` is an infinite list of `Integer`s, and Haskell will handle it just fine until you do something like ask for its length, or what the last element is. – bheklilr Jun 05 '14 at 00:45
  • @bheklilr Even in a strict language, I think it won't go into infinite loop until we execute that. Isn't so? – Sibi Jun 05 '14 at 00:47
  • So... if I `seq (fmap f bar)` I end up in an infinite loop? And I can't define `fmap` as awesomely as jozefg did above? Instead, I have to implement a terminating graph traversal algorithm? Is this what you mean by "it works just as well as any knot-tied graph representation would" jozefg? Are there any good articles related to this problem of representing graphs in Haskell? – brooksbp Jun 05 '14 at 00:50
  • @brooksbp If you fully evaluate the `foo` or `fmap f foo` you'll loop since their both infinite. And you need to phrase this graph algorithm so it can be used lazily if you want this behavior, otherwise you'll have the same problem with/without calling it `fmap`. – daniel gratzer Jun 05 '14 at 01:03
  • @brooksbp, no, `seq (fmap f bar)` isn't going to infinite loop either. You don't need to write a terminating graph algorithm, just a corecursive one (one that continues to produce information as you ask for it). I suggest you play around a bit with infinite lists and `jozefg`'s `Graph` type and `Functor` instance to develop your intuition for laziness. – luqui Jun 05 '14 at 01:19
  • @luqui sorry `seq` was bad example, I didn't fully understand. A better example: `let foo = Node 1 [Node 2 [foo]] ; putStrLn $ show $ fmap (\x -> x) foo` will livelock. – brooksbp Jun 05 '14 at 02:27
  • @jozefg So, where do you draw the line between 1) writing simpler code that could possibly livelock (e.g. your Functor instance for Graph) and 2) writing more complex code but it guarantees termination even for "knot-tied" / looped data? Your Functor instance is awesome because it showed me how simple it could be, but I am not seeing why you would ever want to write a Graph traversal a la Functor like that.. maybe if you could make the assumption that the input was a Graph in the form of a spanning tree aka no loops? – brooksbp Jun 05 '14 at 02:38
  • @brooksbp, try it and see. I claim it will not. – luqui Jun 05 '14 at 02:38
  • @brooksbp, try it without the `fmap` – luqui Jun 05 '14 at 02:39
  • Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/55104/discussion-between-luqui-and-brooksbp). – luqui Jun 05 '14 at 02:42
  • ...which means that the fmap didn't cause the livelock. – AndrewC Jun 05 '14 at 08:08