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

On 24 July 2012 12:52, Qi Qi 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 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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- Ivan Lazar Miljenovic Ivan.Miljenovic@gmail.com http://IvanMiljenovic.wordpress.com

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- Ivan Lazar Miljenovic Ivan.Miljenovic@gmail.com http://IvanMiljenovic.wordpress.com