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