[Haskell-begin] Exercises for beginners and Natural Tansformations

[Federico Brubacher]

@A. Wagner 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

@A. Bromage
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.

Cheers from Uruguay
Federico

On Sat, Jul 19, 2008 at 11:41 AM, <ajb at spamcop.net> wrote:

> 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
>
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
>



-- 
Federico Brubacher
www.fbrubacher.com

Colonial Duty Free Shop
www.colonial.com.uy
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/beginners/attachments/20080719/01669061/attachment-0001.htm