G'day Federico.
Quoting Federico Brubacher
But how to do it with Natural transformations ???
Step back for a moment, and forget about sum. This is important because natural transformations are bound up with polymorphism. Think of the category theory definition of "natural transformation". Suppose that F and G are functors. Then a natural transformation eta : F -> G is a map that takes an object (in Haskell, that's a type; call it a) and returns a morphism from F(a) to G(a). It then has to satisfy a certain coherence condition, which we'll get to in a moment. So what you'd like is something like this: eta :: (some type a) -> (F a -> G a) where F and G are functors. Note that this type would be wrong: eta :: a -> (F a -> G a) because the first argument of eta would be a _value_ of type a. We want to pass in an actual type, instead. It turns out that Haskell does this implicitly. The real type of eta is this: eta :: forall a. F a -> G a and in the implementation, the "forall a" indicates that a hidden argument which represents the type "a" is passed to eta first. Sorry if I didn't explain that well. Let me know if I need to expand on that. OK, now, the coherence condition. If you translate it into Haskell, it looks like this. For any f :: A -> B, then: fmap f . eta = eta . fmap f If you haven't seen fmap before, it is the same as the "map" operation on lists, but generalised to arbitrary functors. There is an instance, for example, for Maybe: fmap f (Just x) = Just (f x) fmap f Nothing = Nothing And fmap on lists, of course, is just map. Note that in the coherence condition, the two instances of fmap are different: fmap_G f . eta = eta . fmap_F f Now, here's the interesting bit. Let's just look at lists for a moment. Suppose you had a function of this type: something :: [a] -> [a] It has the type of a natural transformation, but to be a natural transformation, you need to satisfy the additional condition: map f . something = something . map f How could you guarantee that? Look at the type again, this time with the explicit "forall": something :: forall a. [a] -> [a] What does "forall" mean? Well, it means that a can be _any_ type. Anything at all. So the "something" function can't depend in any way on what "a" is. So all that "something" can do is rearrange the skeleton of the list. It could be a fancy "id", it could reverse the list, it could duplicate some elements, it could drop some elements. But whatever it does, it can't make the decision about what to do based on the actual values stored in the list, because it can't inspect those values. Please convince yourself of this before reading on. (Aside: Actually, there is one thing that "something" can do with an arbitrary element in the list, and that's perform "seq" on it. This complicates things considerably, so we'll ignore it.) Now, this means that you could replace the values in the list with something else, and "something" would have to do essentially the same thing. Which is just a fancy way of saying this: map f . something = something . map f In other words, "something" is a natural transformation. Without knowing anything about the implementation of "something", you know it's a natural transformation just because it has the type of a natural transformation! And, by the way, this reasoning doesn't just work for lists. If F and G are functors, then any function eta :: F a -> G a satisfies: fmap f . eta = eta . fmap f In Haskell, if it looks like a natural transformation, then it is a natural transformation. How cool is that? And, by the way, this is a great bit of intuition, as well. I always used to wonder what's so "natural" about a natural transformation in category theory. Now you know: a natural transformation transforms (F a) into (G a) without looking at the a's. Cheers, Andrew Bromage