[Haskell-cafe] Question about memory usage

[Andrew Coppin]

Tako Schotanus wrote:
> > fiblist = 0 : 1 : (zipWith (+) fiblist (tail fiblist))
>   
>
> Very interesting stuff for somebody who comes from an imperative world 
> of course.

Oh yes, that old chestnut. There's a page on the wiki somewhere with a 
whole collection of these cryptic one-liners - Pascal's triangle, the 
prime numbers, the Fibonacci numbers, etc.

> But then I read that "Once it's been referenced, then the list up to 
> where you looked is concrete - the computations /won't/ be repeated."
> and I started wondering how that works.

fiblist is a global variable. It points to a list calculation 
expression. When a list cell is calculated, the calculation node is 
overwritten with the result of the calculation. When you access the 
list, you look at each cell; if it's already done, you just use it. If 
it's not done, execute it and then use it. (How it actually works below 
that is a problem for the runtime engine to figure out, and varies by 
Haskell implementation. For example, GHC uses the spineless tagless 
G-machine.)

> Because this seems to mean that functions could have unknown (to the 
> caller) memory requirements.

Yes.

> How does one, programming in Haskell, keep that in check?

...and here begins an entire textbook that nobody has published yet.

> And when does that memory get reclaimed?

It's called "garbage collection". The memory is reclaimed when it 
becomes unreachable becuase there are no pointers to it left. In the 
example above, fiblist is a global variable, so the answer to "when does 
it get freed?" would be "never". (I believe it's called a CAF leak.) 
Whether this is very cool or a major performance issue depends on your 
point of view; you're trading space for time. (Then again, the Fibonacci 
numbers can be computed in O(1) time, and nobody ever needs Fibonacci 
numbers in the first place, so this is obviously example code.)