# [Haskell-begin] Exercises for beginners and Natural Tansformations

Tony Morris tmorris at tmorris.net
Sat Jul 19 16:36:14 EDT 2008

```-----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
> <fbrubacher at gmail.com <mailto: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
>     <mailto:ajb at spamcop.net>> wrote:
>
>         G'day Federico.
>
>
>         Quoting Federico Brubacher <fbrubacher at gmail.com
>         <mailto: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
>         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.
>
>
>         (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
>
>
>
>
>     --
>     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

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

```