[Haskell-cafe] Re: sort and lazyness (?)
lrpalmer at gmail.com
Fri Dec 19 11:58:22 EST 2008
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 ++ _|_) = _|_
On Fri, Dec 19, 2008 at 9:48 AM, Duncan Coutts
<duncan.coutts at worc.ox.ac.uk>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).
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Haskell-Cafe