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.)
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
