<div dir="ltr">@A. Wagner <div>Thanks for the tips ... about fold ... the idea that I have is that when ever possible use foldr instead of foldl as foldr works in normal order (lazy) while foldl does not. That's why I used that</div>
<div><br></div><div>@A. Bromage </div><div>Thanks great clarification on category theory , I think I will use your pointers on how Haskell imlements CT and do some examples, that's the part that I'm having trouble with, wraping my mind on how theory translates into practice.</div>
<div><br></div><div>Cheers from Uruguay</div><div>Federico </div><div><br><div class="gmail_quote">On Sat, Jul 19, 2008 at 11:41 AM, <<a href="mailto:ajb@spamcop.net">ajb@spamcop.net</a>> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
G'day Federico.<div class="Ih2E3d"><br>
<br>
Quoting Federico Brubacher <<a href="mailto:fbrubacher@gmail.com" target="_blank">fbrubacher@gmail.com</a>>:<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
But how to do it with Natural transformations ???<br>
</blockquote>
<br></div>
Step back for a moment, and forget about sum. This is important<br>
because natural transformations are bound up with polymorphism.<br>
<br>
Think of the category theory definition of "natural transformation".<br>
<br>
Suppose that F and G are functors. Then a natural transformation<br>
eta : F -> G is a map that takes an object (in Haskell, that's a type;<br>
call it a) and returns a morphism from F(a) to G(a). It then has to<br>
satisfy a certain coherence condition, which we'll get to in a moment.<br>
<br>
So what you'd like is something like this:<br>
<br>
eta :: (some type a) -> (F a -> G a)<br>
<br>
where F and G are functors.<br>
<br>
Note that this type would be wrong:<br>
<br>
eta :: a -> (F a -> G a)<br>
<br>
because the first argument of eta would be a _value_ of type a. We<br>
want to pass in an actual type, instead.<br>
<br>
It turns out that Haskell does this implicitly. The real type of eta<br>
is this:<br>
<br>
eta :: forall a. F a -> G a<br>
<br>
and in the implementation, the "forall a" indicates that a hidden<br>
argument which represents the type "a" is passed to eta first.<br>
<br>
Sorry if I didn't explain that well. Let me know if I need to expand<br>
on that.<br>
<br>
OK, now, the coherence condition. If you translate it into Haskell,<br>
it looks like this. For any f :: A -> B, then:<br>
<br>
fmap f . eta = eta . fmap f<br>
<br>
If you haven't seen fmap before, it is the same as the "map" operation<br>
on lists, but generalised to arbitrary functors. There is an instance,<br>
for example, for Maybe:<br>
<br>
fmap f (Just x) = Just (f x)<br>
fmap f Nothing = Nothing<br>
<br>
And fmap on lists, of course, is just map.<br>
<br>
Note that in the coherence condition, the two instances of fmap are<br>
different:<br>
<br>
fmap_G f . eta = eta . fmap_F f<br>
<br>
Now, here's the interesting bit. Let's just look at lists for a moment.<br>
Suppose you had a function of this type:<br>
<br>
something :: [a] -> [a]<br>
<br>
It has the type of a natural transformation, but to be a natural<br>
transformation, you need to satisfy the additional condition:<br>
<br>
map f . something = something . map f<br>
<br>
How could you guarantee that?<br>
<br>
Look at the type again, this time with the explicit "forall":<br>
<br>
something :: forall a. [a] -> [a]<br>
<br>
What does "forall" mean? Well, it means that a can be _any_ type.<br>
Anything at all. So the "something" function can't depend in any way<br>
on what "a" is. So all that "something" can do is rearrange the<br>
skeleton of the list. It could be a fancy "id", it could reverse the<br>
list, it could duplicate some elements, it could drop some elements.<br>
But whatever it does, it can't make the decision about what to do based<br>
on the actual values stored in the list, because it can't inspect those<br>
values.<br>
<br>
Please convince yourself of this before reading on.<br>
<br>
(Aside: Actually, there is one thing that "something" can do with an<br>
arbitrary element in the list, and that's perform "seq" on it. This<br>
complicates things considerably, so we'll ignore it.)<br>
<br>
Now, this means that you could replace the values in the list with<br>
something else, and "something" would have to do essentially the same<br>
thing. Which is just a fancy way of saying this:<br>
<br>
map f . something = something . map f<br>
<br>
In other words, "something" is a natural transformation. Without<br>
knowing anything about the implementation of "something", you know it's<br>
a natural transformation just because it has the type of a natural<br>
transformation!<br>
<br>
And, by the way, this reasoning doesn't just work for lists. If F and<br>
G are functors, then any function eta :: F a -> G a satisfies:<br>
<br>
fmap f . eta = eta . fmap f<br>
<br>
In Haskell, if it looks like a natural transformation, then it is a<br>
natural transformation. How cool is that?<br>
<br>
And, by the way, this is a great bit of intuition, as well. I always<br>
used to wonder what's so "natural" about a natural transformation in<br>
category theory.<br>
<br>
Now you know: a natural transformation transforms (F a) into (G a)<br>
without looking at the a's.<br>
<br>
Cheers,<br>
Andrew Bromage<div><div></div><div class="Wj3C7c"><br>
_______________________________________________<br>
Beginners mailing list<br>
<a href="mailto:Beginners@haskell.org" target="_blank">Beginners@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/beginners" target="_blank">http://www.haskell.org/mailman/listinfo/beginners</a><br>
</div></div></blockquote></div><br><br clear="all"><br>-- <br>Federico Brubacher<br><a href="http://www.fbrubacher.com">www.fbrubacher.com</a><br><br>Colonial Duty Free Shop<br><a href="http://www.colonial.com.uy">www.colonial.com.uy</a>
</div></div>