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

[mf-hcafe-15c311f0c at etc-network.de]

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
position.


-- 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
[9.881155955344708e8,9.910336352165401e8,9.71000686630374e8,9.968532576451201e8,9.996200333115692e8]
$ grep 'total alloc' test.prof 
	total alloc =     744,180 bytes  (excludes profiling overheads)
$ ./test 10000 +RTS -p
[9.996199711457872e8,9.998928358545277e8,9.99960283632381e8,9.999707142123885e8,9.998952151508758e8]
$ 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.
$ 


so...

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?

thanks!
matthias