[Haskell-begin] Exercises for beginners and Natural Tansformations

[Chaddaï Fouché]

2008/7/19 Federico Brubacher <fbrubacher at gmail.com>:
> 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ï