"Albert Y. C. Lai" <tre...@vex.net> 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..] <copious output ...> 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 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
