2008/7/19 Federico Brubacher
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ï