RE: heap and walking through a very long list
You can do it specifically for GHC, not not in standard Haskell (except grossly inefficiently). To see how to do it in GHC, look at the implementation in the source code (ghc/lib/std), which is online (check the CVS repository link on GHC's home page). Meanwhile you could use the IArray stuff. Simon | -Original Message- | From: Joe English [mailto:[EMAIL PROTECTED]] | Sent: 25 November 2001 00:12 | To: [EMAIL PROTECTED] | Subject: Re: heap and walking through a very long list | | | | Simon Peyton-Jones wrote: | | There should really be a strict accumArray, just as there | should be a | strict foldl. | | Yes, please! | | Is there a way to write a strict version of accumArray in | Haskell 98, or does this need to be done by the implementation? | | | --Joe English | | [EMAIL PROTECTED] | | ___ | Haskell mailing list | [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell | ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
Re: heap and walking through a very long list
Simon Peyton-Jones wrote: There should really be a strict accumArray, just as there should be a strict foldl. Yes, please! Is there a way to write a strict version of accumArray in Haskell 98, or does this need to be done by the implementation? --Joe English [EMAIL PROTECTED] ___ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
RE: heap and walking through a very long list
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 10 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
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 10 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
