Hmm, okay. I guess there are some subtle technical jargon issues then. You're talking about space in terms of fully evaluated inputs. But whatever I used to talk about this, I would want it to distinguish the behavior of "reverse" and, say, "map id". But I suppose strictness is a better tool to talk about that difference than space complexity. I.e.:
reverse (xs ++ _|_) = _|_ Luke On Fri, Dec 19, 2008 at 9:48 AM, Duncan Coutts <[email protected]>wrote: > On Fri, 2008-12-19 at 08:44 -0700, Luke Palmer wrote: > > On Fri, Dec 19, 2008 at 8:26 AM, Duncan Coutts > > > > It allocates a new list cell for every cell it finds in the > > input list. If the input list can be garbage collected then > > reverse takes constant space because each time it inspects a > > list cell from the input list that cell can be garbage > > collected. If the input list is being retained for some other > > reason then reverse will take linear space. > > > > I don't think that's true. It must inspect the whole input list to > > give the first element of the output list, but it cannot garbage > > collect the input list because it needs to yield every element of it. > > > > When I tested: > > > > ghci> length $ reverse [1..10^7] > > > > It certainly did not run in constant space. > > But that's because the input list took constant not linear space. I said > it allocates an element for every element in the input. So it's only > constant space if we can offset a linear amount of space used for the > output with a linear amount of space saved from collecting the input. > > Try this: > > using the helper function: > force = foldr (\x xs -> seq xs (x : xs)) [] > > Then we want to look at the heap space used to evaluate: > head (force [1..10^6]) > > and compare it to: > head (reverse (force [1..10^6])) > > We can do that using $ ghc +RTS -s -RTS -e 'expr' > and looking at the "bytes maximum residency" in the GC stats. > > On my box (64bit) we find that the two examples use almost exactly the > same maximum heap size (of about 20Mb). > > So that's why I was claiming reverse takes constant net memory (when the > input list is evaluated and can be subsequently discarded). > > Duncan > >
_______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
