heap and walking through a very long list

Lukasz Pankowski lupan@zamek.gda.pl
19 Nov 2001 00:18:03 +0100

Hi. I wonder if there are any methods of walking through a very long list
without a huge heap. It is good that a laziness makes creation of
large stuctures delayed, but it seems that destruction of never again
used beginning of a list is also delayed (probably because of other

Consider the simple program:

        main = do putStrLn $ show $ hist_inc 100000 3

        hist_inc n b = hist (0,b) $ take n $ repeat b

        hist bnds is = accumArray (+) 0 bnds [(i, 1) | i <- is, inRange bnds i]

and it's output (compiled with GHC):

        $ ./hist_inc
        Stack space overflow: current size 1048576 bytes.
        Use `+RTS -Ksize' to increase it.

I am using GHC 5.0, does it have any optimization to overcome it (`-O
-fvia-C -O2-for-C' does not do this). It is obvious that the beginning
of the list is no longer needed (does garbage collector now this?).

If there is a way is it written somewhere in documentation?

I feel it insane to have to have let say 256Mb of memory because I
have 1 million measurements on a list. Currently I pipe the results to
a C program, nice UN!X practice which I would like avoid.


=*= Lukasz Pankowski =*=