Why is there a space leak here?

Juan Carlos Arevalo Baeza jcab@roningames.com
Sat, 09 Jun 2001 19:39:42 -0700

At 10:41 AM 6/8/2001 -0400, S. Alexander Jacobson wrote:

> > One portable way to implement a memoizing function in Haskell (if the
> > domain of the function is countable) is to lazily build a data
> > structure that contains the results of the function on every possible
> > argument.  Then you evaluate the portions of the data structure that
> > you need; the result on each argument is only evaluated once.  This
> > probably would count as a "growing expression", and it's certainly
> > possible that the function on some arguments would be bottom.
>I don't think I understood this.  Can you clarify?

    I believe I know what he's talking about. The example I've read about 
this technique is random-number generators. Because typical generators will 
need a state (the seed), they can be awkward to use in functional 
languages. Instead, you can just generate an infinite list of the random 
numbers, and extract them from that list lazily.

    Specifically, what he's talking about is the fact that a function like 
"Natural -> a" corresponds to a list where all the possible results for 
each number are stored in the corresponding position in the list. If you 
generate that list lazily, and then access it, each element will only be 
computed once (the compiler/interpreter takes care of this in a very 
natural way). But if you do this, the program will (or can) grow as more 
elements get computed.

    Am I making sense?


Juan Carlos "JCAB" Arevalo Baeza    | http://www.roningames.com
Senior Technology programmer        | mailto:jcab@roningames.com
Ronin Entertainment                 | ICQ: 10913692
                        (my opinions are only mine)
JCAB's Rumblings: http://www.metro.net/jcab/Rumblings/html/index.html