Foldl has the space leak effect, and that's why foldl' has been recommended. 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

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 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

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

"Albert Y. C. Lai" writes:

On 12-07-23 10:52 PM, Qi Qi wrote:

...

Foldl has the space leak effect, and that's why foldl' has been recommended.

foldr (+) and foldl (+) for Int have the same asymptotic costs, both time and space. See my http://www.vex.net/~trebla/haskell/lazy.xhtml

Therefore, I do not understand why they are labeled opposite space-leakness.

That may be true, but if the function argument supplied to foldr is lazy in its second argument, then the story can be quite different. Remember that foldr on a list [x1..xn] produces a chain of the following form: f x1 (f x2 ... (f xn z)) If f is lazy in its second argument, then evaluating the head of this chain does not force evaluation of the rest of the chain. Therefore, if you evaluate this chain from left to right and immediately discard each element in the chain as you go along, then this can be done in constant space. One example of this is when you evaluating the result of a right fold on an infinite list in ghci: ghci> foldr (\x y -> x + 10 : y) [] [1..] To display the resulting list, ghci evaluates the head of the list, displays it to the screen, then evaluates the head of the tail, the head of the tail of the tail... and so on. After displaying an element of the list, it can be reclaimed by the garbage collector. Hope this helps, -- Mathieu

The difference is that foldl *must* produce the entire list of thunks, even if f is lazy in its first argument. There's no foldl that can perform better given a sufficiently-lazy f; given head = foldr go fail where go x y = x fail = error "head: empty list" head [a,b,c,d] = foldr go fail [a,b,c,d] = go a (foldr go fail [b,c,d]) = a you might think you can define last = foldl go fail where go x y = y fail = error "last: empty list" but this fails to be sufficiently lazy: last [a,b,c,d] = foldl go fail [a,b,c,d] = foldl go (go fail a) [b,c,d] = foldl go (go (go fail a) b) [c,d] = foldl go (go (go (go fail a) b) c) [d] = foldl go (go (go (go (go fail a) b) c) d) [] = go (go (go (go fail a) b) c) d = d which allocates lots of extra space for thunks, which may even take more memory than the original list. Whereas if last uses foldl': last [a,b,c,d] = foldl' go fail [a,b,c,d] = let z = go fail a in seq z $ foldl' go z [b,c,d] = foldl' go a [b,c,d] = let z = go a b in seq z $ foldl' go z [c,d] = foldl' go b [c,d] = ... = let z = go c d in seq z $ foldl' go z [] = foldl' go d [] = d -- ryan