[Haskell-cafe] Re: sort and lazyness (?)

Luke Palmer 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 ++ _|_) = _|_

Luke

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).
>
> Duncan
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20081219/b3fa25c7/attachment.htm


More information about the Haskell-Cafe mailing list