[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
> 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 <mailto:Beginners at 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 at 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-----
More information about the Beginners
mailing list