heap and walking through a very long list

[Simon Peyton-Jones]

The trouble here is the usual one: accumArray is lazy,
and simply accumulates a giant closure in each array slot.
Then, when it is evaluated, the stack gets big.

There should really be a strict accumArray, just as there
should be a strict foldl.  There isn't in Haskell 98, but if you
are using a fixed type (like Int) you can use GHC's IArrays
(see documentation on the 'lang' package).  There's an
accumArray in there too, and it'll be strict for sure.

Simon

| -----Original Message-----
| From: Lukasz Pankowski [mailto:lupan@zamek.gda.pl]=20
| Sent: 18 November 2001 23:18
| To: haskell@haskell.org
| Subject: heap and walking through a very long list
|=20
|=20
|=20
| Hi. I wonder if there are any methods of walking through a=20
| very long list without a huge heap. It is good that a=20
| laziness makes creation of large stuctures delayed, but it=20
| seems that destruction of never again used beginning of a=20
| list is also delayed (probably because of other reason).
|=20
| Consider the simple program:
|=20
|         main =3D do putStrLn $ show $ hist_inc 100000 3
|=20
|         hist_inc n b =3D hist (0,b) $ take n $ repeat b
|=20
|         hist bnds is =3D accumArray (+) 0 bnds [(i, 1) | i <-=20
| is, inRange bnds i]
|=20
| and it's output (compiled with GHC):
|=20
|         $ ./hist_inc
|         Stack space overflow: current size 1048576 bytes.
|         Use `+RTS -Ksize' to increase it.
|=20
|=20
| I am using GHC 5.0, does it have any optimization to overcome=20
| it (`-O -fvia-C -O2-for-C' does not do this). It is obvious=20
| that the beginning of the list is no longer needed (does=20
| garbage collector now this?).
|=20
| If there is a way is it written somewhere in documentation?
|=20
| I feel it insane to have to have let say 256Mb of memory=20
| because I have 1 million measurements on a list. Currently I=20
| pipe the results to a C program, nice UN!X practice which I=20
| would like avoid.
|=20
|=20
| --=20
|=20
| =3D*=3D Lukasz Pankowski =3D*=3D
|=20
|=20
| _______________________________________________
| Haskell mailing list
| Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
|=20