Hi all,
I think i will love this list :) Yesterday I was looking at this Haskell Exercises for beginners [1] and got somewhat stuck at Ex nbr 2 , here's why: The idea of this exercises is that you don't use built in Haskell Lists, so no pattern matching, instead you have to use the data type list provided in the source of the exercise. My friend who is more advanced in Haskell said this approach is good because you get to learn natural Transformations. So I googled that and I came up with this [2]. I can read al little bit of category theory but I would love to know how to apply [2] in the sum exercise. Anyway as we all know summing all the elements in a list using Haskell lists is trivial : sum :: [Int] -> Int sum (xs) = foldr(+)0xs But how to do it with Natural transformations ??? Thanks a lot Federico [1] http://blog.tmorris.net/haskell-exercises-for-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/668e9e08/attachment.htm |
G'day Federico.
Quoting Federico Brubacher <[hidden email]>: > 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 |
@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, <[hidden email]> wrote: > G'day Federico. > > Quoting Federico Brubacher <[hidden email]>: > > 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 > [hidden email] > 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 |
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 <[hidden email]> 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, <[hidden email]> wrote: > >> G'day Federico. >> >> Quoting Federico Brubacher <[hidden email]>: >> >> 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 >> [hidden email] >> 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 |
2008/7/19 Federico Brubacher <[hidden email]>:
> 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 > - foldl' is a mix of the good thing of both , so it is lazy and tail > recusive > Am I right ? No... Did you read the link I gave you ? The explanation there is pretty good. First foldr and foldl are both lazy. foldl' is strict in the accumulator. The advantage of foldr is that it is not tail recursive, in "foldr f k (x:xs)" the first reduction will give us : foldr f k (x:xs) ==> f x (foldr f k xs) If f is lazy in its second argument we can then reduce f immediately, and maybe consume the result. Which means that we could potentially do our thing in constant space, or process infinite lists or ... But the problem in your code was that max is not lazy in its second argument, which is why using foldr there wasn't a good idea. foldl is almost never the right solution, compared to foldr, it doesn't expose f before the end of the list is reached, which means we can't do reduction at the same time we travel the list. foldl' is nice because being strict in the accumulator it will force the evaluation of f at each step, thus it won't create a big thunk of call to f we'll have to unravel at the end like foldl. (Well in certain case it still will, in nested lazy structure for example but that's a lesson for another day) So : foldr when f is lazy in it's second argument and we can process its result at each step, foldl' when f is strict in it's second argument, foldl never but read the HaskellWiki link, you'll see better why you must use foldl' here. -- Jeda? |
In reply to this post by Federico Brubacher
-----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 > <[hidden email] <mailto:[hidden email]>> 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, <[hidden email] > <mailto:[hidden email]>> wrote: > > G'day Federico. > > > Quoting Federico Brubacher <[hidden email] > <mailto:[hidden email]>>: > > 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 > [hidden email] <mailto:[hidden email]> > 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 > [hidden email] > 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----- |
In reply to this post by Chaddaï Fouché
2008/7/19 Chadda? Fouch? <[hidden email]>:
> 2008/7/19 Federico Brubacher <[hidden email]>: >> 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 >> - foldl' is a mix of the good thing of both , so it is lazy and tail >> recusive >> Am I right ? > > No... Did you read the link I gave you ? The explanation there is pretty good. > First foldr and foldl are both lazy. foldl' is strict in the accumulator. Ok, I'm confusing this with another discussion, sorry... ^^ The link I was speaking about is : http://www.haskell.org/haskellwiki/Foldr_Foldl_Foldl%27 (But the things I said about the folds are still true :-) -- Jeda? PS : ajb, thank you for the explanation, it was very clear ! |
In reply to this post by Federico Brubacher
On Sat, 19 Jul 2008 10:00:12 -0300, "Federico Brubacher"
<[hidden email]> wrote: >Hi all, >I think i will love this list :) Thank you. Please let us know if you have any suggestions for improvement, comments, criticism, etc. > [...] > >My friend who is more advanced in Haskell said this approach is good because >you get to learn natural Transformations. So I googled that and I came up >with this [2]. I can read al little bit of category theory but I would love >to know how to apply [2] in the sum exercise. > > [...] > >[1] http://blog.tmorris.net/haskell-exercises-for-beginners/ It seems that you forgot to include the link to [2]. Which reference was that? -- Benjamin L. Russell |
>
> >[1] http://blog.tmorris.net/haskell-exercises-for-beginners/ > > It seems that you forgot to include the link to [2]. Which reference > was that? > > -- Benjamin L. Russell Yes, sorry about that, [2] was : [2] http://www.haskell.org/haskellwiki/Category_theory/Natural_transformation Thank you guys!! Federico -- 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/20080722/9e9f1f6b/attachment.htm |
Free forum by Nabble | Edit this page |