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

[Ivan Lazar Miljenovic]

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