Re: [Haskell-begin] Exercises for beginners and Natural Tansformations

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Hi Federico, You would be best to use a left-fold (called foldLeft in the exercises) for Exercise 2 (sum :: List[Int ] -> Int) because it is tail recursive and *forces the accumulator*. This is analogous to foldl'. However, foldl, while tail recursive, does not force the accumulator. You can see that foldLeft uses a function call 'seq'. You might also be interested in this explanation of a left-fold on lists (if you can read Scala - it translates directly from Haskell): http://blog.tmorris.net/scalalistfoldleft-for-java-programmers/ Notice that stack space remains constant as the list is traversed, since in this case, it is a loop. - -- Tony Morris http://tmorris.net/ Real-world problems are simply degenerate cases of pure mathematical problems. Federico Brubacher wrote:

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 mailto:fbrubacher@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, mailto:ajb@spamcop.net> wrote:

G'day Federico.

Quoting Federico Brubacher mailto:fbrubacher@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@haskell.org mailto:Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

-- Federico Brubacher www.fbrubacher.com http://www.fbrubacher.com

Colonial Duty Free Shop www.colonial.com.uy http://www.colonial.com.uy

-- Federico Brubacher www.fbrubacher.com http://www.fbrubacher.com

Colonial Duty Free Shop www.colonial.com.uy http://www.colonial.com.uy

----------------------------------------------------------------------

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

-----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.6 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQFIglA+mnpgrYe6r60RAqxKAKDA+BJl30M+olvOLutPCl/oxrXD2gCeKuWe xe/ThJU40hwq7lzbmf40DrE= =1VYy -----END PGP SIGNATURE-----