[Haskell-cafe] How do I get this done in constant mem?

mf-hcafe-15c311f0c at etc-network.de mf-hcafe-15c311f0c at etc-network.de
Fri Oct 9 16:05:11 EDT 2009

Hi all,

I think there is something about my use of the IO monad that bites me,
but I am bored of staring at the code, so here you g.  The code goes
through a list of records and collects the maximum in each record

-- test.hs
import Random
import System.Environment (getArgs)
import System.IO (putStr)

samples :: Int -> Int -> IO [[Double]]
samples i j = sequence . replicate i . sequence . replicate j $ randomRIO (0, 1000 ** 3)

maxima :: [[Double]] -> [Double]
maxima samples@(_:_) = foldr (\ x y -> map (uncurry max) $ zip x y) (head samples) (tail samples)

main = do
  args <- getArgs
  x <- samples (read (head args)) 5
  putStr . (++ "\n") . show $ maxima x

I would expect this to take constant memory (foldr as well as foldl),
but this is what happens:

$ ghc -prof --make -O9 -o test test.hs
[1 of 1] Compiling Main             ( test.hs, test.o )
Linking test ...
$ ./test 100 +RTS -p
$ grep 'total alloc' test.prof 
	total alloc =     744,180 bytes  (excludes profiling overheads)
$ ./test 10000 +RTS -p
$ grep 'total alloc' test.prof 
	total alloc =  64,777,692 bytes  (excludes profiling overheads)
$ ./test 1000000 +RTS -p
Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize' to increase it.


does sequence somehow force the entire list of monads into evaluation
before the head of the result list can be used?  what can i do to
implement this in constant memory?


More information about the Haskell-Cafe mailing list