Dan Weston wrote: > Ronald Guida wrote: >> I need some help with space and time leaks. >> >> I know of two types of space leak. The first type of leak occurs when >> a function uses unnecessary stack or heap space. >> >> GHCi> sum [1..10^6] >> *** Exception: stack overflow >> >> Apparently, the default definition for "sum" has a space leak. >> I can define my own sum in terms of strict foldl ... >> >> > sum' xs = foldl' (+) 0 xs >> >> ... and it doesn't overflow the stack. >> >> GHCi> sum' [1..10^6] >> 500000500000 >> (0.27 secs, 112403416 bytes) > > But it fills the heap? My intuition is that > > foldr (+) 0 [1..10^6] > > is the fusion of a good producer and consumer so no heap is wasted > constructing [1..10^6] but the stack is instead filled with > (1+),(2+),...,(999999+) unary functions, whereas > > foldl' (+) 0 [1..10^6] > > does not fill the stack with anything but does fill the heap with > [1..10^6] because foldl' is no longer a good consumer?
Nope, it runs in small space. The [1..10^6] is evaluated lazily, it is never larger than the thunk that represent the rest of the list. If foldl' is a "good consumer" then GHC can avoid making the list's cons-cells (:). If foldl' is not a "good consumer" then then each cons cell is created and then quickly garbage collected. > > If so, it seems that the stack is smaller than the heap (or else the > size of (1+) is much larger than that the element of an [Int]. > > Anyone know the truth of any of this? _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
