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@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