[Haskell-cafe] Re: Looking for the fastest Haskell primes

[Heinrich Apfelmus]

Niemeijer, R.A. wrote:
> Heinrich Apfelmus wrote:
>> +1 except that exporting the potentially infinite list of primes is
>> problematic in that it may become a memory leak.
>>
>> I'd suggest to export two versions
>>
>>   primes  :: [Integer]
>>   primes' :: () -> [Integer]
>>
>> for casual (i.e. throwaway program to solve a Project Euler problem) and
>> for memory aware use respectively.
> 
> I'm afraid I don't quite follow. Would you mind explaining what the
> first parameter is for and how it would solve the memory leak?

Sure.

Lazy evaluation means that values, once evaluated, are stored in memory
until garbage collections reclaims them because it is clear that they
won't be used anymore. A  memory leak  happens when the programmer knows
that values won't be used anymore while this knowledge is not available
to the garbage collector.

More specifically, consider the following example

  main = do
      print (primes !! 100)
      print (primes !! 20)

This program will calculate the first 100 primes, and then print the
100th and the 1st prime. Now, after having printed the 100th prime, the
21th to 100th prime won't be used anymore and could thus be safely
reclaimed by garbage collection. But since they are part of the  primes
 list and this list is still in use for printing the 20th prime, this
won't happen; we have a memory leak.

The memory leak above can be avoided at the expense of recalculating the
list. Using a function  primes'  with a dummy argument ensures^1 that
the list of primes will be recalculated and garbage collected each time
it is used:

  main = do
      print (primes' () !! 100)
      print (primes' () !! 20)

Here, the first 100 primes are calculated, garbage collected and then
the first 20 primes are (re-)calculated and garbage collected.

We can fine control memory usage with the dummy argument version by
using  let  statements or  where  clauses

  main = do
      let ps = primes' () in do
        print (ps !! 101)
        print (ps !! 100)        -- no recalculation of ps
      print (primes' () !! 20)   -- recalculates first 20 primes


^1: Compiler optimizations may interfere with that behavior. Generally,
consensus is that the compiler should preserve sharing meticulously, but
this is not guaranteed. See also: "full laziness transform".



The above is folklore and should be written down properly at someplace
prominent. The wiki page

   http://www.haskell.org/haskellwiki/Memory_leak

is a start, but I think the explanation there is currently a bit murky.
Feel free to incorporate my writings above.


Regards,
apfelmus

--
http://apfelmus.nfshost.com