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

9 messages
Open this post in threaded view
|

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

 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
Open this post in threaded view
|

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

Open this post in threaded view
|

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

Open this post in threaded view
|

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

Open this post in threaded view
|

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

 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?
Open this post in threaded view
|

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

Open this post in threaded view
|

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

 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 !