On Monday 24 January 2011 11:59:15, Seung Soo, Ha wrote:

my setup: phenom II quadcore, 4GB mem Ubuntu Maverick

While implementing my own reverse in "99 haskell questions",

I made the following mistake: (Caution: stack over flow causing code below)

reverse'::[a] -> [a] reverse' [] = [] reverse' [x] = [x] reverse' xs = last xs : init (reverse' xs)

The last line is the wrong part. It should be reverse' xs = last xs : reverse' (init xs)

anyway, the original code seems to cause an infinite recursion by repeating the last part forever.

Yes. In loop :: [Int] loop = 1 : init loop the evaluation goes loop = 1 : init loop -- now it must be checked whether init loop -- a) gives an error because loop is empty (which it isn't, so no error) -- b) is empty because loop is one element long -- c) is nonempty because loop contains at least two elements ~> 1 : init (1 : init loop) -- same problem in the parentheses ~> 1 : init (1 : init (1 : init loop)) -- ad infinitum To see whether loop has a second element, we first must see whether loop has a second element. the structure is the same as for your last line of reverse', only there you have function calls instead of named values (1, loop).

When I try this out on ghci:

*Main> reverse' [1,2,3,4,5] [5*** Exception: stack overflow *Main>

The problem is, unless I manually exit ghci, the "stack" does not seem to be freed (garbage collected?) and memory remains fully occupied by ghci.

GHC used to not return any memory it has allocated to the OS (in case it is needed again later), thus ghci wouldn't return any memory either. I think¹ that as of GHC-7, GHC now returns memory to the OS after memory usage has dropped (not immediately, of course, it waits until memory usage has been lower for a bit). ¹ I may be wrong, it may have already been in some 6.12. With ghci-7.0.1, after ^C-ing the computation at 24% memory, according to top, it dropped to 4%, didn't wait to check whether more memory would be released later.

I tried waiting a bit, but it stayed the same.

Is this expected behavior?

I think so. At least for GHC < 7.

Shouldn't the GC kick in? Is this orthogonal of the GC?

The GC would free the memory but keep it for the process to reuse. If you can run space consuming things afterwards without ghci's memory usage going up, that's what's happening.

I think this would help me understand haskell and GHC much better.