[Haskell-begin] Exercises for beginners and Natural Tansformations

[ajb at spamcop.net]

G'day Federico.

Quoting Federico Brubacher <fbrubacher at gmail.com>:

> 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