[Haskell-cafe] why does a foldr not have a space leak effect?

[Qi Qi]

This question actually was risen when I read a relevant part in the RWH 
book.
Now it's much clearer to me. Thanks Ivan!

On Monday, July 23, 2012 10:04:00 PM UTC-5, Ivan Lazar Miljenovic wrote:
>
> On 24 July 2012 12:52, Qi Qi <qiqi789 at gmail.com> wrote: 
> > Foldl has the space leak effect, and that's why foldl' has been 
> recommended. 
>
> foldl can have a space leak due to accumulation of thunks: 
>
> foldl f a [b,c,d] = f (f (f a b) c) d 
>
> ^^ Building up a chain of functions.  As such, these thunks are kept 
> around until the result is actually needed.  foldl' forces each 
> previous thunk first. 
>
> foldr f a [b,c,d] = f b (f c (f d a)) 
>
> ^^ This also builds up a chain of functions... but foldr is typically 
> used in cases where f is lazy in the second argument.  For example, 
> and = foldr (&&); so as soon as it hits one False value, it doesn't 
> need to go on with the rest of the list. 
>
> Thus, it's not that foldr doesn't necessarily have a space-leak 
> effect; it's just that foldr is used in cases where you're either a) 
> using something that should stop traversing the list when it reaches a 
> certain type of value, or b) you want to preserve the list order (e.g. 
> using foldr to implement map).  foldl is used in cases where the 
> entire list _does_ need to be consumed, so the possibility of a space 
> leak becomes more of an issue. 
>
> Note also the recommendation of foldl' is a bit of a premature 
> optimisation: it isn't _always_ needed (short lists, values are 
> evaluated soon after the fold, etc.), but it's easier to always prefer 
> foldl' over foldl rather than having to go through your code base and 
> selectively replace foldl with foldl'. 
>
> > 
> > On Monday, July 23, 2012 9:44:59 PM UTC-5, Ivan Lazar Miljenovic wrote: 
> >> 
> >> (Trying again using the real mailing list address rather than google 
> >> groups) 
> >> 
> >> On 24 July 2012 12:37, Qi Qi <qiqi789 at gmail.com> wrote: 
> >> > Hi, 
> >> > 
> >> > I wonder why a foldr does not have a space leak effect? 
> >> > Any hints? Thanks. 
> >> 
> >> Why should it? 
> >> 
> >> Does it not depend on the function you're folding, the type of data 
> >> you're folding over, how you use it, etc.? 
> >> 
> >> > 
> >> > Qi 
> >> > 
> >> > _______________________________________________ 
> >> > Haskell-Cafe mailing list 
> >> > Haskell-Cafe at haskell.org 
> >> > http://www.haskell.org/mailman/listinfo/haskell-cafe 
> >> > 
> >> 
> >> 
> >> 
> >> -- 
> >> Ivan Lazar Miljenovic 
> >> Ivan.Miljenovic at gmail.com 
> >> http://IvanMiljenovic.wordpress.com 
> >> 
> >> _______________________________________________ 
> >> Haskell-Cafe mailing list 
> >> Haskell-Cafe at haskell.org 
> >> http://www.haskell.org/mailman/listinfo/haskell-cafe 
>
>
>
> -- 
> Ivan Lazar Miljenovic 
> Ivan.Miljenovic at gmail.com 
> http://IvanMiljenovic.wordpress.com 
>
> _______________________________________________ 
> Haskell-Cafe mailing list 
> Haskell-Cafe at haskell.org 
> http://www.haskell.org/mailman/listinfo/haskell-cafe 
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20120723/de6e2d08/attachment.htm>