[Haskell-begin] Exercises for beginners and Natural Tansformations

[Federico Brubacher]

One more thing to see if I have the fold thing correct :
- foldr is good because it's lazy but is not tail recursive
- foldl is tail recursive so less stack space but not lazy so not good on
infinite lists
- flodl' is a mix of the good thing of both , so it is lazy and tail
recusive

Am I right ?
Thanks a lot
Federico

On Sat, Jul 19, 2008 at 1:17 PM, Federico Brubacher <fbrubacher at gmail.com>
wrote:

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



-- 
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/8ba0ed7e/attachment.htm