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 <qiqi...@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 <qiqi...@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@haskell.org > >> > http://www.haskell.org/mailman/listinfo/haskell-cafe > >> > > >> > >> > >> > >> -- > >> Ivan Lazar Miljenovic > >> ivan.miljeno...@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.miljeno...@gmail.com > http://IvanMiljenovic.wordpress.com > > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe >
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
