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:[EMAIL PROTECTED]] | Sent: 18 November 2001 23:18 | To: [EMAIL PROTECTED] | Subject: heap and walking through a very long list | | | | 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 reason). | | 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 =*= | | | _______________________________________________ | Haskell mailing list | [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell | _______________________________________________ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
